Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Jörn Schumacher and Markus Püschel (Proc. IEEE Workshop on Signal Processing Systems (SIPS), pp. 1-6, 2014)
High-performance sparse fast Fourier transforms
Preprint (1.2 MB)
Published paper (link to publisher)
Bibtex
The sparse fast Fourier transform (SFFT) is a recent novel algorithm to compute discrete Fourier transforms on signals with a sparse frequency domain with an improved asymptotic runtime. Reference implementations exist for different variants of the algorithm and were already shown to be faster than state-of-the-art FFT implementations in cases of sufficient sparsity. However, to date the SFFT has not been carefully optimized for modern processors. In this paper, we first analyze the performance of the existing SFFT implementations and discuss possible improvements. Then we present an optimized implementation. We achieve a speedup of 2-5 compared to the existing code and an efficiency that is competitive to high-performance FFT libraries.
Keywords: Fast Fourier TransformMore information: