Topics in Comptuter Algebra: II
Algorithms and data structures for sparse polynomial multiplication and division.
Michael Monagan, Department of Mathematics, Simon Fraser University.
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.