Class MultivariatePolynomial<E>

• Field Detail

• ring

public final Ring<E> ring
The coefficient ring
• Method Detail

• create

public static <E> MultivariatePolynomial<E> create​(int nVariables,
Ring<E> ring,
Comparator<DegreeVector> ordering,
Iterable<Monomial<E>> terms)
Creates multivariate polynomial from a list of monomial terms
Parameters:
ring - the ring
ordering - term ordering
terms - the monomial terms
Returns:
multivariate polynomial
• create

public static <E> MultivariatePolynomial<E> create​(int nVariables,
Ring<E> ring,
Comparator<DegreeVector> ordering,
Monomial<E>... terms)
Creates multivariate polynomial from a list of monomial terms
Parameters:
ring - the ring
ordering - term ordering
terms - the monomial terms
Returns:
multivariate polynomial
• zero

public static <E> MultivariatePolynomial<E> zero​(int nVariables,
Ring<E> ring,
Comparator<DegreeVector> ordering)
Creates zero polynomial.
Parameters:
nVariables - number of variables
ring - the ring
ordering - the ordering
Returns:
zero polynomial
• one

public static <E> MultivariatePolynomial<E> one​(int nVariables,
Ring<E> ring,
Comparator<DegreeVector> ordering)
Creates unit polynomial.
Parameters:
nVariables - number of variables
ring - the ring
ordering - the ordering
Returns:
unit polynomial
• parse

public static MultivariatePolynomial<BigInteger> parse​(String string,
String... variables)
Parse multivariate Z[X] polynomial from string.
Parameters:
string - the string
variables - string variables that should be taken into account. For examples: parse("a", LEX) and parse("a", LEX, "a", "b") although give the same mathematical expressions are differ, since the first one is considered as Z[x], while the second as Z[x1,x2]
Returns:
multivariate Z[X] polynomial
• parse

@Deprecated
public static MultivariatePolynomial<BigInteger> parse​(String string)
Deprecated.
use #parse(string, ring, ordering, variables)
Parse multivariate Z[X] polynomial from string.
Parameters:
string - the string
Returns:
multivariate Z[X] polynomial
• parse

public static <E> MultivariatePolynomial<E> parse​(String string,
Ring<E> ring,
String... variables)
Parse multivariate polynomial from string.
Parameters:
string - the string
ring - the ring
variables - string variables that should be taken into account. For examples: parse("a", LEX) and parse("a", LEX, "a", "b") although give the same mathematical expressions are differ, since the first one is considered as Z[x], while the second as Z[x1,x2]
Returns:
multivariate polynomial
• parse

@Deprecated
public static <E> MultivariatePolynomial<E> parse​(String string,
Ring<E> ring)
Deprecated.
use #parse(string, ring, ordering, variables)
Parse multivariate polynomial from string.
Parameters:
string - the string
ring - the ring
Returns:
multivariate polynomial
• parse

public static MultivariatePolynomial<BigInteger> parse​(String string,
Comparator<DegreeVector> ordering,
String... variables)
Parse multivariate Z[X] polynomial from string.
Parameters:
string - the string
ordering - monomial order
variables - string variables that should be taken into account. For examples: parse("a", LEX) and parse("a", LEX, "a", "b") although give the same mathematical expressions are differ, since the first one is considered as Z[x], while the second as Z[x1,x2]
Returns:
Z[X] multivariate polynomial
• parse

public static <E> MultivariatePolynomial<E> parse​(String string,
Ring<E> ring,
Comparator<DegreeVector> ordering,
String... variables)
Parse multivariate polynomial from string.
Parameters:
string - the string
ring - the ring
ordering - monomial order
variables - string variables that should be taken into account. For examples: parse("a", LEX) and parse("a", LEX, "a", "b") although give the same mathematical expressions are different, since the first one is considered as Z[a], while the second as Z[a,b]
Returns:
multivariate polynomial
• parse

@Deprecated
public static <E> MultivariatePolynomial<E> parse​(String string,
Ring<E> ring,
Comparator<DegreeVector> ordering)
Deprecated.
use #parse(string, ring, ordering, variables)
Parse multivariate polynomial from string.
Parameters:
string - the string
ring - the ring
ordering - monomial order
• asMultivariate

