Accurate pairwise convolutions of non-negative vectors via FFT

Huon Wilson and Uri Keich

Computational Statistics & Data Analysis, 2016, vol. 101, issue C, 300-315

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.

Keywords: Accuracy–speed tradeoff; Convolution; Distribution on a lattice; Fast Fourier transform; Roundoff error (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167947316300536
Full text for ScienceDirect subscribers only.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:csdana:v:101:y:2016:i:c:p:300-315

DOI: 10.1016/j.csda.2016.03.010

Access Statistics for this article

Computational Statistics & Data Analysis is currently edited by S.P. Azen

More articles in Computational Statistics & Data Analysis from Elsevier
Bibliographic data for series maintained by Catherine Liu ().