Optimizing Sparse Polynomial Multiplication
Roman Pearce, CECM, SFU.
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.