Accurate pairwise convolutions of non-negative vectors via FFT

A novel method is presented for fast convolution of a pair of probability mass functions defined on a finite lattice with guaranteed accuracy of all computed values. This method, called aFFT-C (accurate FFT convolution), utilizes the Fast Fourier Transform (FFT) for the gain in speed, but relying on a rigorous analysis of the propagation of roundoff error, it can detect and circumvent the accumulation of this numerical error that is otherwise inherent to the Fourier transform. In the worst case scenario aFFT-C's execution time is on par with the accurate naive convolution but in a typical application it is comparable with a direct FFT-based convolution (FFT-C). The properties of the proposed algorithm are demonstrated both theoretically and empirically.