Example: A Generic Quotient Field Implementation Using Generic Programming - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Applications and Example Worksheets : Language and System : examples/QuotientFields

Example: A Generic Quotient Field Implementation Using Generic Programming

Quotient Fields

  

As an example of generic programming, a generic quotient field (or field of fractions) construction algorithm is discussed.

Mathematical Description

  

Given an integral domain D, its quotient field is (up to isomorphism) the unique field k, paired with a nonzero ring homomorphism η : D -> k, with the property that, for any nonzero ring homomorphism φ : D -> F, in which F is a field, there is a unique ring homomorphism sigma for which the diagram

  

commutes. Because a nonzero ring homomorphism into a field must be injective, this says that every field F that contains D as a subring must also contain an isomorphic copy of k.

  

Concretely, the quotient field of an integral domain D can be thought of as the set of "reduced fractions" nd, with n, dD.

  

A formal construction can be produced by defining an equivalence relation on the set D×D0, according to which two pairs (n1,d1) and (n2,d2) are equivalent only if,

n1·d2=n2·d1.

  

A representative from each equivalence class is chosen to represent the field element defined by that class. This understanding guides the computer representation of the quotient field.

Unit Normal Representatives

  

If R is a commutative ring with multiplicative identity, then

UR×RR:u,ru·r

  

is a natural action of the group U(R) of units of R on R. Each orbit of this action has a representative called the unit normal representative of the class. Consider an effective mapping R -> R that selects the unit normal representative of each class. For instance, for the ring  of integers, the group U of units is the set { 1, -1 }, the orbits are the sets { n, -n } for n0 together with { 0 }, and you take the unit normal representative to be the positive member of each orbit, and 0 for the orbit { 0 }. (Thus, the unit normal mapping simply computes the sign and absolute value of an integer.) The unit normal mapping on the ring k[T] of polynomials in an indeterminate T over a field k is

pT1lcpT·pT

  

in which lcpT denotes the leading coefficient of the polynomial p( T ). (The group of units in k[ T ] is the set k*=k0, of nonzero members of k, and each orbit of k[ T ] under the action of k* contains an unique monic polynomial that is its representative.)

Designing the Ring Interfaces

  

The first step in representing these ideas in software is to devise an interface that describes the rings. Suppose that the rings are equipped with the basic ring operations, as well as several methods that implement desired computations.

`type/Ring` := '`module`(
    `+`::procedure,
    `*`::procedure,
    `-`::procedure,
    iszero::procedure,
    isone::procedure,
    zero, one
)':

  

This interface corresponds naturally with a formal mathematical characterization of the ring as a tuple

<S,+,*,0,1>

  

that satisfies a number of properties, and to which some computational capabilities have been added. Given the way operator overrides work in Maple, unary negation (-) is added. (In a more tightly integrated system, you specify the number and types of arguments to each of the procedures.)

  

For these computations, you need a slightly richer structure.

`type/GcdRing` := '`module`(
    `+`::procedure,
    `*`::procedure,
    `-`::procedure,
    quo::procedure,
    rem::procedure,
    gcd::procedure,
    unormal::procedure,
    iszero::procedure,
    isone::procedure,
    zero, one
)':

  

This interface extends the Ring interface defined previously. Note that nothing in the signature enforces any ring-theoretic properties (such as being an integral domain, or having unique factorization). It merely specifies the admissible operations. To compute with infinite rings (and even large finite ones), you do not require an enumeration of the elements of the ring. You can focus entirely on the effectively computable operations that the ring must support.

Representing the ring  of Integers

  

One of the simplest examples of a ring that supports the computations is the ring of integers  in its native Maple representation.

MapleIntegers := module()
    description "the ring of integers";
    export `+`, `*`, `-`,
           gcd, unormal, iszero,
           isone, zero, one, rem, quo;
    `+` := ( a, b ) -> a + b;
    `*` := ( a, b ) -> a * b;
    `-` := i -> -i;
    quo := ( a, b ) -> :-iquo( a, b );
    rem := ( a, b ) -> :-irem( a, b );
    gcd := ( a, b ) -> :-igcd( a, b );
    unormal := proc( i::integer )
        if i < 0 then
            -1, -i;
        else
            1, i; # includes 0
        end if;
    end proc;
    iszero := i -> evalb( i = 0 );
    isone := i -> evalb( i = 1 );
    zero := 0;
    one := 1;
