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 RingElts,
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 RingElems.
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 longs.
Other implementations, e.g. sparse representation or
bigger numbers or ints 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 GenPolynomials
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 ]
Last modified: Sun Mar 12 14:29:09 CET 2006
$Id$