DocumentCode :
190602
Title :
High-performance sparse fast Fourier transforms
Author :
Schumacher, Jorn ; Puschel, Markus
Author_Institution :
CERN, Geneva, Switzerland
fYear :
2014
fDate :
20-22 Oct. 2014
Firstpage :
1
Lastpage :
6
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Signal Processing Systems (SiPS), 2014 IEEE Workshop on
Conference_Location :
Belfast
Type :
conf
DOI :
10.1109/SiPS.2014.6986055
Filename :
6986055
Link To Document :
بازگشت