end module:

  

This is a software representation of the ring of integers. The unit normal mapping is represented by the exported procedure unormal. It returns an expression sequence of length two, whose first member is a unit, and whose second member is the unit normal form of its argument. The product of the output values yields the input ring element. The other methods only invoke the corresponding built-in Maple operations.

type( MapleIntegers, 'Ring' );

true

(1)

type( MapleIntegers, 'GcdRing' );

true

(2)

An Interface for Fields

  

The quotient field constructor produces a field. An interface that describes fields differs from the one for integral domains by the absence of a gcd method (since they are trivial) and the addition of the (unary) / operator that computes inverses. The methods rem and quo are also not included in the signature for fields, because they are trivial in a field. Two new methods are included:

• 

make for constructing field elements from their numerators and denominators

• 

embed, the natural embedding of the integral domain D into its field k of fractions.

  

Additionally, the two methods numer and denom allow the user to extract the components of a fraction.

`type/Field` := '`module`(
    `+`::procedure,
    `*`::procedure,
    `-`::procedure,
    `/`::procedure,
    normal::procedure,
    iszero::procedure,
    isone::procedure,
    zero, one,
    make::procedure,
    embed::procedure,
    numer::procedure,
    denom::procedure
)':

  

Naturally, the ring  of integers is not a field.

type( MapleIntegers, 'Field' );

false

(3)
  

Fields produced by the quotient field constructor satisfy this interface.

The Quotient Field Functor

  

Here is the generic constructor for quotient fields.

QuotientField := proc( R::GcdRing )
    description "quotient field functor";

    module()
        description "a quotient field";
        export `+`, `*`, `-`, `/`,
               zero, one,
               iszero, isone,
               make,
               numer, denom,
               normal, embed;
        make := proc( n, d )
            local u, nd;
            if R:-iszero( d ) then
                error "division by zero";
            end if;
            u, nd := R:-unormal( d );
            'FRACTION'( u*n, nd );
        end proc;
        embed := d -> make( d, R:-one );
        numer := f -> op( 1, f );
        denom := f -> op( 2, f );
        zero := embed( R:-zero );
        one := embed( R:-one );
        iszero := f -> evalb( normal( f ) = zero );
        isone := f -> evalb( normal( f ) = one );
        normal := proc( f )
            local g, a, b;
            g := R:-gcd( numer( f ), denom( f ) );
            if R:-isone( g ) then
                f;
            else
                a := R:-quo( numer( f ), g );
                b := R:-quo( denom( f ), g );
                make( a, b );
            end if;
        end proc;
        `-` := f -> normal( R:-`-`( numer( f ) ), denom( f ) );
        `/` := f -> normal( make( denom( f ), numer( f ) ) );
        `+` := proc( a, b );
            use `+` = R:-`+`, `*` = R:-`*` in
                normal( make( numer( a ) * denom( b )
                                 + denom( a ) * numer( b ),
                              denom( a ) * denom( b ) ) );
            end use;
        end proc;
        `*` := proc( a, b )
            use `*` = R:-`*` in
                normal( make( numer( a ) * numer( b ),
                              denom( a ) * denom( b ) ) );
            end use;
        end proc;
    end module;
end proc:

  

Note: The source code for QuotientField.mpl is available in the samples/ProgrammingGuide directory of your Maple installation.

  

Most of the exported routines are straightforward. The fraction constructor make accepts two members of the ring R as arguments and returns the constructed fraction, which is represented by an unevaluated function call of the form

  FRACTION( numerator, denominator )

  

The exported procedure embed is the canonical embedding η of the integral domain into its quotient field, described previously. This makes the constructor functorial. The arithmetic operators are simple implementations of the familiar rules for fraction arithmetic:

ab+cd=ad+bcbd

ab×cd=acbd

ab-1=ba

ab=-ab

  

After applying these simple formulae, the result is normalized by using a call to the local routine normal (not the top-level routine :-normal). The normal routine does most of the interesting work in the ring generated by this constructor. It uses the manifestation of the division algorithm in the ring R via the exported procedures quo and gcd to reduce each fraction to the lowest terms. The fraction constructor make and the method normal represent field elements by the normal form representative of the appropriate equivalence class. The make routine prevents division by zero, and forces denominators to be unit normal representatives. The normal routine ensures that fractions are reduced to lowest terms.

  

