Topics in Comptuter Algebra: II

Algorithms and data structures for sparse polynomial multiplication and division.

Michael Monagan, Department of Mathematics, Simon Fraser University.

Wednesday May 23 and 30, 2009, K9509, 3:30-5:00pm.

Abstract:
Suppose we have two multivariate polynomials F and G in k[x1,...,xn], k a field.
Let Q and R be the quotient and remainder of F divided G so that
F = Q G + R.  Suppose the divisor has M terms and the quotient has N
terms and suppose also they are sparse so that F = Q G has O(M N) terms.
We will study the efficiency of various data structures for polynomial division.

The Axiom computer algebra system uses a linked list of terms, sorted in
descending order using a monomial ordering where each term is stored as a
pair, a coefficient and an exponent vector.  If we use this for division,
and we subtract polynomials using merging of linked lists, the algorithm will
do O(M^2 N) comparisons of monomials and O(M N) coefficient operations.

We will study two data structures, ``geo-buckets'' introduced by Yan in 1996,
and ``pointer heaps'', introduced by Johnson in 1971, which both allow us to
reduce the number of comparisons to O(M N log N).  We will also study
the divisor heap algorithm of Monagan and Pearce which does O(M N log M)
comparisons, which is faster when the divisor is small.

Other practical considerations to improve the efficiency of polynomial 
multiplication and division include encoding monomials x^i y^j z^k in an
integer in such a way that monomial comparisons and multiplications can
be done using one
machine integer comparison and addition respectively.