The Design and Implementation of FFTW3

by Matteo Frigo and Steven G. Johnson.

Proceedings of the IEEE, vol. 93, no. 2, pp. 216--231 (2005)
[Full text]


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 ``SIMD'' instructions, and how a special-purpose compiler can derive optimized implementations of the discrete cosine and sine transforms automatically from a DFT algorithm.

This page maintained by: Matteo Frigo. Last updated: Sun Jun 21 09:29:38 2009