Optimizing Sparse Polynomial Multiplication

Roman Pearce, CECM, SFU.


Wednesday October 22nd, 2008 at 3:30pm in K9509.


Abstract:
In this talk we will examine a method for multiplying sparse polynomials
that is based on a binary heap.  The product of two sparse polynomials
with N and M terms can have N*M terms, so our task is to construct and
sort and merge all pairwise products of terms in an efficient manner.
A number of algorithms share the best-known asymptotic complexity:
O(N M log min(M,N)), however this ignores the significant differences in
design that can ultimately determine performance.  The binary heap
method is often ten times faster in practice.  In this talk we will
describe the optimizations that allow us to achieve this performance.