PolynomialRing

Package

Class

Use

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.perisic.ring
Class PolynomialRing

java.lang.Object
  com.perisic.ring.Ring
      com.perisic.ring.PolynomialRing

public class PolynomialRing
extends Ring
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+")"); 
    }
}

Last Change: July 03 (Documentation fixed for getTrueCoefficientAt).
Last Change: 13.12.03 (GPL)
Last Change: 01.05.11 (Minor changes in documentation
Copyright: (c) Marc Conrad, 2002-2011
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.

Version:: 0.3
Author:: Marc Conrad
See Also:: Ring.Z

Field Summary

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
`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:
variables - 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.



Returns:
The (local) coefficient ring.





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.



Returns:
The main variable.





add
public RingElt add(RingElt p,
                   RingElt q)

Returns the sum of the parameters.


Specified by:
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.


Specified by:
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.


Specified by:
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.


Specified by:
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.


Specified by:
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:
a - 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:
ob - an object that may or may not be a PolynomialRing.
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:
a - 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:
a - 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)














  
      Package 
    Class 
      Use 
      Tree 
      Deprecated 
      Index 
      Help 
  









 PREV CLASS 
 NEXT CLASS

  FRAMES   
 NO FRAMES   
 







  SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.perisic.ring Class PolynomialRing

PolynomialRing

PolynomialRing

toString

isEuclidian

isUFD

getCoefficientRing

getVariable

add

mult

divmod

ediv

tdiv

mod

gcd

extendedGcd

leadingCoefficient

degree

getCoefficientAt

getTrueCoefficientAt

normalize

globalLeadingCoefficient

one

zero

inv

neg

equalZero

contents

primitivePart

equals

map

map

construct

construct

com.perisic.ring
Class PolynomialRing