MITACS Seminar Series on Mathematics of Computer Algebra and Analysis
Fast and Small: Multiplying Polynomials without Extra Space
Daniel Roche, University of Waterloo.
Abstract: Multiplication of univariate polynomials and multi-precision integers is one of the most basic, well-studied, and widely-used operations in mathematical computing. While asymptotic time complexity correlates with performance, it is well-known that memory usage and cache misses also contribute significantly to the running time of computer programs. Furthermore, in some applications such as embedded systems, physical restrictions on memory can limit the size of possible computations. All algorithms which achieve sub-quadratic time complexity for multiplication currently require at least O(n) auxiliary storage space for their implementation, producing an apparent time/space trade-off. Two new algorithms are presented which achieve the same time complexity as Karatsuba's and FFT-based algorithms (respectively) without requiring the use of an auxiliary array for temporary storage. While the FFT-based approach only applies under certain conditions, the Karatsuba-like method is general and is the first algorithm to break the O(n^2) time-space barrier, under a practical space complexity model which allows both reads and writes to the output array. A low-level C language implementation is also presented which demonstrates the practical effectiveness of these new approaches.