com.perisic.ring
Class PolynomialRing

java.lang.Object
  |
  +--com.perisic.ring.Ring
        |
        +--com.perisic.ring.PolynomialRing

public class PolynomialRing

extends Ring

Multivariate Polynomials over a Ring. Example of use (Polynomials of Z[a][b]):

 import com.perisic.ring.*;
 import java.math.*;
 public class PolynomialRingExample1 { 
 public static void main(String [] args) { 
    PolynomialRing P = new PolynomialRing(Ring.Z,"a,b");
    RingElt a = P.map("a^2 - b^2");
    RingElt b = P.map("(a - b)^2");
    
    RingElt d = P.gcd(a,b);
    System.out.println("gcd("+a+","+b+") = "+d+" (in "+P+")"); 
    }
}

writes "gcd(a^2 + -1*b^2,a^2 + -2*a*b + b^2) = -1*a + b (in Z[a][b])" to the output.
• Last Change: July 03 (Documentation fixed for getTrueCoefficientAt).
• Last Change: 13.12.03 (GPL)
• Copyright: (c) Marc Conrad, 2002, 2003
• Email: ring@perisic.com. Please let me know if you use this software.
• WWW: www.ring.perisic.com
• The com.perisic.ring library is distributed under the terms of the GNU Lesser General Public License (LGPL).
• If you require the package under a different licence please contact me.
• disclaimer: The classes are provided "as is". There is no warranty implied by using the com.perisic.ring package.

See Also:

Ring.Z

Fields inherited from class com.perisic.ring.Ring

C, F2, Q, R, Z

Constructor Summary

PolynomialRing(Ring R, java.lang.String variables)
Constructs a new polynomial ring over one or more variables.

PolynomialRing(Ring R, java.lang.String[] variables)
Constructs a new polynomial ring over variables.length variables.

Method Summary

RingElt	add(RingElt p, RingElt q) Returns the sum of the parameters.
RingElt	construct(int[] exponents, java.lang.Object[] coefficients) Returns a Polynomial by matching exponents to coefficients.
RingElt	construct(int exponent, java.lang.Object coefficient) Returns the Polynomial coefficient * X^exponent, where X is the variable of this PolynomialRing.
RingElt	contents(RingElt b) Returns the contents of b.
int	degree(RingElt b) The degree of b, where b is considered as an univariate polynomial.
RingElt[]	divmod(RingElt p, RingElt q) Returns an array { p/q, p%q }.
RingElt	ediv(RingElt p, RingElt q) Returns p/q (Euclidian division).
boolean	equals(java.lang.Object ob) true if coefficient ring and variable are the same.
boolean	equalZero(RingElt b) Returns true if b is equals to zero, false otherwise.
RingElt[]	extendedGcd(RingElt a, RingElt b) Extended greatest common divisor of the parameters.
RingElt	gcd(RingElt p, RingElt q) Greatest common divisor of the parameters.
RingElt	getCoefficientAt(int i, RingElt b) Returns the coefficient for x^i of b (or null), where b is considered as an univariate polynomial over x.
Ring	getCoefficientRing() Returns the Ring R sucht that the PolynomialRing is the Ring R[x] where x is the variable of the PolynomialRing.
RingElt	getTrueCoefficientAt(int i, RingElt b) Returns the coefficient for x^i of b, where b is considered as an univariate polynomial over x.
java.lang.String	getVariable() Returns the variable x sucht that the PolynomialRing is the Ring R[x] where R is a Ring.
RingElt	globalLeadingCoefficient(RingElt b) Determins recursively the global leading Coefficient of the polynomial over all variables.
RingElt	inv(RingElt b) Returns 1/b as an element of this Ring.
boolean	isEuclidian() true if the coefficient ring is a field.
boolean	isUFD() true if the coefficient ring and therefore also the polynomial ring is an uniqe factorization domain.
RingElt	leadingCoefficient(RingElt b) The leading coefficient of b, where b is considered as an univariate polynomial.
RingElt	map(RingElt a) Maps a RingElt of various other rings to this ring.
RingElt	map(java.lang.String a) Maps a String to an element of this PolynomialRing.
RingElt	mod(RingElt p, RingElt q) Returns p%q (remainder of Euclidian division).
RingElt	mult(RingElt p, RingElt q) Returns the product of the parameters.
RingElt	neg(RingElt b) Returns -b as an element of this Ring.
RingElt	normalize(RingElt b) Returns a normal form for the polynomial b.
RingElt	one() Returns 1 as an element of this Ring.
RingElt	primitivePart(RingElt a) Returns b/contents(b).
RingElt	tdiv(RingElt p, RingElt q) Returns p/q (true division).
java.lang.String	toString() Returns a the polynomial ring in the format R[x1][x2]...[xn].
RingElt	zero() Returns 0 as an element of this Ring.

