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

java.lang.Object
  edu.jas.poly.GenPolynomial<C>

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

Direct Known Subclasses:

GenSolvablePolynomial

public class GenPolynomial<C extends RingElem<C>>
extends java.lang.Object
implements RingElem<GenPolynomial<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.

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, 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.
int	compareTo(GenPolynomial<C> b) GenPolynomial comparison.
java.util.Map<ExpVector,GenPolynomial<C>>	contract(GenPolynomialRing<C> pfac) Contract variables.
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) GenPolynomial division with remainder.
void	doPutToMap(ExpVector e, C c) Put an ExpVector to coefficient entry 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.
GenPolynomial<C>	extend(GenPolynomialRing<C> pfac, int j, long k) Extend variables.
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>	inverse() GenPolynomial inverse.
boolean	isConstant() Is GenPolynomial a constant.
boolean	isONE() Is GenPolynomial one.
boolean	isUnit() Is GenPolynomial a unit.
boolean	isZERO() Is GenPolynomial zero.
C	leadingBaseCoefficient() Leading base coefficient.
ExpVector	leadingExpVector() Leading exponent vector.
java.util.Map.Entry<ExpVector,C>	leadingMonomial() Leading monomial.
int	length() Length of GenPolynomial.
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>	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, ExpVector e) GenPolynomial subtraction.
GenPolynomial<C>	subtract(GenPolynomial<C> S) GenPolynomial subtraction.
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	toString() String representation of GenPolynomial.
java.lang.String	toString(java.lang.String[] v) String representation of GenPolynomial.
C	trailingBaseCoefficient() Trailing base coefficient.

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

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

clone

public GenPolynomial<C> clone()

Clone this GenPolynomial.

Specified by:

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

Overrides:

clone in class java.lang.Object

See Also:

Object.clone()

Returns:

Creates and returns a copy of this Elemnt.

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.

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.

See Also:

Object.toString()

Parameters:

v - names for variables.

isZERO

public boolean isZERO()

Is GenPolynomial zero.

Specified by:

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

See Also:

AbelianGroupElem.isZERO()

Returns:

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

isONE

public boolean isONE()

Is GenPolynomial one.

Specified by:

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

See Also:

MonoidElem.isONE()

Returns:

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

isUnit

public boolean isUnit()

Is GenPolynomial a unit.

Specified by:

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

See Also:

MonoidElem.isUnit()

Returns:

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

isConstant

public boolean isConstant()

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

See Also:

Object.equals(java.lang.Object)

Returns:

true if this is equal to b, else false.

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

See Also:

Object.hashCode()

Returns:

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

leadingBaseCoefficient

public C leadingBaseCoefficient()

Leading base coefficient.

Returns:

first coefficient.

trailingBaseCoefficient

public C trailingBaseCoefficient()

Trailing base coefficient.

Returns:

coefficient of constant term.

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.

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.

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.

divideAndRemainder

public GenPolynomial<C>[] divideAndRemainder(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.

See Also:

PolyUtil.basePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial).

Parameters:

S - nonzero GenPolynomial with invertible leading coefficient.

Returns:

[ quotient , remainder ] with this = quotient * S + remainder.

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

See Also:

PolyUtil.basePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial).

Parameters:

S - nonzero GenPolynomial with invertible leading coefficient.

Returns:

quotient with this = quotient * S + remainder.

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

See Also:

PolyUtil.basePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial).

Parameters:

S - nonzero GenPolynomial with invertible leading coefficient.

Returns:

remainder with this = quotient * S + remainder.

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

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.

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

reverse

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

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

Returns:

polynomial with reversed variables.