edu.jas.poly
Class GenPolynomial<C extends RingElem<C>>

java.lang.Object
  edu.jas.poly.GenPolynomial<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.Cloneable, 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 C. 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 (this will eventually be changed in the future). C can also be a non integral domain, e.g. a ModInteger, i.e. it may contain zero divisors, since multiply() does now check for zeros. Note: multiply() now checks for wrong method dispatch for GenSolvablePolynomial.

Author:

Heinz Kredel

See Also:

Serialized Form

Field Summary

GenPolynomialRing<C>	ring The factory for the polynomial ring.
protected java.util.SortedMap<ExpVector,C>	val The data structure for polynomials.

Constructor Summary

	GenPolynomial(GenPolynomialRing<C> r) Constructor for zero GenPolynomial.
	GenPolynomial(GenPolynomialRing<C> r, C c) Constructor for GenPolynomial c * x0.
	GenPolynomial(GenPolynomialRing<C> r, C c, ExpVector e) Constructor for GenPolynomial c * xe.
protected	GenPolynomial(GenPolynomialRing<C> r, java.util.SortedMap<ExpVector,C> v) Constructor for GenPolynomial.

Method Summary

GenPolynomial<C>	abs() GenPolynomial absolute value, i.e. leadingCoefficient > 0.
GenPolynomial<C>	clone() Clone this GenPolynomial.
C	coefficient(ExpVector e) Coefficient.
java.util.Iterator<C>	coefficientIterator() Iterator over coefficients.
int	compareTo(GenPolynomial<C> b) GenPolynomial comparison.
java.util.Map<ExpVector,GenPolynomial<C>>	contract(GenPolynomialRing<C> pfac) Contract variables.
GenPolynomial<C>	contractCoeff(GenPolynomialRing<C> pfac) Contract variables to coefficient polynomial.
long	degree() Maximal degree.
long	degree(int i) Degree in variable i.
ExpVector	degreeVector() Maximal degree vector.
GenPolynomial<C>	divide(C s) GenPolynomial division.
GenPolynomial<C>	divide(GenPolynomial<C> S) GenPolynomial division.
GenPolynomial<C>[]	divideAndRemainder(GenPolynomial<C> S) Deprecated. use quotientRemainder()
void	doPutToMap(ExpVector e, C c) Put an ExpVector to coefficient entry into the internal map of this GenPolynomial.
void	doPutToMap(java.util.SortedMap<ExpVector,C> vals) Put an a sorted map of exponents to coefficients into the internal map of this GenPolynomial.
GenPolynomial<C>[]	egcd(GenPolynomial<C> S) GenPolynomial extended greatest comon divisor.
boolean	equals(java.lang.Object B) Comparison with any other object.
java.util.Iterator<ExpVector>	exponentIterator() Iterator over exponents.
GenPolynomial<C>	extend(GenPolynomialRing<C> pfac, int j, long k) Extend variables.
GenPolynomial<C>	extendLower(GenPolynomialRing<C> pfac, int j, long k) Extend lower variables.
GenPolynomial<C>	extendUnivariate(GenPolynomialRing<C> pfac, int i) Extend univariate to multivariate polynomial.
GenPolynomialRing<C>	factory() Get the corresponding element factory.
GenPolynomial<C>	gcd(GenPolynomial<C> S) GenPolynomial greatest common divisor.
java.util.SortedMap<ExpVector,C>	getMap() ExpVector to coefficient map of GenPolynomial.
int	hashCode() Hash code for this polynomial.
GenPolynomial<C>[]	hegcd(GenPolynomial<C> S) GenPolynomial half extended greatest comon divisor.
GenPolynomial<C>	inverse() GenPolynomial inverse.
boolean	isConstant() Is GenPolynomial<C> a constant.
boolean	isONE() Is GenPolynomial<C> one.
boolean	isUnit() Is GenPolynomial<C> a unit.
boolean	isZERO() Is GenPolynomial<C> zero.
java.util.Iterator<Monomial<C>>	iterator() Iterator over monomials.
C	leadingBaseCoefficient() Leading base coefficient.
ExpVector	leadingExpVector() Leading exponent vector.
java.util.Map.Entry<ExpVector,C>	leadingMonomial() Leading monomial.
int	length() Length of GenPolynomial.
GenPolynomial<C>	map(UnaryFunctor<? super C,C> f) Map a unary function to the coefficients.
C	maxNorm() GenPolynomial maximum norm.
GenPolynomial<C>	modInverse(GenPolynomial<C> m) GenPolynomial modular inverse.
GenPolynomial<C>	monic() GenPolynomial monic, i.e. leadingCoefficient == 1.
GenPolynomial<C>	multiply(C s) GenPolynomial multiplication.
GenPolynomial<C>	multiply(C s, ExpVector e) GenPolynomial multiplication.
GenPolynomial<C>	multiply(ExpVector e) GenPolynomial multiplication.
GenPolynomial<C>	multiply(GenPolynomial<C> S) GenPolynomial multiplication.
GenPolynomial<C>	multiply(java.util.Map.Entry<ExpVector,C> m) GenPolynomial multiplication.
GenPolynomial<C>	negate() GenPolynomial negation.
int	numberOfVariables() Number of variables.
GenPolynomial<C>[]	quotientRemainder(GenPolynomial<C> S) GenPolynomial division with remainder.
GenPolynomial<C>	reductum() Reductum.
GenPolynomial<C>	remainder(GenPolynomial<C> S) GenPolynomial remainder.
GenPolynomial<C>	reverse(GenPolynomialRing<C> oring) Reverse variables.
int	signum() GenPolynomial signum.
GenPolynomial<C>	subtract(C a) GenPolynomial subtract.
GenPolynomial<C>	subtract(C a, ExpVector e) GenPolynomial subtraction.
GenPolynomial<C>	subtract(GenPolynomial<C> S) GenPolynomial subtraction.
GenPolynomial<C>	sum(C a) GenPolynomial addition.
GenPolynomial<C>	sum(C a, ExpVector e) GenPolynomial addition.
GenPolynomial<C>	sum(GenPolynomial<C> S) GenPolynomial summation.
C	sumNorm() GenPolynomial sum norm.
java.lang.String	toScript() Get a scripting compatible string representation.
java.lang.String	toScriptFactory() Get a scripting compatible string representation of the factory.
java.lang.String	toString() String representation of GenPolynomial.
java.lang.String	toString(java.lang.String[] v) String representation of GenPolynomial.
C	trailingBaseCoefficient() Trailing base coefficient.
ExpVector	trailingExpVector() Trailing exponent vector.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