public static <E> MultivariatePolynomial<E> asMultivariate​(UnivariatePolynomial<E> poly,
int nVariables,
int variable,
Comparator<DegreeVector> ordering)
Converts univariate polynomial to multivariate.
Parameters:
poly - univariate polynomial
nVariables - number of variables in the result
variable - variable that will be used as a primary variable
ordering - monomial order
Returns:
multivariate polynomial
• asNormalMultivariate

public static <E> MultivariatePolynomial<E> asNormalMultivariate​(MultivariatePolynomial<UnivariatePolynomial<E>> poly,
int variable)
Converts multivariate polynomial over univariate polynomial ring (R[variable][other_variables]) to a multivariate polynomial over coefficient ring (R[variables])
Parameters:
poly - the polynomial
variable - the variable to insert
Returns:
multivariate polynomial over normal coefficient ring
• asNormalMultivariate

public static <E> MultivariatePolynomial<E> asNormalMultivariate​(MultivariatePolynomial<MultivariatePolynomial<E>> poly)
Converts multivariate polynomial over multivariate polynomial ring to a multivariate polynomial over coefficient ring
Parameters:
poly - the polynomial
Returns:
multivariate polynomial over normal coefficient ring
• asNormalMultivariate

public static <E> MultivariatePolynomial<E> asNormalMultivariate​(MultivariatePolynomial<MultivariatePolynomial<E>> poly,
int[] coefficientVariables,
int[] mainVariables)
Converts multivariate polynomial over multivariate polynomial ring to a multivariate polynomial over coefficient ring
Parameters:
poly - the polynomial
Returns:
multivariate polynomial over normal coefficient ring
• asPolyZSymmetric

public static MultivariatePolynomial<BigInteger> asPolyZSymmetric​(MultivariatePolynomial<BigInteger> poly)
Converts Zp[x] polynomial to Z[x] polynomial formed from the coefficients of this represented in symmetric modular form (-modulus/2 <= cfx <= modulus/2).
Parameters:
poly - Zp polynomial
Returns:
Z[x] version of the poly with coefficients represented in symmetric modular form (-modulus/2 <= cfx <= modulus/2).
Throws:
IllegalArgumentException - is poly.ring is not a IntegersZp
• contentAsPoly

public MultivariatePolynomial<E> contentAsPoly()
Description copied from interface: IPolynomial
Returns the content of this (gcd of coefficients) as a constant poly
• isOverField

public boolean isOverField()
Description copied from interface: IPolynomial
Returns whether the coefficient ring of this polynomial is a field
Returns:
whether the coefficient ring of this polynomial is a field
• isOverFiniteField

public boolean isOverFiniteField()
Description copied from interface: IPolynomial
Returns whether the coefficient ring of this polynomial is a finite field
Returns:
whether the coefficient ring of this polynomial is a finite field
• isOverZ

public boolean isOverZ()
Description copied from interface: IPolynomial
Returns whether the coefficient ring of this polynomial is Z
Returns:
whether the coefficient ring of this polynomial is Z
• coefficientRingCardinality

public BigInteger coefficientRingCardinality()
Description copied from interface: IPolynomial
Returns cardinality of the coefficient ring of this poly
Returns:
cardinality of the coefficient ring
• coefficientRingCharacteristic

public BigInteger coefficientRingCharacteristic()
Description copied from interface: IPolynomial
Returns characteristic of the coefficient ring of this poly
Returns:
characteristic of the coefficient ring
• isOverPerfectPower

public boolean isOverPerfectPower()
Description copied from interface: IPolynomial
Returns whether the coefficientRingCardinality() is a perfect power
Returns:
whether the coefficientRingCardinality() is a perfect power
• coefficientRingPerfectPowerBase

public BigInteger coefficientRingPerfectPowerBase()
Description copied from interface: IPolynomial
Returns base so that coefficientRingCardinality() == base^exponent or null if cardinality is not finite
Returns:
base so that coefficientRingCardinality() == base^exponent or null if cardinality is not finite
• coefficientRingPerfectPowerExponent

public BigInteger coefficientRingPerfectPowerExponent()
Description copied from interface: IPolynomial
Returns exponent so that coefficientRingCardinality() == base^exponent or null if cardinality is not finite
Returns:
exponent so that coefficientRingCardinality() == base^exponent or null if cardinality is not finite
• createArray2d

