Package edu.jas.poly

Class GenPolynomial<C extends RingElem<C>>

  • Type Parameters:
    C - coefficient type
    All Implemented Interfaces:
    AbelianGroupElem<GenPolynomial<C>>, Element<GenPolynomial<C>>, MonoidElem<GenPolynomial<C>>, RingElem<GenPolynomial<C>>, java.io.Serializable, java.lang.Comparable<GenPolynomial<C>>, java.lang.Iterable<Monomial<C>>
    Direct Known Subclasses:
    GenSolvablePolynomial

    public class GenPolynomial<C extends RingElem<C>>
    extends java.lang.Object
    implements RingElem<GenPolynomial<C>>, java.lang.Iterable<Monomial<C>>
    GenPolynomial generic polynomials implementing RingElem. n-variate ordered polynomials over coefficients C. The variables commute with each other and with the coefficients. For non-commutative coefficients some care is taken to respect the multiplication order. Objects of this class are intended to be immutable. The implementation is based on TreeMap respectively SortedMap from exponents to coefficients. Only the coefficients are modeled with generic types, the exponents are fixed to ExpVector with long entries (@see edu.jas.poly.ExpVector StorUnit). 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. Note: multiply() now checks for wrong method dispatch for GenSolvablePolynomial.
    Author:
    Heinz Kredel
    See Also:
    Serialized Form
    • Field Detail

      • val

        protected final java.util.SortedMap<ExpVector,​C extends RingElem<C>> val
        The data structure for polynomials.
      • hash

        protected transient int hash
        Stored hash code.
      • blen

        protected transient long blen
        Stored bitLength.
    • Method Detail

      • length

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

        public java.util.SortedMap<ExpVector,​CgetMap()
        ExpVector to coefficient map of GenPolynomial.
        Returns:
        val as unmodifiable SortedMap.
      • doPutToMap

        public void doPutToMap​(ExpVector e,
                               C c)
        Put an ExpVector to coefficient entry into the internal map of this GenPolynomial. 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:
        c - coefficient.
        e - exponent.
      • doRemoveFromMap

        public void doRemoveFromMap​(ExpVector e,
                                    C c)
        Remove an ExpVector to coefficient entry from the internal map of this GenPolynomial. 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 - exponent.
        c - expected coefficient, null for ignore.
      • doPutToMap

        public void doPutToMap​(java.util.SortedMap<ExpVector,​C> vals)
        Put an a sorted map of exponents to coefficients into the internal map of this GenPolynomial. 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 exponents and coefficients.
      • toString

        public java.lang.String toString()
        String representation of GenPolynomial.
        Overrides:
        toString in class java.lang.Object
        See Also:
        Object.toString()
      • toString

        public java.lang.String toString​(java.lang.String[] v)
        String representation of GenPolynomial.
        Parameters:
        v - names for variables.
        See Also:
        Object.toString()
      • toScript

        public java.lang.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:
        Element.toScript()
      • isConstant

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

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

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

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

        public int numberOfVariables()
        Number of variables.
        Returns:
        ring.nvar.
      • trailingBaseCoefficient

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

        public C coefficient​(ExpVector e)
        Coefficient.
        Parameters:
        e - exponent.
        Returns:
        coefficient for given exponent.
      • degree

        public long degree​(int i)
        Degree in variable i.
        Returns:
        maximal degree in the variable i.
      • degree

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

        public long degreeMin()
        Minimal degree. Author: Youssef Elbarbary
        Returns:
        minimal degree in any variables.
      • totalDegree

        public long totalDegree()
        Total degree.
        Returns:
        total degree in any variables.
      • weightDegree

        public long weightDegree()
        Weight degree.
        Returns:
        weight degree in all variables.
      • isWeightHomogeneous

        public boolean isWeightHomogeneous()
        Is GenPolynomial<C> homogeneous with respect to a weight.
        Returns:
        true, if this is weight homogeneous, else false.
      • degreeVector

        public ExpVector degreeVector()
        Maximal degree vector.
        Returns:
        maximal degree vector of all variables.
      • deltaExpVectors

        public java.util.List<ExpVectordeltaExpVectors()
        Delta of exponent vectors.
        Returns:
        list of u-v, where u = lt() and v != u in this.
      • deltaExpVectors

        public java.util.List<ExpVectordeltaExpVectors​(ExpVector u)
        Delta of exponent vectors.
        Parameters:
        u - marked ExpVector in this.expVectors
        Returns:
        list of u-v, where v != u in this.expVectors.
      • maxNorm

        public C maxNorm()
        GenPolynomial maximum norm.
        Returns:
        ||this|| the maximum of all absolute values of coefficients.
      • sumNorm

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

        public C squareNorm()
        GenPolynomial square norm.
        Returns:
        the sum all squared values of coefficients.
      • sum

        public GenPolynomial<Csum​(C a,
                                    ExpVector e)
        GenPolynomial addition. This method is not very efficient, since this is copied.
        Parameters:
        a - coefficient.
        e - exponent.
        Returns:
        this + a xe.
      • sum

        public GenPolynomial<Csum​(Monomial<C> m)
        GenPolynomial addition. This method is not very efficient, since this is copied.
        Parameters:
        m - monomial.
        Returns:
        this + m.
      • sum

        public GenPolynomial<Csum​(C a)
        GenPolynomial addition. This method is not very efficient, since this is copied.
        Parameters:
        a - coefficient.
        Returns:
        this + a x0.
      • doAddTo

        public void doAddTo​(GenPolynomial<C> S)
        GenPolynomial destructive summation.
        Parameters:
        S - GenPolynomial.
      • doAddTo

        public void doAddTo​(C a,
                            ExpVector e)
        GenPolynomial destructive summation.
        Parameters:
        a - coefficient.
        e - exponent.
      • doAddTo

        public void doAddTo​(C a)
        GenPolynomial destructive summation.
        Parameters:
        a - coefficient.
      • subtract

        public GenPolynomial<Csubtract​(C a,
                                         ExpVector e)
        GenPolynomial subtraction. This method is not very efficient, since this is copied.
        Parameters:
        a - coefficient.
        e - exponent.
        Returns:
        this - a xe.
      • subtract

        public GenPolynomial<Csubtract​(Monomial<C> m)
        GenPolynomial subtraction. This method is not very efficient, since this is copied.
        Parameters:
        m - monomial.
        Returns:
        this - m.
      • subtract

        public GenPolynomial<Csubtract​(C a)
        GenPolynomial subtract. This method is not very efficient, since this is copied.
        Parameters:
        a - coefficient.
        Returns:
        this + a x0.
      • negateAlt

        public GenPolynomial<CnegateAlt()
        GenPolynomial negation, alternative implementation.
        Returns:
        -this.
      • multiply

        public GenPolynomial<Cmultiply​(C s)
        GenPolynomial multiplication. Product with coefficient ring element.
        Parameters:
        s - coefficient.
        Returns:
        this*s.
      • multiplyLeft

        public GenPolynomial<CmultiplyLeft​(C s)
        GenPolynomial left multiplication. Left product with coefficient ring element.
        Parameters:
        s - coefficient.
        Returns:
        s*this.
      • monic

        public GenPolynomial<Cmonic()
        GenPolynomial monic, i.e. leadingCoefficient == 1. If leadingCoefficient is not invertible returns this unmodified.
        Returns:
        monic(this).
      • monicRight

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

        public GenPolynomial<Cmultiply​(C s,
                                         ExpVector e)
        GenPolynomial multiplication. Product with ring element and exponent vector.
        Parameters:
        s - coefficient.
        e - exponent.
        Returns:
        this * s xe.
      • multiply

        public GenPolynomial<Cmultiply​(ExpVector e)
        GenPolynomial multiplication. Product with exponent vector.
        Parameters:
        e - exponent (!= null).
        Returns:
        this * xe.
      • multiply

        public GenPolynomial<Cmultiply​(java.util.Map.Entry<ExpVector,​C> m)
        GenPolynomial multiplication. Product with 'monomial'.
        Parameters:
        m - 'monomial'.
        Returns:
        this * m.
      • divide

        public GenPolynomial<Cdivide​(C s)
        GenPolynomial division. Division by coefficient ring element. Fails, if exact division is not possible.
        Parameters:
        s - coefficient.
        Returns:
        s**(-1) * this.
      • rightDivideCoeff

        public GenPolynomial<CrightDivideCoeff​(C s)
        GenPolynomial right division. Right division by coefficient ring element. Fails, if exact division is not possible.
        Parameters:
        s - coefficient.
        Returns:
        this * s**(-1).
      • leftDivideCoeff

        public GenPolynomial<CleftDivideCoeff​(C s)
        GenPolynomial left division. Left division by coefficient ring element. Fails, if exact division is not possible.
        Parameters:
        s - coefficient.
        Returns:
        s**(-1) * this.
      • coeffPrimitivePart

        public GenPolynomial<CcoeffPrimitivePart()
        GenPolynomial coefficient primitive part. Division by gcd of coefficients.
        Returns:
        this/gcd(coeff(this)).
      • gcd

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

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

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

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

        public GenPolynomial<Cextend​(GenPolynomialRing<C> pfac,
                                       int j,
                                       long k)
        Extend variables. Used e.g. in module embedding. Extend all ExpVectors by i elements and multiply by x_j^k.
        Parameters:
        pfac - extended polynomial ring factory (by i variables).
        j - index of variable to be used for multiplication.
        k - exponent for x_j.
        Returns:
        extended polynomial.
      • extendLower

        public GenPolynomial<CextendLower​(GenPolynomialRing<C> pfac,
                                            int j,
                                            long k)
        Extend lower variables. Used e.g. in module embedding. Extend all ExpVectors by i lower elements and multiply by x_j^k.
        Parameters:
        pfac - extended polynomial ring factory (by i variables).
        j - index of variable to be used for multiplication.
        k - exponent for x_j.
        Returns:
        extended polynomial.
      • contract

        public java.util.Map<ExpVector,​GenPolynomial<C>> contract​(GenPolynomialRing<C> pfac)
        Contract variables. Used e.g. in module embedding. Remove i elements of each ExpVector.
        Parameters:
        pfac - contracted polynomial ring factory (by i variables).
        Returns:
        Map of exponents and contracted polynomials. Note: could return SortedMap
      • contractCoeff

        public GenPolynomial<CcontractCoeff​(GenPolynomialRing<C> pfac)
        Contract variables to coefficient polynomial. Remove i elements of each ExpVector, removed elements must be zero.
        Parameters:
        pfac - contracted polynomial ring factory (by i variables).
        Returns:
        contracted coefficient polynomial.
      • extendUnivariate

        public GenPolynomial<CextendUnivariate​(GenPolynomialRing<C> pfac,
                                                 int i)
        Extend univariate to multivariate polynomial. This is an univariate polynomial in variable i of the polynomial ring, it is extended to the given polynomial ring.
        Parameters:
        pfac - extended polynomial ring factory.
        i - index of the variable of this polynomial in pfac.
        Returns:
        extended multivariate polynomial.
      • inflate

        public GenPolynomial<Cinflate​(long e)
        GenPolynomial inflate. Only for univariate polynomials over fields.
        Parameters:
        e - exponent.
        Returns:
        this(x**e)
      • coefficientIterator

        public java.util.Iterator<CcoefficientIterator()
        Iterator over coefficients.
        Returns:
        val.values().iterator().
      • exponentIterator

        public java.util.Iterator<ExpVectorexponentIterator()
        Iterator over exponents.
        Returns:
        val.keySet().iterator().
      • iterator

        public java.util.Iterator<Monomial<C>> iterator()
        Iterator over monomials.
        Specified by:
        iterator in interface java.lang.Iterable<C extends RingElem<C>>
        Returns:
        a PolyIterator.
      • spliterator

        public java.util.Spliterator<Monomial<C>> spliterator()
        Spliterator over monomials.
        Specified by:
        spliterator in interface java.lang.Iterable<C extends RingElem<C>>
        Returns:
        a PolySpliterator.
      • map

        public GenPolynomial<Cmap​(UnaryFunctor<? super C,​C> f)
        Map a unary function to the coefficients.
        Parameters:
        f - evaluation functor.
        Returns:
        new polynomial with coefficients f(this.coefficients).
      • mapOnStream

        public GenPolynomial<CmapOnStream​(java.util.function.Function<? super java.util.Map.Entry<ExpVector,​C>,​? extends java.util.Map.Entry<ExpVector,​C>> f)
        Map a function to the polynomial stream entries.
        Parameters:
        f - evaluation functor.
        Returns:
        new polynomial with f(this.entries).
      • mapOnStream

        public GenPolynomial<CmapOnStream​(java.util.function.Function<? super java.util.Map.Entry<ExpVector,​C>,​? extends java.util.Map.Entry<ExpVector,​C>> f,
                                            boolean parallel)
        Map a function to the polynomial stream entries.
        Parameters:
        f - evaluation functor.
        Returns:
        new polynomial with f(this.entries).
      • bitLength

        public long bitLength()
        Returns the number of bits in the representation of this polynomial.
        Returns:
        number of bits in the representation of this polynomial, including sign bits.