The most important property of the QuotientField functor is that it is generic. It relies solely on the GcdRing interface. No knowledge of the concrete representation of the input integral domain R (other than that it is a module that satisfies the required interface) is used in the construction. Therefore, it works with any implementation of the GcdRing interface that:

• 

Implements the correct semantics for its public operations

• 

Satisfies the abstract constraint that it be a software representation of an integral domain. (This constraint is required to ensure that the arithmetic operations are well defined.)

Constructing the Rationals as the Quotient Field of  

  

To construct the quotient ring of the ring MapleIntegers defined previously, proceed as follows.

FF := QuotientField( MapleIntegers );

FFmodule...end module

(4)

type( FF, 'Field' );

true

(5)

a := FF:-make( 2, 3 );

aFRACTION2&comma;3

(6)

b := FF:-make( 2, 4 );

bFRACTION2&comma;4

(7)

use FF in
    a + b;
    a * b;
    a / b;
end use;

FRACTION7&comma;6

FRACTION1&comma;3

FRACTION4&comma;3

(8)
  

Note: This is a complex representation of the field of rational numbers.

The Quotient Field of the Polynomial Ring [T]

  

To illustrate the generic quality of this constructor, construct the field [T] of rational functions in a single indeterminate T from a concrete representation of Maple rational polynomials.

MaplePoly := module()
      description "the ring of rational polynomials";
      export `+`, `*`, `-`,
             zero, one,
             iszero, isone,
             gcd, unormal,
             quo, rem;
      `+` := ( a, b ) -> expand( a + b );
      `*` := ( a, b ) -> expand( a * b );
      `-` := p -> -p;
      gcd := ( a, b ) -> :-gcd( a, b );
      unormal := proc( p )
          local lc;
          if iszero( p ) then
              one, zero;
          else
              use lc = lcoeff( p ) in
                  lc, :-normal( p / lc );
              end use;
          end if;
      end proc;
      iszero := p -> Testzero( p );
      isone := p -> Testzero( p - 1 );
      zero := 0;
      one := 1;
      rem := proc( a, b )
          local vars;
          vars := indets( {a,b}, 'name' );
          if nops( vars ) > 1 then
              error "expecting univariate polynomials, but received %1 and %2", a, b;
          end if;
          :-rem( a, b, op( vars ) );
      end proc;
      quo := proc( a, b )
          local vars;
          vars := indets( {a,b}, 'name' );
          if nops( vars ) > 1 then
              error "expecting univariate polynomials, but received %1 and %2", a, b;
          end if;
          :-quo( a, b, op( vars ) );
      end proc;
end module:

  

The unormal method produces the leading coefficient and monic associate of a given polynomial in [T]. The remaining exports simply capture built-in Maple operations on univariate rational polynomials.

RR := QuotientField( MaplePoly );

RRmodule...end module

(9)

type( RR, 'Field' );

true

(10)
  

To make printed fractions more readable, introduce the following extension to the print command.

`print/FRACTION` := ( n, d ) -> sort( n ) / sort( d ):

  

Finally, construct a few examples, and test the arithmetic.

a := RR:-make( randpoly( 'T', 'degree' = 4, 'terms' = 3 ),
               randpoly( 'T', 'degree' = 4, 'terms' = 3 ) );
b := RR:-make( randpoly( 'T', 'degree' = 4, 'terms' = 3 ),
               randpoly( 'T', 'degree' = 4, 'terms' = 3 ) );
use RR in
    a + b;
    a * b;
    a / b;
end use;

a4015T4+6862T26351TT4+473T3+8373T2

b620T4+820T2800TT3+710T+4

620T7+29061573T6+840073T5+1301945146T4+77361773T3+1421241365T2+23002310T25404T6+473T5+1341730T4+1474365T3+741730T2+33273T

2489300T6962140T4+725620T3+5626840T210697420T+5080800T5+473T4+1341730T3+1474365T2+741730T+33273

2489300T65996950T46019580T32978108T214261426T+15750480T7+473T64202263T5+27562263T432432263T3+33202263T2

(11)

 

Return to the Index of Example Worksheets.

See Also

examples/GenericGraphAlgorithms, examples/GenericGroups