ring

public final GenPolynomialRing<C extends RingElem<C>> ring

The factory for the polynomial ring.

val

protected final java.util.SortedMap<ExpVector,C extends RingElem<C>> val

The data structure for polynomials.

Constructor Detail

GenPolynomial

public GenPolynomial(GenPolynomialRing<C> r)

Constructor for zero GenPolynomial.

Parameters:

r - polynomial ring factory.

GenPolynomial

public GenPolynomial(GenPolynomialRing<C> r,
                     C c,
                     ExpVector e)

Constructor for GenPolynomial c * x^e.

Parameters:

r - polynomial ring factory.

c - coefficient.

e - exponent.

GenPolynomial

public GenPolynomial(GenPolynomialRing<C> r,
                     C c)

Constructor for GenPolynomial c * x⁰.

Parameters:

r - polynomial ring factory.

c - coefficient.

GenPolynomial

protected GenPolynomial(GenPolynomialRing<C> r,
                        java.util.SortedMap<ExpVector,C> v)

Constructor for GenPolynomial.

Parameters:

r - polynomial ring factory.

v - the SortedMap of some other polynomial.

Method Detail

factory

public GenPolynomialRing<C> factory()

Get the corresponding element factory.

Specified by:

factory in interface Element<GenPolynomial<C extends RingElem<C>>>

Returns:

factory for this Element.

See Also:

Element.factory()

clone

public GenPolynomial<C> clone()

Clone this GenPolynomial.

Overrides:

clone in class java.lang.Object

See Also:

Object.clone()

length

public int length()

Length of GenPolynomial.

Returns:

number of coefficients of this GenPolynomial.

getMap

public java.util.SortedMap<ExpVector,C> getMap()

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.

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<GenPolynomial<C extends RingElem<C>>>

Returns:

script compatible representation for this Element.

See Also:

Element.toScript()

toScriptFactory

public java.lang.String toScriptFactory()

Get a scripting compatible string representation of the factory.

Specified by:

toScriptFactory in interface Element<GenPolynomial<C extends RingElem<C>>>

Returns:

script compatible representation for this ElemFactory.

See Also:

Element.toScriptFactory()

isZERO

public boolean isZERO()

Is GenPolynomial<C> zero.

Specified by:

isZERO in interface AbelianGroupElem<GenPolynomial<C extends RingElem<C>>>

Returns:

If this is 0 then true is returned, else false.

See Also:

AbelianGroupElem.isZERO()

