What is the right data structure to use for polynomial division?

Michael Monagan, CECM, SFU

Wednesday February 7th, 2007 at 1:30pm in IRMACS 10908.


Suppose we want to divide f by {g1,g2,...,gs} in the polynomial
ring k[x1,...,xn], k a field.  The general division algorithm computes
quotients q1, q2, ...., qs and a remainder r satisfying

   f = q1 g1 + ... + qs gs + r

with r zero or no term in r divisible by any leading term of a divisor gi.
This algorithm forms the heart of Groebner basis computation in the sense
that 99% of the time is spent doing division.
The cost of division depends critically on the data structure that
one uses to represent polynomials in k[x1,...,xn].

In the first part of this talk, given on February 7th, we will present the
standard data structure, a linked list of terms, that is used by Axiom and
other computer algebra systems, and explain why and where it is inefficient.
We present also Thomas Yan's "geobucket" data structure that is used in the
Singular computer algebra system and explain where it is also inefficient.
We suggest that using dynamic arrays of terms with packed exponent vectors
will be better than using linked lists of terms.

In the second part of the talk, given on February 21st, we describe how to
use "pointer heaps" to reduce the number of monomial comparisons.
We can use either a heap of pointers into the divisors or a heap of pointers
into the quotients.  In the first case, the size of the heap will be bounded
by the number of terms in the quotients, in the second, by the number of
terms in the divisors.  We will present some timing data comparing the
various data structures on various division problems.

This is joint work with Roman Pearce.
It is funded by a NSERC CRD research grant and the Maple company.