In ths document we discus some design alternatives, some problems and present our implemented solutions.

**Note:**
In this section 'base ring'
and 'extension ring' mean object oriented concepts not
the mathematical concepts. I.e. 'base ring' is the super class
of all considered ring classes and 'extension ring' is some
subclass of the 'base ring' class.

The first question is which classes or which objects implement the arithmetic of polynomials. Are polynomials only passive containers which are transformed by ring methods? Or are polynomials active objects with methods.

One design was proposed e.g. by M. Conrad in 2002
(see ring.perisic.com).
It starts with an abstract `Ring`

with abstract
methods for the ring operations and some real implementations,
e.g. for powers. The method parameters are `RingElt`

s,
which serve mostly as containers for the different ring
implementations. The concrete rings, e.g. rational numbers
or polynomials, extend `Ring`

and implement the
algortihms for the respective (extended) `RingElt`

data structures. `RingElt`

structures are moreover
mostly private classes within their corresponding `Ring`

extension.

Type resolution of the parameters of the methods is completely dynamic
during runtime. There is no compile time type checking.
The type resolution, by means of a `RingX.map(RingElt)`

method, is moreover able to coerce elements from one ring to
some other ring, e.g. form rational to polynomial over rationals,
similar to Scratchpad.
The base `Ring`

knows about all extension rings, like in
a closed world.

Creation of extension rings is mainly at initialization time of the
base ring (since it knows all extensions) into ring properties.
Creation of ring elements is mostly dynamic using direct constructors
in the various `map()`

methods.

An other design, e.g. used in our approach, takes polynomials as
the primary players. A `Polynomial`

is implemented as
a class with the usual algebraic operations as methods.
Each polynomial has a reference to a corresponding `Ring`

object, which is a container for the ring characteristics. E.g.
for polynomial rings these are the number of variables, the
type information of the coefficent ring, the term order,
the names of the variables and eventualy the commutator relations.
There is one proposal by V. Niculescu, from 2003,
[ref:
A design proposal for an object oriented algebraic library]
to view and implement the `Ring`

as a factory class
for polynomials and to make the polynomial constructors unavailable.

Creation of ring elements was in our first design by employing the
prototype creational pattern (via `clone()`

)
and directly using element constructors. In the new design it
will use the factory pattern (via `getZERO()`

,
`getONE()`

etc.) of the `RingFactory`

Type resolution of the coefficient or polynomial method parameters are
to the respective interface during compile time with a dynamic upcast
to the actual polynomial or coefficient during runtime.
There is currently no mapping of elements from one ring to
another. However there are conversions / constructor / parser methods
from `long`

, `java.math.BigInteger`

,
`String`

and `java.io.Reader`

in the new design.

These approaches may not be completely covered by Java, C++ or C#. For polynomials they mean the usage of a type parameter (eventually restricted to some unterface) for the coefficient ring.

The creation problem is difficult to solve in Java, since
type parameters can not be used in `new`

or `class.newInstance()`

. I.e. new objects can not be
generated only from a type parameter but only from an object or class.

During the development and refactorings some problems have been detected. Consider the following interface and class definitions.

