Heap-Based Algorithms for Sparse Polynomial Arithmetic

Roman Pearce, CECM, SFU


Wednesday February 21st, 2007 at 1:30pm in IRMACS 10908.


Abstract: 

This talk is a continuation of Michael Monagan's talk from Feb. 7th.
Algorithms for sparse polynomial arithmetic typically reduce to strategies
for performing an n-ary merge.  For example, to multiply f*g you can
merge the partial products f[i]*g, where f[i] ranges over the terms of f.
Similarly, to divide f by g, one computes the next term q[i]=LT(f)/LT(g)
in the quotient then merges f with -q[i]*g.

In the previous talk we presented two strategies for doing these merges,
both of which are iterative.  That is, the products f[i]*g (or q[i]*g)
were merged with an intermediate object, one after another, until the
result was obtained.  The algorithms differed in that the intermediate
object was either a global array or a "geobucket" structure, which
naturally produces a "divide-and-conquer" approach.  We will review
these two methods and compare them in our implementation.

Another way to perform an n-ary merge is to use a heap of pointers
into the objects being merged, and merge all of them simultaneously.
The heap maintains the maximum element efficiently, and the pointers
increment along the objects being merged.  At each step the largest
term is extracted from the heap, and the next term in that polynomial
is added to the heap.  This requires O(log n) time per term, where n
is the number of polynomials being merged.  The resulting algorithms
build the result one term at a time and use little "working storage",
allowing them to remain efficient even as the size of the problem
grows to fill all available memory.

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