Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6869001 | Computational Statistics & Data Analysis | 2016 | 16 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Huon Wilson, Uri Keich,