
MITACS Seminar Series on Mathematics of Computer Algebra and AnalysisFast and Small: Multiplying Polynomials without Extra SpaceDaniel Roche, University of Waterloo.
Abstract: Multiplication of univariate polynomials and multiprecision integers is one of the most basic, wellstudied, and widelyused operations in mathematical computing. While asymptotic time complexity correlates with performance, it is wellknown 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 subquadratic time complexity for multiplication currently require at least O(n) auxiliary storage space for their implementation, producing an apparent time/space tradeoff. Two new algorithms are presented which achieve the same time complexity as Karatsuba's and FFTbased algorithms (respectively) without requiring the use of an auxiliary array for temporary storage. While the FFTbased approach only applies under certain conditions, the Karatsubalike method is general and is the first algorithm to break the O(n^2) timespace barrier, under a practical space complexity model which allows both reads and writes to the output array. A lowlevel C language implementation is also presented which demonstrates the practical effectiveness of these new approaches. 