JAS - Designs, Problems and Solutions

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

1. Designs

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.

1.1. Ring is object 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.

1.2. Polynomial is object with 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.

1.3. Template, generics and type parameter approaches

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.

2. Problems

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.

3. Solutions

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

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

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

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

  4. 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> >
    
  5. 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.

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

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

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

3.1. Interfaces

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);
}

3.2. Some constructors

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)

3.3. Polynomial examples

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),  ]

3.4. Algebraic number examples

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),  ] ]

3.5. Solvable polynomial examples

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: problems.html 787 2006-03-12 13:29:40Z kredel $