Title :
High-performance sparse fast Fourier transforms
Author :
Schumacher, Jorn ; Puschel, Markus
Author_Institution :
CERN, Geneva, Switzerland
Abstract :
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 highperformance FFT libraries.
Keywords :
discrete Fourier transforms; software libraries; software performance evaluation; SFFT algorithm; asymptotic runtime improvement; discrete Fourier transforms; high-performance FFT libraries; high-performance sparse fast Fourier transforms; performance analysis; sparse frequency domain; Discrete Fourier transforms; Frequency estimation; Optimization; Probabilistic logic; Runtime; Signal processing algorithms; Vectors; Fast Fourier transform; SIMD processors; Software performance;
Conference_Titel :
Signal Processing Systems (SiPS), 2014 IEEE Workshop on
Conference_Location :
Belfast
DOI :
10.1109/SiPS.2014.6986055