Time-space efficient algorithms for computing convolutions and related problems

AbstractIn this paper, we consider the related problems of convolution and polynomial multiplication and show the existence of a spectrum of algorithms that clearly illustrate the trade-off between time and space inherent in these problems. We model high speed algorithms for these problems with a graph and then play the well-known pebble game on the graph representations to obtain time-space efficient pebbling strategies. For convolving together two n element vectors, we present strategies using time T = O(n2log2SS), where space S can be chosen to lie anywhere in the range 1 ≤ S ≤ n. The methods are shown to be optimal over all fast Fourier transform based algorithms, and come close to meeting the lower bound T = Ω(n2S) that must be satisfied by any algorithm solving the problem. Central to the derivation of these time-space efficient pebbling strategies is a new recursive convolution algorithm, which is of interest because it makes two (rather than three) recursive calls to solve subproblems of half the size