isONE

public boolean isONE()

Is GenPolynomial<C> one.

Specified by:

isONE in interface MonoidElem<GenPolynomial<C extends RingElem<C>>>

Returns:

If this is 1 then true is returned, else false.

See Also:

MonoidElem.isONE()

isUnit

public boolean isUnit()

Is GenPolynomial<C> a unit.

Specified by:

isUnit in interface MonoidElem<GenPolynomial<C extends RingElem<C>>>

Returns:

If this is a unit then true is returned, else false.

See Also:

MonoidElem.isUnit()

isConstant

public boolean isConstant()

Is GenPolynomial<C> a constant.

Returns:

If this is a constant polynomial then true is returned, else false.

equals

public boolean equals(java.lang.Object B)

Comparison with any other object.

Specified by:

equals in interface Element<GenPolynomial<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<GenPolynomial<C extends RingElem<C>>>

Overrides:

hashCode in class java.lang.Object

Returns:

the hashCode.

See Also:

Object.hashCode()

compareTo

public int compareTo(GenPolynomial<C> b)

GenPolynomial comparison.

Specified by:

compareTo in interface Element<GenPolynomial<C extends RingElem<C>>>

Specified by:

compareTo in interface java.lang.Comparable<GenPolynomial<C extends RingElem<C>>>

Parameters:

b - GenPolynomial.

Returns:

sign(this-b).

signum

public int signum()

GenPolynomial signum.

Specified by:

signum in interface AbelianGroupElem<GenPolynomial<C extends RingElem<C>>>

Returns:

sign(ldcf(this)).

numberOfVariables

public int numberOfVariables()

Number of variables.

Returns:

ring.nvar.

leadingMonomial

public java.util.Map.Entry<ExpVector,C> leadingMonomial()

Leading monomial.

Returns:

first map entry.

leadingExpVector

public ExpVector leadingExpVector()

Leading exponent vector.

Returns:

first exponent.

trailingExpVector

public ExpVector trailingExpVector()

Trailing exponent vector.

Returns:

last exponent.

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(ExpVector e)

Coefficient.

Parameters:

e - exponent.

Returns:

coefficient for given exponent.

reductum

public GenPolynomial<C> reductum()

Reductum.

Returns:

this - leading monomial.

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.

degreeVector

public ExpVector degreeVector()

Maximal degree vector.

Returns:

maximal degree vector of all variables.

maxNorm

public C maxNorm()

GenPolynomial maximum norm.

Returns:

||this||.

sumNorm

public C sumNorm()

GenPolynomial sum norm.

Returns:

sum of all absolute values of coefficients.

sum

public GenPolynomial<C> sum(GenPolynomial<C> S)

GenPolynomial summation.

Specified by:

sum in interface AbelianGroupElem<GenPolynomial<C extends RingElem<C>>>

Parameters:

S - GenPolynomial.

Returns:

this+S.

sum

public GenPolynomial<C> sum(C a,
                            ExpVector e)

GenPolynomial addition. This method is not very efficient, since this is copied.

Parameters:

a - coefficient.

e - exponent.

Returns:

this + a x^e.

sum

public GenPolynomial<C> sum(C a)

GenPolynomial addition. This method is not very efficient, since this is copied.

Parameters:

a - coefficient.

Returns:

this + a x⁰.

subtract

public GenPolynomial<C> subtract(GenPolynomial<C> S)

GenPolynomial subtraction.

Specified by:

subtract in interface AbelianGroupElem<GenPolynomial<C extends RingElem<C>>>

Parameters:

S - GenPolynomial.

Returns:

this-S.

subtract

public GenPolynomial<C> subtract(C a,
                                 ExpVector e)

GenPolynomial subtraction. This method is not very efficient, since this is copied.

Parameters:

a - coefficient.

e - exponent.

Returns:

this - a x^e.

subtract

public GenPolynomial<C> subtract(C a)

GenPolynomial subtract. This method is not very efficient, since this is copied.

Parameters:

a - coefficient.

Returns:

this + a x⁰.

negate

public GenPolynomial<C> negate()

GenPolynomial negation.

Specified by:

negate in interface AbelianGroupElem<GenPolynomial<C extends RingElem<C>>>

Returns:

-this.

abs

public GenPolynomial<C> abs()

GenPolynomial absolute value, i.e. leadingCoefficient > 0.

Specified by:

abs in interface AbelianGroupElem<GenPolynomial<C extends RingElem<C>>>

Returns:

abs(this).

multiply

public GenPolynomial<C> multiply(GenPolynomial<C> S)

