
What is the right data structure to use for polynomial division?Michael Monagan, CECM, SFU
Abstract: 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. 