The Design and Implementation of FFTW3

Top Cited Papers

24 January 2005

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE

Vol. 93 (2) , 216-231
https://doi.org/10.1109/jproc.2004.840301

Abstract

FFTW is an implementation of the discrete Fourier transform (DFT) that adapts to the hardware in order to maximize performance. This paper shows that such an approach can yield an implementation that is competitive with hand-optimized libraries, and describes the software structure that makes our current FFTW3 version flexible and adaptive. We further discuss a new algorithm for real-data DFTs of prime size, a new way of implementing DFTs by means of machine-specific single-instruction, multiple-data (SIMD) instructions, and how a special-purpose compiler can derive optimized implementations of the discrete cosine and sine transforms automatically from a DFT algorithm.

Keywords

This publication has 49 references indexed in Scilit:

Cache-oblivious algorithms
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2003
Architecture independent short vector FFTs
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
A Blocking Algorithm for FFT on Cache-Based Processors
Published by Springer Nature ,2001
Transposing a matrix on a vector computer
Parallel Computing, 1995
An improved fast Fourier transform algorithm using mixed frequency and time decimations
IEEE Transactions on Acoustics, Speech, and Signal Processing, 1988
On computing the split-radix FFT
IEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
On Computing the Discrete Fourier Transform
Mathematics of Computation, 1978
Algorithm 513: Analysis of In-Situ Transposition [F1]
ACM Transactions on Mathematical Software, 1977
An algorithm for computing the mixed radix fast Fourier transform
IEEE Transactions on Audio and Electroacoustics, 1969
Discrete Fourier transforms when the number of data samples is prime
Proceedings of the IEEE, 1968