RE: [Axiom-developer] Domains and expressions

[Bill Page]

Gaby,

On March 17, 2006 1:11 PM you wrote:
> 
> Ralf Hemmecke <address@hidden> writes:
> 
> | On 03/16/2006 07:23 PM, Gabriel Dos Reis wrote:
> | > "Bill Page" <address@hidden> writes:
> | > | > In their approach to mimic Axiom, they avoid been careful
> | > | > in making AbelianMonoid "derive" from Monoid.
> | > | Yes, that is interesting - nice diagram. I wonder how much
> | > | of that was actually implemented?
> | > Good question.
> | 
> | No it is so simple. They actually suffer from the same 
> | problem that we have with Axiom/Aldor. However, if you
> | look at the code you find the stuff below. It is simply
> | that: Gauss-Monoid is written additively, and Gauss-AbelianMonoid,
> | too. We could do that in Axiom, too. So, no surprise.
> | 
> | BTW, if you look at Gauss-Ring, you find that the
> | multiplicative structure is not a derived from Gauss-Monoid.
> 
> Interesting, so "to see is to believe" is not true :-)
> Thanks!
> 

Someone more knowledgeable about Maple than I has pointed out
to me that "Gauss" became the package called "Domains". This
is distributed with the current Maple release 10. Here is the
introduction to Domains from the Maple documentation:

Domains Version 1.0

Description

Domains is a tool for developing code for complicated algorithms. The
computational facilities offered by Domains differ from Maple in that you
can parameterize a domain, for example, a polynomial or matrix ring, by the
coefficient ring. This means that the code is more general as it will work
in principle for any coefficient ring.

When computing in Domains, you first construct a domain of computation. For
example, if you want to compute univariate polynomials with rational
coefficients, first create the Q[x] domain as follows 

> with(Domains):
> P := DenseUnivariatePolynomial(Q, x):

The value assigned to P is a Maple table of the operations, available for
computing with polynomials in Q[x]. For example, you can compute the
remainder of two polynomials a and b by doing 

> P[Rem](a,b);

To use Domains interactively, you must first load it into Maple using
with(Domains); 
This also assigns the variables Z and Q to the domain of integers and
rationals respectively, by executing 

> Z := Integers():
> Q := Rationals():

and defines many standard abbreviations for the domains known to Domains.
For more information, see Domains/domain. Having defined the integers Z, you
can compute the remainder of two integers m and n by doing 

> Z[Rem](m,n);

The principle advantage Domains offers over Maple is in allowing you to
parameterize domains (for example, polynomial, series, and matrix rings) by
a coefficient ring R. If you know how to compute in a coefficient ring R,
and you write code for polynomials, then that code should work for any ring
R. You should not have to rewrite the polynomial code for a new R. 

Consider another example. Suppose you have implemented Gaussian elimination
to solve a linear system of equations over a field F. Domains allows you to
parameterize your subroutine by F so that your routine works for all fields,
not just the field of rational numbers that you may have envisioned when
writing the routine. This is accomplished by grouping all operations in a
ring or a field into a datastructure called a domain. In Domains, a domain
is a Maple table of operations. For more details on domains and a list of
known domains, see Domains/domain. 

Coding

Coding with the Domains tool is quite straightforward, although you must
package-call every operation.(See Domains/example.) For an example of how to
code a simple function that computes with values of a domain, see
Domains/coding. 

Coding domains is somewhat more difficult and also cumbersome because nested
lexical scopes and closures are not supported in Maple and must be
simulated. It is recommended that you study the code of existing domains. 

Before using Domains, read the help file Domains/example to see a Domains
sample session. 
Acknowledgements

Some of the main ideas behind Domains come from the AXIOM system, which was
formerly called Scratchpad II. AXIOM also has the notion of parameterized
types which it calls domains. The author of Domains would like to
acknowledge the use of the primary idea behind AXIOM, namely that of passing
as a parameter a collection of functions as a single unit, which the authors
of AXIOM have termed a domain. 

See Also 

Domains/coding, Domains/domain, Domains/evaldomains, Domains/example,
RealDomain 

--------------

Here are two references to the use of the Maple Domains package:

http://www.cas.mcmaster.ca/~carette/publications/ge.pdf

Gaussian Elimination: a case study in efficient
genericity with MetaOCaml

Jacques Carette

Abstract

The Gaussian Elimination algorithm is in fact an algorithm family -
common implementations contain at least 6 (mostly independent)
design choices. A generic implementation can easily be parametrized
by all these design choices, but this usually leads to slow and
bloated code. Using MetaOCaml's staging facilities, we show how
we can produce a natural and type-safe implementation of Gaussian
Elimination which exposes its design choices at code-generation
time, so that these choices can effectively be specialized away,
and where the resulting code is quite efficient.

---------

http://www4.ncsu.edu/~kaltofen/bibliography/99/KaMo99.pdf

On the Genericity of the Modular Polynomial GCD Algorithm*
(c) 1999 ACM

Erich Kaltofen
North Carolina State University
Mathematics Department, Box 8205
Raleigh, N.C. 27695-8205 USA.
E-mail: address@hidden
URL: www.math.ncsu.edu/~kaltofen

Michael Monagan
Centre for Experimental and Constructive Mathematics
Simon Fraser University
Burnaby, British Columbia, V5A 1S6 Canada.
E-mail: address@hidden

Abstract
In this paper we study the generic setting of the modular
GCD algorithm. We develop the algorithm for multivariate
polynomials over Euclidean domains which have a special
kind of remainder function. Details for the parameterization
and generic Maple code are given. Applying this generic
algorithm to a GCD problem in Z=(p)[t][x] where p is small
yields an improved asymptotic performance over the usual
approach, and a very practical algorithm for polynomials
over small finite fields.

Regards,
Bill Page.