Methods inherited from class com.perisic.ring.Ring

div, eltToString, equal, evaluatePolynomial, isField, map, map, map, pow, pow, sub

Methods inherited from class java.lang.Object

clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PolynomialRing

public PolynomialRing(Ring R,
                      java.lang.String variables)

Constructs a new polynomial ring over one or more variables. Examples:

• P = new PolynomialRing(Ring.Z, "a,x1,x2,x3,y"); generates P = Z[a][x1][x2][x3][y].
• S = new PolynomialRing(new QuotientField(P),"W"); with P as before, generates S = Z(a,x1,x2,x3,y)[W].

Notes:

• Variables names should start with a letter followed by letters or numbers. However every combination of characters is possible but might lead to unexpected behaviour when parsing from a string or mapping from/to the PolynomialRing.
• PolynomialRings are constructed recursively. So, S = new PolynomialRing(R,"a,b"); is the same as T = new PolynomialRing(R,"a"); S = new PolynomialRing(T,"b");

Parameters:

variables - is a comma separated list of alphanumeric characters.

R - is the (global) Coefficient Ring

PolynomialRing

public PolynomialRing(Ring R,
                      java.lang.String[] variables)

Constructs a new polynomial ring over variables.length variables. The behaviour is similar as of PolynomialRing(Ring,java.lang.String).

Parameters:

an - String array of alphanumeric characters.

R - is the (global) Coefficient Ring

See Also:

PolynomialRing(Ring,java.lang.String).

Method Detail

toString

public java.lang.String toString()

Returns a the polynomial ring in the format R[x1][x2]...[xn]. As polynomial rings are constructed recursively the general form is S[a] where a is the variable of the polynomial ring and S the String description of the coefficient ring.

Overrides:

toString in class java.lang.Object

Returns:

a String which describes the polynomial ring.

isEuclidian

public boolean isEuclidian()

true if the coefficient ring is a field. False otherwise. This is equivalent to the condition that the Polynomial Ring is Euclidian.

Overrides:

isEuclidian in class Ring

Returns:

true if the polynomial ring is Euclidian.

isUFD

public boolean isUFD()

true if the coefficient ring and therefore also the polynomial ring is an uniqe factorization domain. False otherwise.

Overrides:

isUFD in class Ring

Returns:

true if the polynomial ring is an UFD

getCoefficientRing

public Ring getCoefficientRing()

Returns the Ring R sucht that the PolynomialRing is the Ring R[x] where x is the variable of the PolynomialRing. So for Z[a][b] we have R = Z[a] and x = b.

getVariable

public java.lang.String getVariable()

Returns the variable x sucht that the PolynomialRing is the Ring R[x] where R is a Ring. So for Z[a][b] we have R = Z[a] and x = b.

add

public RingElt add(RingElt p,
                   RingElt q)

Returns the sum of the parameters.

Overrides:

add in class Ring

Parameters:

p - a RingElt which can be mapped via map(RingElt) to an element of this ring.

q - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

p + q.

mult

public RingElt mult(RingElt p,
                    RingElt q)

Returns the product of the parameters.

Overrides:

mult in class Ring

Parameters:

p - a RingElt which can be mapped via map(RingElt) to an element of this ring.

q - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

p * q.

divmod

public RingElt[] divmod(RingElt p,
                        RingElt q)

Returns an array { p/q, p%q }. Here, p/q is euclidian division and p/q the remainder arising from euclidian division.

Note: For non Euclidian rings this method still works if the leading coefficient of q is a unit in the Coefficient Ring.

Parameters:

p - a RingElt which can be mapped via map(RingElt) to an element of this ring.

q - a RingElt which can be mapped to via map(RingElt) an element of this ring.

Returns:

An Array { p/q, p%q } of Euclidian quotient and remainder.

ediv

public RingElt ediv(RingElt p,
                    RingElt q)

Returns p/q (Euclidian division).

Overrides:

ediv in class Ring

Parameters:

p - a RingElt which can be mapped via map(RingElt) to an element of this ring.

q - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

p/q (Euclidian quotient).

tdiv

public RingElt tdiv(RingElt p,
                    RingElt q)

Returns p/q (true division). If the division cannot be performed, that is p%q is not equals 0, a RingException is thrown.

Overrides:

tdiv in class Ring

Parameters:

p - a RingElt which can be mapped via map(RingElt) to an element of this ring.

q - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

p/q (true quotient).

Throws:

RingException - for p%q != 0.

mod

public RingElt mod(RingElt p,
                   RingElt q)

Returns p%q (remainder of Euclidian division).

Overrides:

mod in class Ring

Parameters:

p - a RingElt which can be mapped via map(RingElt) to an element of this ring.

q - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

p%q (remainder of Euclidian division).

gcd

public RingElt gcd(RingElt p,
                   RingElt q)

Greatest common divisor of the parameters.

Overrides:

gcd in class Ring

Parameters:

p - a RingElt which can be mapped via map(RingElt) to an element of this ring.

q - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

gcd(p,q).

extendedGcd

public RingElt[] extendedGcd(RingElt a,
                             RingElt b)

Extended greatest common divisor of the parameters. Returns an array { d, s } where the first entry d is the greatest common divisor of the parameters a and b and the second entry is an inverse of b modulo a. The coefficient ring must be a field, otherwise an error is thrown.

Parameters:

a - a RingElt which can be mapped via map(RingElt) to an element of this ring.

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

{ d, s } such that d = gcd(a,b) such that b * s = d mod a.

Throws:

RingException - if the coefficient ring is not a field.

leadingCoefficient

public RingElt leadingCoefficient(RingElt b)

The leading coefficient of b, where b is considered as an univariate polynomial. So, if b = an * x^n ... + a1 * x + a0 the coefficient an is returned. The return value for the null polynomial is 0.

Parameters:

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

the leading coefficient of b.

degree

public int degree(RingElt b)

The degree of b, where b is considered as an univariate polynomial. So, if b = an * x^n ... + a1 * x + a0 with an != 0, the value n is returned.

Parameters:

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

the degree of the univariate polynomial b.

getCoefficientAt

public RingElt getCoefficientAt(int i,
                                RingElt b)

Returns the coefficient for x^i of b (or null), where b is considered as an univariate polynomial over x. So, if b = an * x^n ... + a1 * x + a0 with an != 0 the coefficient ai is returned if ai != 0. For ai == 0 null is returned. If i > n or i < 0 a java.lang.IndexOutOfBoundException is thrown.

Note: If the coefficient is 0 then null is returned!

Parameters:

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

the i-th coefficient of b or null.

Throws:

IndexOutOfBoundException - for i < 0 or i > degree(b).

getTrueCoefficientAt

public RingElt getTrueCoefficientAt(int i,
                                    RingElt b)

Returns the coefficient for x^i of b, where b is considered as an univariate polynomial over x. So, if b = an * x^n ... + a1 * x + a0 the coefficient ai is returned. Note that while getCoefficientAt() might return null, getTrueCoefficientAt() always returns an element of the coefficient ring.

Parameters:

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

the i-th coefficient of b.

normalize

public RingElt normalize(RingElt b)

Returns a normal form for the polynomial b. The normal form for multivariate polynomials over a field is defined as the global leading coefficient is equals 1. For multivariate polynomials over Z the normal form is defined as the global leading coefficient being positive.

Parameters:

b - A RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

A normal form of b.

Throws:

RingException - if the polynomial is not (consindered as multivariate) a polynomoial over a field or Z.

globalLeadingCoefficient

public RingElt globalLeadingCoefficient(RingElt b)

Determins recursively the global leading Coefficient of the polynomial over all variables. Note that the result depends on the order of the variables, e.g. the global leading coefficient of 2 * a^2 + 3 * b^3 is equals 3 in Q[a][b] but 2 in Q[b][a].

Parameters:

b - A RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

The global leading coefficient.

one

public RingElt one()

Returns 1 as an element of this Ring.

Overrides:

one in class Ring

Returns:

1.

zero

public RingElt zero()

Returns 0 as an element of this Ring.

Overrides:

zero in class Ring

Returns:

0.

inv

public RingElt inv(RingElt b)

Returns 1/b as an element of this Ring. An RingException is thrown if the degree of b is greater then

Overrides:

inv in class Ring