interface ModulElem { ModulElem sum(ModulElem other); ... } interface RingElem extends ModulElem { // RingElem sum(RingElem other); no override RingElem multiply(RingElem other); ... } class Rational implements RingElem { // jdk 1.5 /*ModulElem*/ Rational sum(ModulElem other) { ... } /*RingElem*/ Rational multiply(RingElem other) { if ( other instanceof Rational ) { return multiply( (Rational)other ); } else { return // coerce to suitable ring extension } } Rational multiply(Rational other) { ... } } class Complex implements RingElem { ... } void usageOK() { Rational a = new Rational(); Rational b = new Rational(); Rational c; c = a.sum(b); // jdk 1.5 c = a.multiply(b); // jdk 1.5 } void usageProblem1() { RingElem a = new Rational(); RingElem b = new Rational(); RingElem c; c = (RingElem) a.sum(b); // must cast c = a.multiply(b); // no cast } void usageProblem2() { RingElem a = new Rational(); RingElem b = new Complex(); RingElem c; c = a.multiply(b); // runtime failiure }

One problem is the cast in
`c = (RingElem)a.sum(b)`

which is not expected since a and b are `RingElem`

s.
One sulution would be to redefine `sum()`

for
`RingElem`

, but then `sum()`

in
`ModulElem`

is not overriden.
Then `RingElem`

is no longer an extension of
`ModulElem`

and the relation between the
interfaces is broken.

The other problem is 'up cast' in
`return multiply( (Rational)other )`

which defeates compile time type safety.
`multiply( )`

is at first not meaningful defined
between `Rational`

and `Complex`

.
One could as in Scratchpad coerce `Rational`

to `Complex`

(here extend) and multiply to
`Complex`

objects, but this may not be expected
by the application.

This problems exist also if abstract classes are used instead of interfaces.

Reflecting on the mentioned designs and problems our design proposal is as follows.

We do not distinguish between interfaces for modules, rings or fields. There is only one interface for rings, wich also defines

`inverse()`

and`quotient()`

together with a method`isUnit()`

to see if a certain element is invertible or can be used as divisor.To separate the creation process of ring elements from the implementation of the ring element abstract data type we distinguish two interfaces:

`RingElem<C extends RingElem>`

and`RingFactory<C extends RingElem>`

.`RingElem`

uses a type parameter`C`

which is itself recursively reqired to extend`RingElem`

:`C extends RingElem`

. Also the interface`RingFactory`

depends on the same type parameter.Basic data types, such as rational numbers, can directly implement both interfaces but more complex data types, such as polynomials will implement the interfaces in two different classes. e.g.

BigRational implements RingElem<BigRational>, RingFactory<BigRational>

or for generic polynomials

GenPolynomial<C extends RingElem<C> > implements RingElem< GenPolynomial<C> > GenPolynomialRing<C extends RingElem<C> > implements RingFactory< GenPolynomial<C> >

Constructors for basic data types can be implemented in any appropriate way. Constructors for more complex data types should always require one parameter to be of the respective factory type. This is to avoid the creation of elements with no knowledge of is corresponding ring factory. Constructors which require more preconditions, which are only provided by type (internal) methods should not be declared public. It seems best to declare them as protected.

Basic arithmetic is implemented using the

`java.math.BigInteger`

class, which is itself implemented like GnuMP. At the moment the following classes are implemented`BigInteger`

,`BigRational`

,`ModInteger`

,`BigComplex`

,`BigQuaternion`

and`AlgebraicNumber`

.Generic polynomials are implemented as sorted maps from exponent vectors to coefficients. For sorted map the Java class

`java.util.TreeMap`

is used. The older alternative implementation using`Map`

, implemented with`java.util.LinkedHashMap`

, has been abandoned. There is only one implementation of exponent vectors`ExpVector`

as dense Java array of`long`

s. Other implementations, e.g. sparse representation or bigger numbers or`int`

s are not considered at the moment. The comparators for`SortedMap<ExpVector,C>`

are created from a`TermOrder`

class which implements most used term orders in practice.Non commutative polynomials with respect to certain commutator relations, so called solvable polynomials, are extended from

`GenPolynomial`

respectively`GenPolynomialRing`

. The relations are stored in`RelationTable`

objects, which are inteded to be internal to the`GenSolvablePolynomialRing`

. The class`GenSolvablePolynomial`

implements the non commutative multiplication and uses the commutative methods from its super class`GenPolynomial`

. As mentioned before, some casts are eventualy required, e.g.`GenSolvablePolynomial<C> p.sum(q)`

. The respective objects are however correctly buildt using the methods from the solvable ring factory.

The class design allows solvable polynomial objects to be used in all algorithms where`GenPolynomial`

s can be used as parameters as long as no distinction between left and right multiplication is required.

The interface definition for ring elements with the usual arithmetic operations and some status, comparison methods and a clone method is as follows.

public interface RingElem<C extends RingElem> extends Cloneable, Comparable<C>, Serializable { public C clone(); public boolean isZERO(); public boolean isONE(); public boolean isUnit(); public boolean equals(Object b); public int hashCode(); public int compareTo(C b); public int signum(); public C sum(C S); public C subtract(C S); public C negate(); public C abs(); public C multiply(C S); public C divide(C S); public C remainder(C S); public C inverse(); }

The interface definition for a ring factory for the creation respectively the reference to the ring constants 0 and 1 is given in the following code. Moreover there are often used casts / conversions from the basic Java types long and BigInteger, as well as a method to create a random element of the ring, a counter part to clone and some parsing methods to obtain a ring element from some external String or Reader.

public interface RingFactory<C extends RingElem> extends Serializable { public C getZERO(); public C getONE(); public C fromInteger(long a); public C fromInteger(BigInteger a); public C random(int n); public C copy(C c); public C parse(String s); public C parse(Reader r); }

Constructors for BigRational:

protected BigRational(BigInteger n, BigInteger d) // assert gcd(n,d) == 1 public BigRational(BigInteger n) public BigRational(long n, long d) public BigRational(long n) public BigRational() public BigRational(String s) throws NumberFormatException

Constructors for GenPolynomial

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

Constructors for GenPolynomialRing

public GenPolynomialRing(RingFactory< C > cf, int n) public GenPolynomialRing(RingFactory< C > cf, int n, TermOrder t) { public GenPolynomialRing(RingFactory< C > cf, int n, TermOrder t, String[] v)

Example of a random polynomial in 7 variables over the rational numbers with default term order and with 10 non zero coefficients:

BigRational cfac = new BigRational(); GenPolynomialRing<BigRational> fac; fac = new GenPolynomialRing<BigRational>(cfac,7); GenPolynomial<BigRational> a = fac.random(10); a = GenPolynomial[ 31/5 (0,0,0,1,2,1,2), 19/15 (2,0,0,0,0,0,2), 13/5 (0,2,1,1,0,0,0), 2/3 (0,0,2,0,0,0,0), 217/18 (0,0,0,2,0,0,0), 18/5 (0,0,0,0,2,0,0), 11/32 (1,0,0,0,0,0,0), 63/4 (0,0,0,0,0,0,0) ] :: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ]

Example of a random polynomial in 3 variables over a polynomial ring in 7 variables over the rational numbers, both with default term order and with 10 non zero coefficients:

BigRational cfac = new BigRational(); GenPolynomialRing<BigRational> fac; fac = new GenPolynomialRing<BigRational>(cfac,7); GenPolynomialRing<GenPolynomial<BigRational>> gfac; gfac = new GenPolynomialRing<GenPolynomial<BigRational>>(fac,3); GenPolynomial<GenPolynomial<BigRational>> a = gfac.random(10); a = GenPolynomial[ GenPolynomial[ 10/3 (2,0,1,1,0,0,2), 8/7 (1,0,2,0,0,0,0), 9/5 (0,1,0,0,0,0,0), 1/4 (0,0,1,0,0,0,0), 3/14 (0,0,0,0,0,0,0) ] :: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (2,1,0), GenPolynomial[ 26/23 (0,2,2,0,1,0,2), 9/4 (1,0,0,0,0,1,1), 29/17 (0,0,2,0,1,0,0), 24/19 (2,0,0,0,0,0,0), 28/13 (1,0,0,1,0,0,0), 11/32 (0,0,1,0,1,0,0), 18/11 (1,0,0,0,0,0,0), 5/11 (0,0,0,0,1,0,0), 475/32 (0,0,0,0,0,0,0) ] :: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (2,0,0), GenPolynomial[ 14/15 (2,0,0,1,1,0,2), 19/5 (1,1,0,0,0,0,0), 4/29 (0,0,2,0,0,0,0), 23/27 (0,0,0,2,0,0,0), 20/13 (0,0,0,0,0,0,0) ] :: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (0,0,2), GenPolynomial[ 13/8 (2,0,0,1,1,0,0), 8/7 (2,0,0,0,0,0,2), 21/2 (0,0,1,0,0,0,2), 23/22 (0,1,0,0,0,1,0), 9/11 (0,0,0,2,0,0,0), 21/2 (0,0,0,0,2,0,0), 23/13 (0,0,0,0,0,2,0), 5/2 (0,1,0,0,0,0,0), 367/62 (0,0,0,0,0,0,0) ] :: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (1,0,0), GenPolynomial[ 4/3 (0,1,0,1,2,1,1), 17/2 (2,1,0,0,2,0,0), 10/29 (1,0,0,0,0,2,2), 3/2 (0,0,2,2,0,0,1), 11/8 (2,0,0,0,0,0,2), 26/31 (0,2,1,0,0,0,0), 10/9 (0,0,1,2,0,0,0), 4/5 (0,0,1,0,0,2,0), 1/8 (2,0,0,0,0,0,0), 1161/406 (0,2,0,0,0,0,0), 31/6 (0,0,0,2,0,0,0), 19 (0,0,1,0,0,0,0), 2 (0,0,0,0,0,1,0), 7/19 (0,0,0,0,0,0,1), 20227/2520 (0,0,0,0,0,0,0) ] :: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (0,0,0) ] :: GenPolynomialRing[ GenPolynomialRing, 3, IGRLEX(4), ]

Example of algebraic numbers

AlgebraicNumber<C extends RingElem<C> > implements RingElem< AlgebraicNumber<C> >, RingFactory< AlgebraicNumber<C> >

over rational numbers (so defining an algebraic extension Q(alpha))

BigRational cfac = new BigRational(); GenPolynomialRing<BigRational> mfac; mfac = new GenPolynomialRing<BigRational>( cfac, 1 ); GenPolynomial<BigRational> modul = mfac.random(8).monic(); // assume !modul.isUnit() AlgebraicNumber<BigRational> fac; fac = new AlgebraicNumber<BigRational>( modul ); AlgebraicNumber< BigRational > a = fac.random(15); modul = GenPolynomial[ 1 (2), 13/12 (1), 55/21 (0) ] :: GenPolynomialRing[ BigRational, 1, IGRLEX(4), ] a = AlgebraicNumber[ GenPolynomial[ 1 (1), -175698982/14106209 (0) ] :: GenPolynomialRing[ BigRational, 1, IGRLEX(4), ] mod GenPolynomial[ 1 (2), 13/12 (1), 55/21 (0) ] :: GenPolynomialRing[ BigRational, 1, IGRLEX(4), ] ]

or modular integers (so defining a Galois field GF(p,n)).

long prime = getPrime(); // 2^60-93 ModInteger cfac = new ModInteger(prime,1); GenPolynomialRing<ModInteger> mfac; mfac = new GenPolynomialRing<ModInteger>( cfac, 1 ); GenPolynomial<ModInteger> modul = mfac.random(8).monic(); // assume !modul.isUnit() AlgebraicNumber<ModInteger> fac; fac = new AlgebraicNumber<ModInteger>( modul ); AlgebraicNumber< ModInteger > a = fac.random(12); modul = GenPolynomial[ 1 mod(1152921504606846883) (2), 123527304065019309 mod(1152921504606846883) (1), 452933448238404135 mod(1152921504606846883) (0) ] :: GenPolynomialRing[ ModInteger, 1, IGRLEX(4), ] a = AlgebraicNumber[ GenPolynomial[ 1 mod(1152921504606846883) (1), 384307168202282226 mod(1152921504606846883) (0) ] :: GenPolynomialRing[ ModInteger, 1, IGRLEX(4), ] mod GenPolynomial[ 1 mod(1152921504606846883) (2), 123527304065019309 mod(1152921504606846883) (1), 452933448238404135 mod(1152921504606846883) (0) ] :: GenPolynomialRing[ ModInteger, 1, IGRLEX(4), ] ]

Example for the creation of a solvable polynomial ring factory. The relation table is created internally.

BigRational fac = new BigRational(0); TermOrder tord = new TermOrder(TermOrder.INVLEX); String[] vars = new String[]{ "x", "y", "z" }; int nvar = vars.length; spfac = new GenSolvablePolynomialRing<BigRational>(fac,nvar,tord,vars); spfac = GenSolvablePolynomialRing[ BigRational, 3, INVLEX(2), x y z , #rel = 0 ] spfac.table = RelationTable[]

A non empty relation table looks as follows.

f = GenSolvablePolynomialRing[ BigRational, 3, INVLEX(2), x y z , #rel = 1 ] f.ring.table = RelationTable[ [0, 1]=[ExpVectorPair[(1,0,0),(0,1,0)], GenSolvablePolynomial[ 1 (1,1,0), -1 (0,0,0) ] :: GenSolvablePolynomialRing[ BigRational, 3, INVLEX(2), x y z , #rel = 1 ] ] ]

Example of a solvable polynomial over Z_19.

d = GenSolvablePolynomial[ 3 mod(19) (1,1,0), 1 mod(19) (0,0,1) ] :: GenSolvablePolynomialRing[ ModInteger, 3, INVLEX(2), x y z , #rel = 1 ]

Heinz Kredel

Last modified: Sun Mar 12 14:29:09 CET 2006

$Id$