Package edu.jas.poly

Class GenWordPolynomial<C extends RingElem<C>>

java.lang.Object
edu.jas.poly.GenWordPolynomial<C>
Type Parameters:
C - coefficient type
All Implemented Interfaces:
AbelianGroupElem<GenWordPolynomial<C>>, Element<GenWordPolynomial<C>>, MonoidElem<GenWordPolynomial<C>>, RingElem<GenWordPolynomial<C>>, Serializable, Comparable<GenWordPolynomial<C>>, Iterable<WordMonomial<C>>

public final class GenWordPolynomial<C extends RingElem<C>> extends Object implements RingElem<GenWordPolynomial<C>>, Iterable<WordMonomial<C>>
GenWordPolynomial generic polynomials implementing RingElem. Non-commutative string polynomials over C. Objects of this class are intended to be immutable. The implementation is based on TreeMap respectively SortedMap from words to coefficients. Only the coefficients are modeled with generic types, the "exponents" are fixed to Word. C can also be a non integral domain, e.g. a ModInteger, i.e. it may contain zero divisors, since multiply() does check for zeros.
See Also:
  • Field Details

    • ring

      public final GenWordPolynomialRing<C extends RingElem<C>> ring
      The factory for the polynomial ring.
    • val

      final SortedMap<Word,C extends RingElem<C>> val
      The data structure for polynomials.
    • logger

      private static final org.apache.logging.log4j.Logger logger
    • debug

      private static final boolean debug
  • Constructor Details

    • GenWordPolynomial

      private GenWordPolynomial(GenWordPolynomialRing<C> r, TreeMap<Word,C> t)
      Private constructor for GenWordPolynomial.
      Parameters:
      r - polynomial ring factory.
      t - TreeMap with correct ordering.
    • GenWordPolynomial

      public GenWordPolynomial(GenWordPolynomialRing<C> r)
      Constructor for zero GenWordPolynomial.
      Parameters:
      r - polynomial ring factory.
    • GenWordPolynomial

      public GenWordPolynomial(GenWordPolynomialRing<C> r, C c, Word e)
      Constructor for GenWordPolynomial c * xe.
      Parameters:
      r - polynomial ring factory.
      c - coefficient.
      e - word.
    • GenWordPolynomial

      public GenWordPolynomial(GenWordPolynomialRing<C> r, C c)
      Constructor for GenWordPolynomial c * x0.
      Parameters:
      r - polynomial ring factory.
      c - coefficient.
    • GenWordPolynomial

      public GenWordPolynomial(GenWordPolynomialRing<C> r, Word e)
      Constructor for GenWordPolynomial xe.
      Parameters:
      r - polynomial ring factory.
      e - word.
    • GenWordPolynomial

      public GenWordPolynomial(GenWordPolynomialRing<C> r, ExpVector e)
      Constructor for GenWordPolynomial xe.
      Parameters:
      r - polynomial ring factory.
      e - exponent vector.
    • GenWordPolynomial

      public GenWordPolynomial(GenWordPolynomialRing<C> r, C c, ExpVector e)
      Constructor for GenWordPolynomial c * xe.
      Parameters:
      r - polynomial ring factory.
      c - coefficient.
      e - exponent vector.
    • GenWordPolynomial

      protected GenWordPolynomial(GenWordPolynomialRing<C> r, SortedMap<Word,C> v)
      Constructor for GenWordPolynomial.
      Parameters:
      r - polynomial ring factory.
      v - the SortedMap of some other polynomial.
  • Method Details

    • factory

      public GenWordPolynomialRing<C> factory()
      Get the corresponding element factory.
      Specified by:
      factory in interface Element<C extends RingElem<C>>
      Returns:
      factory for this Element.
      See Also:
    • copy

      public GenWordPolynomial<C> copy()
      Copy this GenWordPolynomial.
      Specified by:
      copy in interface Element<C extends RingElem<C>>
      Returns:
      copy of this.
    • length

      public int length()
      Length of GenWordPolynomial.
      Returns:
      number of coefficients of this GenWordPolynomial.
    • getMap

      public SortedMap<Word,C> getMap()
      Word to coefficient map of GenWordPolynomial.
      Returns:
      val as unmodifiable SortedMap.
    • doPutToMap

      public void doPutToMap(Word e, C c)
      Put a Word to coefficient entry into the internal map of this GenWordPolynomial. Note: Do not use this method unless you are constructing a new polynomial. this is modified and breaks the immutability promise of this class.
      Parameters:
      e - word.
      c - coefficient.
    • doRemoveFromMap

      public void doRemoveFromMap(Word e, C c)
      Remove a Word to coefficient entry from the internal map of this GenWordPolynomial. Note: Do not use this method unless you are constructing a new polynomial. this is modified and breaks the immutability promise of this class.
      Parameters:
      e - Word.
      c - expected coefficient, null for ignore.
    • doPutToMap

      public void doPutToMap(SortedMap<Word,C> vals)
      Put an a sorted map of words to coefficients into the internal map of this GenWordPolynomial. Note: Do not use this method unless you are constructing a new polynomial. this is modified and breaks the immutability promise of this class.
      Parameters:
      vals - sorted map of wordss and coefficients.
    • toString

      public String toString()
      String representation of GenWordPolynomial.
      Overrides:
      toString in class Object
      See Also:
    • toScript

      public String toScript()
      Get a scripting compatible string representation.
      Specified by:
      toScript in interface Element<C extends RingElem<C>>
      Returns:
      script compatible representation for this Element.
      See Also:
    • toScriptFactory

      public String toScriptFactory()
      Get a scripting compatible string representation of the factory.
      Specified by:
      toScriptFactory in interface Element<C extends RingElem<C>>
      Returns:
      script compatible representation for this ElemFactory.
      See Also:
    • isZERO

      public boolean isZERO()
      Is GenWordPolynomial<C> zero.
      Specified by:
      isZERO in interface AbelianGroupElem<C extends RingElem<C>>
      Returns:
      If this is 0 then true is returned, else false.
      See Also:
    • isONE

      public boolean isONE()
      Is GenWordPolynomial<C> one.
      Specified by:
      isONE in interface MonoidElem<C extends RingElem<C>>
      Returns:
      If this is 1 then true is returned, else false.
      See Also:
    • isUnit

      public boolean isUnit()
      Is GenWordPolynomial<C> a unit.
      Specified by:
      isUnit in interface MonoidElem<C extends RingElem<C>>
      Returns:
      If this is a unit then true is returned, else false.
      See Also:
    • isConstant

      public boolean isConstant()
      Is GenWordPolynomial<C> a constant.
      Returns:
      If this is a constant polynomial then true is returned, else false.
    • isHomogeneous

      public boolean isHomogeneous()
      Is GenWordPolynomial<C> homogeneous.
      Returns:
      true, if this is homogeneous, else false.
    • equals

      public boolean equals(Object B)
      Comparison with any other object.
      Specified by:
      equals in interface Element<C extends RingElem<C>>
      Overrides:
      equals in class Object
      Parameters:
      B -
      Returns:
      true if this is equal to b, else false.
      See Also:
    • hashCode

      public int hashCode()
      Hash code for this polynomial.
      Specified by:
      hashCode in interface Element<C extends RingElem<C>>
      Overrides:
      hashCode in class Object
      Returns:
      the hashCode.
      See Also:
    • compareTo

      public int compareTo(GenWordPolynomial<C> b)
      GenWordPolynomial comparison.
      Specified by:
      compareTo in interface Comparable<C extends RingElem<C>>
      Specified by:
      compareTo in interface Element<C extends RingElem<C>>
      Parameters:
      b - GenWordPolynomial.
      Returns:
      sign(this-b).
    • signum

      public int signum()
      GenWordPolynomial signum.
      Specified by:
      signum in interface AbelianGroupElem<C extends RingElem<C>>
      Returns:
      sign(ldcf(this)).
    • numberOfVariables

      public int numberOfVariables()
      Number of variables.
      Returns:
      ring.alphabet.length().
    • leadingMonomial

      public Map.Entry<Word,C> leadingMonomial()
      Leading monomial.
      Returns:
      first map entry.
    • leadingWord

      public Word leadingWord()
      Leading word.
      Returns:
      first highest word.
    • trailingWord

      public Word trailingWord()
      Trailing word.
      Returns:
      last lowest word.
    • leadingBaseCoefficient

      public C leadingBaseCoefficient()
      Leading base coefficient.
      Returns:
      first coefficient.
    • trailingBaseCoefficient

      public C trailingBaseCoefficient()
      Trailing base coefficient.
      Returns:
      coefficient of constant term.
    • coefficient

      public C coefficient(Word e)
      Coefficient.
      Parameters:
      e - word.
      Returns:
      coefficient for given word.
    • reductum

      public GenWordPolynomial<C> reductum()
      Reductum.
      Returns:
      this - leading monomial.
    • degree

      public long degree()
      Maximal degree.
      Returns:
      maximal degree in any variables.
    • maxNorm

      public C maxNorm()
      GenWordPolynomial maximum norm.
      Returns:
      ||this||.
    • sumNorm

      public C sumNorm()
      GenWordPolynomial sum norm.
      Returns:
      sum of all absolute values of coefficients.
    • sum

      GenWordPolynomial summation.
      Specified by:
      sum in interface AbelianGroupElem<C extends RingElem<C>>
      Parameters:
      S - GenWordPolynomial.
      Returns:
      this+S.
    • sum

      public GenWordPolynomial<C> sum(C a, Word e)
      GenWordPolynomial addition. This method is not very efficient, since this is copied.
      Parameters:
      a - coefficient.
      e - word.
      Returns:
      this + a e.
    • sum

      public GenWordPolynomial<C> sum(C a)
      GenWordPolynomial addition. This method is not very efficient, since this is copied.
      Parameters:
      a - coefficient.
      Returns:
      this + a x0.
    • subtract

      public GenWordPolynomial<C> subtract(GenWordPolynomial<C> S)
      GenWordPolynomial subtraction.
      Specified by:
      subtract in interface AbelianGroupElem<C extends RingElem<C>>
      Parameters:
      S - GenWordPolynomial.
      Returns:
      this-S.
    • subtract

      public GenWordPolynomial<C> subtract(C a, Word e)
      GenWordPolynomial subtraction. This method is not very efficient, since this is copied.
      Parameters:
      a - coefficient.
      e - word.
      Returns:
      this - a e.
    • subtract

      public GenWordPolynomial<C> subtract(C a)
      GenWordPolynomial subtract. This method is not very efficient, since this is copied.
      Parameters:
      a - coefficient.
      Returns:
      this + a x0.
    • negate

      public GenWordPolynomial<C> negate()
      GenWordPolynomial negation.
      Specified by:
      negate in interface AbelianGroupElem<C extends RingElem<C>>
      Returns:
      -this.
    • abs

      public GenWordPolynomial<C> abs()
      GenWordPolynomial absolute value, i.e. leadingCoefficient > 0.
      Specified by:
      abs in interface AbelianGroupElem<C extends RingElem<C>>
      Returns:
      abs(this).
    • multiply

      public GenWordPolynomial<C> multiply(GenWordPolynomial<C> S)
      GenWordPolynomial multiplication.
      Specified by:
      multiply in interface MonoidElem<C extends RingElem<C>>
      Parameters:
      S - GenWordPolynomial.
      Returns:
      this*S.
    • multiply

      GenWordPolynomial left and right multiplication. Product with two polynomials.
      Parameters:
      S - GenWordPolynomial.
      T - GenWordPolynomial.
      Returns:
      S*this*T.
    • multiply

      public GenWordPolynomial<C> multiply(C s)
      GenWordPolynomial multiplication. Product with coefficient ring element.
      Parameters:
      s - coefficient.
      Returns:
      this*s.
    • multiply

      public GenWordPolynomial<C> multiply(C s, C t)
      GenWordPolynomial multiplication. Product with coefficient ring element.
      Parameters:
      s - coefficient.
      t - coefficient.
      Returns:
      s*this*t.
    • monic

      public GenWordPolynomial<C> monic()
      GenWordPolynomial monic, i.e. leadingCoefficient == 1. If leadingCoefficient is not invertible returns this unmodified.
      Returns:
      monic(this).
    • multiply

      public GenWordPolynomial<C> multiply(C s, Word e)
      GenWordPolynomial multiplication. Product with ring element and word.
      Parameters:
      s - coefficient.
      e - left word.
      Returns:
      this * s e.
    • multiply

      public GenWordPolynomial<C> multiply(Word e, Word f)
      GenWordPolynomial left and right multiplication. Product with ring element and two words.
      Parameters:
      e - left word.
      f - right word.
      Returns:
      e * this * f.
    • multiply

      public GenWordPolynomial<C> multiply(C s, Word e, Word f)
      GenWordPolynomial left and right multiplication. Product with ring element and two words.
      Parameters:
      s - coefficient.
      e - left word.
      f - right word.
      Returns:
      e * this * s * f.
    • multiply

      public GenWordPolynomial<C> multiply(C s, Word e, C t, Word f)
      GenWordPolynomial left and right multiplication. Product with ring element and two words.
      Parameters:
      s - coefficient.
      e - left word.
      t - coefficient.
      f - right word.
      Returns:
      s * e * this * t * f.
    • multiply

      public GenWordPolynomial<C> multiply(Word e)
      GenWordPolynomial multiplication. Product with word.
      Parameters:
      e - word (!= null).
      Returns:
      this * e.
    • multiply

      public GenWordPolynomial<C> multiply(Map.Entry<Word,C> m)
      GenWordPolynomial multiplication. Product with 'monomial'.
      Parameters:
      m - 'monomial'.
      Returns:
      this * m.
    • divide

      public GenWordPolynomial<C> divide(C s)
      GenWordPolynomial division. Division by coefficient ring element. Fails, if exact division is not possible.
      Parameters:
      s - coefficient.
      Returns:
      this/s.
    • quotientRemainder

      public GenWordPolynomial<C>[] quotientRemainder(GenWordPolynomial<C> S)
      GenWordPolynomial division with remainder. Fails, if exact division by leading base coefficient is not possible. Meaningful only for univariate polynomials over fields, but works in any case.
      Specified by:
      quotientRemainder in interface MonoidElem<C extends RingElem<C>>
      Parameters:
      S - nonzero GenWordPolynomial with invertible leading coefficient.
      Returns:
      [ quotient , remainder ] with this = quotient * S + remainder and deg(remainder) < deg(S) or remainder = 0.
      See Also:
    • divide

      public GenWordPolynomial<C> divide(GenWordPolynomial<C> S)
      GenWordPolynomial division. Fails, if exact division by leading base coefficient is not possible. Meaningful only for univariate polynomials over fields, but works in any case.
      Specified by:
      divide in interface MonoidElem<C extends RingElem<C>>
      Parameters:
      S - nonzero GenWordPolynomial with invertible leading coefficient.
      Returns:
      quotient with this = quotient * S + remainder.
      See Also:
    • remainder

      public GenWordPolynomial<C> remainder(GenWordPolynomial<C> S)
      GenWordPolynomial remainder. Fails, if exact division by leading base coefficient is not possible. Meaningful only for univariate polynomials over fields, but works in any case.
      Specified by:
      remainder in interface MonoidElem<C extends RingElem<C>>
      Parameters:
      S - nonzero GenWordPolynomial with invertible leading coefficient.
      Returns:
      remainder with this = quotient * S + remainder.
      See Also:
    • gcd

      GenWordPolynomial greatest common divisor. Only for univariate polynomials over fields.
      Specified by:
      gcd in interface RingElem<C extends RingElem<C>>
      Parameters:
      S - GenWordPolynomial.
      Returns:
      gcd(this,S).
    • egcd

      public GenWordPolynomial<C>[] egcd(GenWordPolynomial<C> S)
      GenWordPolynomial extended greatest common divisor. Only for univariate polynomials over fields.
      Specified by:
      egcd in interface RingElem<C extends RingElem<C>>
      Parameters:
      S - GenWordPolynomial.
      Returns:
      [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
    • hegcd

      public GenWordPolynomial<C>[] hegcd(GenWordPolynomial<C> S)
      GenWordPolynomial half extended greatest common divisor. Only for univariate polynomials over fields.
      Parameters:
      S - GenWordPolynomial.
      Returns:
      [ gcd(this,S), a ] with a*this + b*S = gcd(this,S).
    • inverse

      public GenWordPolynomial<C> inverse()
      GenWordPolynomial inverse. Required by RingElem. Throws not invertible exception.
      Specified by:
      inverse in interface MonoidElem<C extends RingElem<C>>
      Returns:
      x with this * x = 1, if it exists.
    • modInverse

      public GenWordPolynomial<C> modInverse(GenWordPolynomial<C> m)
      GenWordPolynomial modular inverse. Only for univariate polynomials over fields.
      Parameters:
      m - GenWordPolynomial.
      Returns:
      a with with a*this = 1 mod m.
    • coefficientIterator

      public Iterator<C> coefficientIterator()
      Iterator over coefficients.
      Returns:
      val.values().iterator().
    • wordIterator

      public Iterator<Word> wordIterator()
      Iterator over words.
      Returns:
      val.keySet().iterator().
    • iterator

      public Iterator<WordMonomial<C>> iterator()
      Iterator over monomials.
      Specified by:
      iterator in interface Iterable<C extends RingElem<C>>
      Returns:
      a PolyIterator.
    • map

      public GenWordPolynomial<C> map(UnaryFunctor<? super C,C> f)
      Map a unary function to the coefficients.
      Parameters:
      f - evaluation functor.
      Returns:
      new polynomial with coefficients f(this(e)).
    • contract

      public GenWordPolynomial<C> contract(GenWordPolynomialRing<C> fac)
      GenWordPolynomial contraction.
      Parameters:
      fac - GenWordPolynomialRing.
      Returns:
      this contracted to fac ring, if this in fac ring, null else.