Parameters:

b - A RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

1/b.

neg

public RingElt neg(RingElt b)

Returns -b as an element of this Ring.

Overrides:

neg in class Ring

Parameters:

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

-b.

equalZero

public boolean equalZero(RingElt b)

Returns true if b is equals to zero, false otherwise.

Overrides:

equalZero in class Ring

Parameters:

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

true if and only if b == 0.

contents

public RingElt contents(RingElt b)

Returns the contents of b. The contents is the greatest common divisor over all coefficients.

Parameters:

b - a RingElt which can be mapped via map(RingElt)to an element of this ring.

Returns:

The greatest common divisor of all coefficients of b.

primitivePart

public RingElt primitivePart(RingElt a)

Returns b/contents(b). The contents is the greatest common divisor over all coefficients.

Parameters:

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

The primitive part of b.

equals

public boolean equals(java.lang.Object ob)

true if coefficient ring and variable are the same. False, if ob is not a PolynomialRing or coefficient ring or variable differ. Note that, according to this definition R[a][b] and R[b][a] are different.

Overrides:

equals in class java.lang.Object

Parameters:

b - a RingElt which can be mapped via map(RingElt) to an element of this ring.

Returns:

b == this.

map

public RingElt map(RingElt a)

Maps a RingElt of various other rings to this ring. The elements of the following Rings are mapped to elements of this PolynomialRing by this method.

• Elements of the Ring.Z of integers.
• Elements of the Ring.Q of rational numbers, if the denominator is a unit in the coefficient ring.
• Elements of each other Ring which can be mapped into the coefficient ring.
• Elements of another PolynomialRing if (1) the set of variables is a subset of the set of variables of this PolynomialRing. and if (2) the coefficient ring can be mapped.
• Elements of a QuotientField if the denominator is invertible in this PolynomialRing and if numerator and denominator can be mapped into the PolynomialRing.

Example:

Elements of the following rings are mapped into F2[a][b][c][d]:

Q[a][b][c][d], F2[a], Z[d][b], Q[b][a], F2[d][b][c][a], Quot(Z[b][d]), ...

Overrides:

map in class Ring

Parameters:

b - a RingElt which can be mapped to an element of this ring.

Returns:

b == this.

Throws:

RingException - if the element cannot be mapped.

map

public RingElt map(java.lang.String a)

Maps a String to an element of this PolynomialRing. Valid Strings are combinations of variables, numbers, +, -, *, /, (, ), and ^ which can be sesibly interpreted as a polynomial of this PolynomialRing. Restrictions: ^ must be followed by a positive number (the exponent), ** for exponentiation is not valid (use ^ instead), the * must be explicitely written (i.e. 2 * a instead of 2a). Examples for valid inputs for this = R[a][b] with R = Ring.R:

a - b, (a + b)^2 * 1.2/7, 1 + ((a + b + a * 5.0 + (3 - b)^13)^17)/10.

Known Bugs/Problems: Expressions containing arithmetic operators with an alternative meaning lead to problems. For example 2E-3 for the DoubleField Number 0.002 leads to a RingException. Use 2/(10^3) instead.

Overrides:

map in class Ring

Parameters:

b - a RingElt of this PolynomialRing which is described by the String.

Returns:

b == this.

Throws:

RingException - if the String cannot be interpreted.

construct

public RingElt construct(int[] exponents,
                         java.lang.Object[] coefficients)

Returns a Polynomial by matching exponents to coefficients. All values exponents[i] must be different. The length of the two arrays must be the same. If exponents = { e0, e1, ..., en } and coefficients = { a0, a1, ..., an } the polynomial a0 * X^e0 + a1 * X^e1 + ... an * X^en is returned (the coefficients are mapped into the coefficient ring first), where X is the variable of this PolynomialRing.

Parameters:

exponents - An array of positive integers.

coefficients - An array of objects which can be mapped to elements of the Coefficient Ring.

Returns:

Returns the polynomial obtained by matching exponents to coefficients.

construct

public RingElt construct(int exponent,
                         java.lang.Object coefficient)

Returns the Polynomial coefficient * X^exponent, where X is the variable of this PolynomialRing.

Parameters:

coefficient - An object which can be mapped to an element of the coefficient ring.

exponent - A positive integer.

Returns:

coefficient * X^exponent.

See Also:

map(java.lang.String), map(RingElt), Ring.map(java.math.BigInteger)