September 27, 2000 from 3:30 - 4:30 in K9509, SFU

Michael Monagan, Simon Fraser University

Talks on

How do Computer Algebra Systems Implement Mathematical Algorithms?

Abstract: At the heart of a computer algebra system is a representation for polynomials which is used to represent algebraic formulae. In this talk I will show three representations for polynomials:

o Maple's general purpose "sum of products" data structure,

o A recursive dense structure that we are presently prototyping for efficiently implementing GCD and factorization algorithms and

o A sparse distributed data structure which is very suitable for implementing Buchberger's algorithm for Groebner bases.

I will then show how one would program one of these three in two different ways, firstly, in a non-generic way where the coefficients are restricted to certain rings, and secondly in a generic way where the coefficients are permitted to be any ring. The latter case is more difficult, for example, the algorithm may depend on properties of the ring, e.g. the characteristic.

I trust that this will give some insight into differences in design of computer algebra systems, their limitations, and how mathematical algorithms can be implemented in their most generic setting.