Heap-Based Algorithms for Sparse Polynomial Arithmetic
Roman Pearce, CECM, SFU
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.