public MultivariatePolynomial<E>[][] createArray2d​(int length1,
int length2)
Description copied from interface: IPolynomial
overcome Java generics...
• sameCoefficientRingWith

public boolean sameCoefficientRingWith​(MultivariatePolynomial<E> oth)
Description copied from interface: IPolynomial
Returns whether oth and this have the same coefficient ring
Parameters:
oth - other polynomial
Returns:
whether this and oth are over the same coefficient ring
• setCoefficientRingFrom

public MultivariatePolynomial<E> setCoefficientRingFrom​(MultivariatePolynomial<E> poly)
Description copied from interface: IPolynomial
Set the coefficient ring from specified poly
Parameters:
poly - the polynomial
Returns:
a copy of this with the coefficient ring taken from poly
• setRing

public MultivariatePolynomial<E> setRing​(Ring<E> newRing)
Returns a copy of this with coefficient reduced to a newRing
Parameters:
newRing - the new ring
Returns:
a copy of this reduced to the ring specified by newRing
• createConstant

public MultivariatePolynomial<E> createConstant​(E val)
Creates constant polynomial with specified value
Parameters:
val - value
Returns:
constant polynomial with specified value
• createZero

public MultivariatePolynomial<E> createZero()
Description copied from interface: IPolynomial
Returns the new instance of zero polynomial (with the same coefficient ring)
Returns:
new instance of 0
• createOne

public MultivariatePolynomial<E> createOne()
Description copied from interface: IPolynomial
Returns the new instance of unit polynomial (with the same coefficient ring)
Returns:
new instance of 1
• createLinear

public final MultivariatePolynomial<E> createLinear​(int variable,
E cc,
E lc)
Creates linear polynomial of the form cc + lc * variable
Parameters:
variable - the variable
cc - the constant coefficient
lc - the leading coefficient
Returns:
linear polynomial cc + lc * variable
• isMonic

public boolean isMonic()
Description copied from interface: IPolynomial
Returns true if this polynomial is monic
Returns:
whether this is monic
• signumOfLC

public int signumOfLC()
Description copied from interface: IPolynomial
Gives signum of the leading coefficient
Returns:
signum of the leading coefficient
• isOne

public boolean isOne()
Description copied from interface: IPolynomial
Returns true if this is one
Returns:
whether this is one
• isUnitCC

public boolean isUnitCC()
Description copied from interface: IPolynomial
Returns true if constant term is equal to one
Returns:
whether constant term is 1
• isConstant

public boolean isConstant()
Description copied from interface: IPolynomial
Returns true if this polynomial has only constant term
Returns:
whether this is constant
• maxAbsCoefficient

public E maxAbsCoefficient()
Returns max absolute coefficient
• lc

public E lc()
Returns the leading coefficient of this polynomial that is coefficient of the largest term according to the ordering.
Returns:
leading coefficient of this polynomial
• lc

public E lc​(Comparator<DegreeVector> ordering)
Returns the leading coefficient of this polynomial with respect to specified ordering
Returns:
leading coefficient of this polynomial with respect to specified ordering
• setLC

public MultivariatePolynomial<E> setLC​(E val)
Sets the leading coefficient to the specified value
Parameters:
val - new value for the lc
Returns:
the leading coefficient to the specified value
• cc

public E cc()
Returns the constant coefficient of this polynomial.
Returns:
constant coefficient of this polynomial
• content

public E content()
Returns the content of this polynomial.
Returns:
content of this polynomial
• coefficients

public Iterable<E> coefficients()
Returns iterable over polynomial coefficients
Returns:
iterable over polynomial coefficients
• coefficientsArray

public E[] coefficientsArray()
Returns array of polynomial coefficients
Returns:
array of polynomial coefficients
• primitivePart

public MultivariatePolynomial<E> primitivePart()
Description copied from interface: IPolynomial
Reduces poly to its primitive part (primitive part will always have positive l.c.)
Returns:
primitive part (poly will be modified)
• primitivePartSameSign

public MultivariatePolynomial<E> primitivePartSameSign()
Description copied from interface: IPolynomial
Reduces poly to its primitive part, so that primitive part will have the same signum as the initial poly
Returns:
primitive part (poly will be modified)
• divideByLC