GenPolynomial multiplication.

Specified by:

multiply in interface MonoidElem<GenPolynomial<C extends RingElem<C>>>

Parameters:

S - GenPolynomial.

Returns:

this*S.

multiply

public GenPolynomial<C> multiply(C s)

GenPolynomial multiplication. Product with coefficient ring element.

Parameters:

s - coefficient.

Returns:

this*s.

monic

public GenPolynomial<C> monic()

GenPolynomial monic, i.e. leadingCoefficient == 1. If leadingCoefficient is not invertible returns this unmodified.

Returns:

monic(this).

multiply

public GenPolynomial<C> multiply(C s,
                                 ExpVector e)

GenPolynomial multiplication. Product with ring element and exponent vector.

Parameters:

s - coefficient.

e - exponent.

Returns:

this * s x^e.

multiply

public GenPolynomial<C> multiply(ExpVector e)

GenPolynomial multiplication. Product with exponent vector.

Parameters:

e - exponent (!= null).

Returns:

this * x^e.

multiply

public GenPolynomial<C> multiply(java.util.Map.Entry<ExpVector,C> m)

GenPolynomial multiplication. Product with 'monomial'.

Parameters:

m - 'monomial'.

Returns:

this * m.

divide

public GenPolynomial<C> divide(C s)

GenPolynomial division. Division by coefficient ring element. Fails, if exact division is not possible.

Parameters:

s - coefficient.

Returns:

this/s.

quotientRemainder

public GenPolynomial<C>[] quotientRemainder(GenPolynomial<C> S)

GenPolynomial 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.

Parameters:

S - nonzero GenPolynomial with invertible leading coefficient.

Returns:

[ quotient , remainder ] with this = quotient * S + remainder and deg(remainder) < deg(S) or remiander = 0.

See Also:

.

divideAndRemainder

@Deprecated
public GenPolynomial<C>[] divideAndRemainder(GenPolynomial<C> S)

Deprecated. use quotientRemainder()

GenPolynomial 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.

Parameters:

S - nonzero GenPolynomial with invertible leading coefficient.

Returns:

[ quotient , remainder ] with this = quotient * S + remainder and deg(remainder) < deg(S) or remiander = 0.

See Also:

.

divide

public GenPolynomial<C> divide(GenPolynomial<C> S)

GenPolynomial 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<GenPolynomial<C extends RingElem<C>>>

Parameters:

S - nonzero GenPolynomial with invertible leading coefficient.

Returns:

quotient with this = quotient * S + remainder.

See Also:

.

remainder

public GenPolynomial<C> remainder(GenPolynomial<C> S)

GenPolynomial 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<GenPolynomial<C extends RingElem<C>>>

Parameters:

S - nonzero GenPolynomial with invertible leading coefficient.

Returns:

remainder with this = quotient * S + remainder.

See Also:

.

gcd

public GenPolynomial<C> gcd(GenPolynomial<C> S)

GenPolynomial greatest common divisor. Only for univariate polynomials over fields.

Specified by:

gcd in interface RingElem<GenPolynomial<C extends RingElem<C>>>

Parameters:

S - GenPolynomial.

Returns:

gcd(this,S).

egcd

public GenPolynomial<C>[] egcd(GenPolynomial<C> S)

GenPolynomial extended greatest comon divisor. Only for univariate polynomials over fields.

Specified by:

egcd in interface RingElem<GenPolynomial<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 comon divisor. Only for univariate polynomials over fields.

Parameters:

S - GenPolynomial.

Returns:

[ gcd(this,S), a ] with a*this + b*S = gcd(this,S).

inverse

public GenPolynomial<C> inverse()

GenPolynomial inverse. Required by RingElem. Throws not implemented exception.

Specified by:

inverse in interface MonoidElem<GenPolynomial<C extends RingElem<C>>>

Returns:

x with this * x = 1, if it exists.

modInverse

public GenPolynomial<C> modInverse(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<C> extend(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<C> extendLower(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<C> contractCoeff(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<C> extendUnivariate(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.

reverse

public GenPolynomial<C> reverse(GenPolynomialRing<C> oring)

Reverse variables. Used e.g. in opposite rings.

Returns:

polynomial with reversed variables.

coefficientIterator

public java.util.Iterator<C> coefficientIterator()

Iterator over coefficients.

Returns:

val.values().iterator().

exponentIterator

public java.util.Iterator<ExpVector> exponentIterator()

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<Monomial<C extends RingElem<C>>>

Returns:

a PolyIterator.

map

public GenPolynomial<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)).