MITACS Seminar Series on Mathematics of Computer Algebra and Analysis

Fast and Small: Multiplying Polynomials without Extra Space

Daniel Roche, University of Waterloo.

Friday July 24th, 2009, at 4:15pm in the IRMACS theatre.

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.