public MultivariatePolynomial<E> divideByLC​(MultivariatePolynomial<E> other)
Description copied from interface: IPolynomial
Divides this polynomial by the leading coefficient of other or returns null (causing loss of internal data) if some of the elements can't be exactly divided by the other.lc(). NOTE: if null is returned, the content of this is destroyed.
Parameters:
other - the polynomial
Returns:
this divided by the other.lc() or null if exact division is not possible
• divideOrNull

public MultivariatePolynomial<E> divideOrNull​(E factor)
Divides this polynomial by a factor or returns null (causing loss of internal data) if some of the elements can't be exactly divided by the factor. NOTE: if null is returned, the content of this is destroyed.
Parameters:
factor - the factor
Returns:
this divided by the factor or null
• divideExact

public MultivariatePolynomial<E> divideExact​(E factor)
Divides this polynomial by a factor or throws exception if exact division is not possible
Parameters:
factor - the factor
Returns:
this divided by the factor
Throws:
ArithmeticException - if exact division is not possible
• monic

public MultivariatePolynomial<E> monic()
Makes this polynomial monic if possible, if not -- destroys this and returns null
Returns:
monic this or null if the ring does not support exact division by lc
• monic

public MultivariatePolynomial<E> monic​(E factor)
Sets this to its monic part multiplied by the factor modulo modulus (that is monic(modulus).multiply(factor) ).
Parameters:
factor - the factor
Returns:
this
• monicWithLC

public MultivariatePolynomial<E> monicWithLC​(MultivariatePolynomial<E> other)
Description copied from interface: IPolynomial
Sets this to its monic part multiplied by the leading coefficient of other;
Parameters:
other - other polynomial
Returns:
monic part multiplied by the leading coefficient of other or null if exact division by the reduced leading coefficient is not possible
• toDenseRecursiveForm

public UnivariatePolynomial toDenseRecursiveForm()
Gives a recursive univariate representation of this poly.
• fromDenseRecursiveForm

public static <E> MultivariatePolynomial<E> fromDenseRecursiveForm​(UnivariatePolynomial recForm,
int nVariables,
Comparator<DegreeVector> ordering)
Converts poly from a recursive univariate representation.
Parameters:
recForm - recursive univariate representation
nVariables - number of variables in multivariate polynomial
ordering - monomial order
• evaluateDenseRecursiveForm

public static <E> E evaluateDenseRecursiveForm​(UnivariatePolynomial recForm,
int nVariables,
E[] values)
Evaluates polynomial given in a dense recursive form at a given points
• toSparseRecursiveForm

public AMultivariatePolynomial toSparseRecursiveForm()
Gives a recursive sparse univariate representation of this poly.
• fromSparseRecursiveForm

public static <E> MultivariatePolynomial<E> fromSparseRecursiveForm​(AMultivariatePolynomial recForm,
int nVariables,
Comparator<DegreeVector> ordering)
Converts poly from a recursive univariate representation.
Parameters:
recForm - recursive univariate representation
nVariables - number of variables in multivariate polynomial
ordering - monomial order
• evaluateSparseRecursiveForm

public static <E> E evaluateSparseRecursiveForm​(AMultivariatePolynomial recForm,
int nVariables,
E[] values)
Evaluates polynomial given in a sparse recursive form at a given points
• getHornerForm

public MultivariatePolynomial.HornerForm getHornerForm​(int[] evaluationVariables)
Gives data structure for fast Horner-like sparse evaluation of this multivariate polynomial
Parameters:
evaluationVariables - variables which will be substituted
• evaluate

public E evaluate​(E... values)
Evaluates this polynomial at specified points
• evaluate

public MultivariatePolynomial<E>[] evaluate​(int variable,
E... values)
Evaluates this polynomial at specified points
• eliminate

public MultivariatePolynomial<E> eliminate​(int variable,
E value)
Substitutes value for variable and eliminates variable from the list of variables so that the resulting polynomial has result.nVariables = this.nVariables - 1.
Parameters:
variable - the variable
value - the value
Returns:
a new multivariate polynomial with value substituted for variable and nVariables = nVariables - 1)
evaluate(int, Object)
• eliminate

public MultivariatePolynomial<E> eliminate​(int variable,
long value)
Substitutes value for variable and eliminates variable from the list of variables so that the resulting polynomial has result.nVariables = this.nVariables - 1.
Parameters:
variable - the variable
value - the value
Returns:
a new multivariate polynomial with value substituted for variable and nVariables = nVariables - 1)
evaluate(int, long)
• eliminate

public MultivariatePolynomial<E> eliminate​(int[] variables,
E[] values)
Returns a copy of this with values substituted for variables
Parameters:
variables - the variables
values - the values
Returns:
a new multivariate polynomial with value substituted for variable but still with the same AMultivariatePolynomial.nVariables (though the effective number of variables is nVariables - 1, compare to eliminate(int, long))
• substitute

public MultivariatePolynomial<E> substitute​(int variable,
MultivariatePolynomial<E> poly)
Returns a copy of this with poly substituted for variable.
Parameters:
variable - the variable
poly - the replacement for the variable
Returns:
a copy of this with variable -> poly
• shift

public MultivariatePolynomial<E> shift​(int variable,
long shift)
Returns a copy of this with variable -> variable + shift
Parameters:
variable - the variable
shift - shift amount
Returns:
a copy of this with variable -> variable + shift
• shift

public MultivariatePolynomial<E> shift​(int variable,
E shift)
Returns a copy of this with variable -> variable + shift
Parameters:
variable - the variable
shift - shift amount
Returns:
a copy of this with variable -> variable + shift
• shift

public MultivariatePolynomial<E> shift​(int[] variables,
E[] shifts)
Returns a copy of this with variables -> variables + shifts
Parameters:
variables - the variables
shifts - the corresponding shifts
Returns:
a copy of this with variables -> variables + shifts

public MultivariatePolynomial<E> add​(E oth)
Adds oth to this polynomial
Parameters:
oth - other polynomial
Returns:
this + oth
• subtract

public MultivariatePolynomial<E> subtract​(E oth)
Subtracts oth from this polynomial
Parameters:
oth - other polynomial
Returns:
this - oth
• multiply

public MultivariatePolynomial<E> multiply​(E factor)
Multiplies this by the factor
Parameters:
factor - the factor
Returns:
this multiplied by the factor
• multiply

public MultivariatePolynomial<E> multiply​(long factor)
Description copied from interface: IPolynomial
Multiplies this by factor
Parameters:
factor - the factor
Returns:
this * factor
• multiplyByBigInteger

public MultivariatePolynomial<E> multiplyByBigInteger​(BigInteger factor)
Description copied from interface: IPolynomial
Multiplies this by factor
Parameters:
factor - the factor
Returns:
this * factor
• seriesCoefficient

public MultivariatePolynomial<E> seriesCoefficient​(int variable,
int order)
Description copied from class: AMultivariatePolynomial
Gives (unevaluated) coefficient of Taylor series expansion for specified variable that is derivative(poly, variable, order) / order! , where the derivative is formal derivative and calculated with arithmetic performed in Z ring (to overcome possible zeros in Zp).
Specified by:
seriesCoefficient in class AMultivariatePolynomial<Monomial<E>,​MultivariatePolynomial<E>>
Parameters:
variable - the variable
order - derivative order
Returns:
derivative(poly, variable, order) / order! , where the derivative is formal derivative and calculated with arithmetic performed in Z ring (to overcome possible zeros in Zp)
• stream

public Stream<E> stream()
Returns a stream of coefficients of this
Returns:
stream of coefficients
• mapTerms

public <T> MultivariatePolynomial<T> mapTerms​(Ring<T> newRing,
Function<Monomial<E>,​Monomial<T>> mapper)
Maps terms of this using specified mapping function
Type Parameters:
T - new element type
Parameters:
newRing - the new ring
mapper - mapping
Returns:
a new polynomial with terms obtained by applying mapper to this terms
• mapCoefficients

public <T> MultivariatePolynomial<T> mapCoefficients​(Ring<T> newRing,
Function<E,​T> mapper)
Maps coefficients of this using specified mapping function
Type Parameters:
T - new element type
Parameters:
newRing - the new ring
mapper - mapping
Returns:
a new polynomial with terms obtained by applying mapper to this terms (only coefficients are changed)
• mapCoefficients

public MultivariatePolynomialZp64 mapCoefficients​(IntegersZp64 newDomain,
ToLongFunction<E> mapper)
Maps coefficients of this using specified mapping function
Parameters:
newDomain - the new ring
mapper - mapping
Returns:
a new polynomial with terms obtained by applying mapper to this terms (only coefficients are changed)