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 handoptimized 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.
Keywords
CompilerComputer scienceSIMDImplementationSineDiscrete cosine transformPrime (order theory)Trigonometric functionsSoftwareDiscrete Fourier transform (general)Sine and cosine transformsFast Fourier transformSoftware implementationAlgorithmParallel computingComputer engineeringFourier transformProgramming languageFourier analysisMathematicsArtificial intelligence
Affiliated Institutions
Related Publications
The Effect of Cold-Work Distortion on X-Ray Patterns
With modern experimental technique, it is possible to measure a peak shape with sufficient accuracy to justify an interpretation based on the precise shape of the reflection. Th...
Improved time bounds for near-optimal sparse Fourier representations
•We study the problem of finding a Fourier representation <b>R </b>of <i>m</i> terms for a given discrete signal <b>A</b> of length<i> N</i>. The Fast Fourier Transform (FFT) ca...
Optuna
The purpose of this study is to introduce new design-criteria for next-generation hyperparameter optimization software. The criteria we propose include (1) define-by-run API tha...
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
This paper proves best known guarantees for exact reconstruction of a sparse signal f from few non-adaptive universal linear measurements. We consider Fourier measurements (rand...
The Capacity of Linear Channels with Additive Gaussian Noise
The standard method of computing the mutual information between two stochastic processes with finite energy replaces the processes with their Fourier coefficients. This procedur...
Publication Info
- Year
- 2005
- Type
- article
- Volume
- 93
- Issue
- 2
- Pages
- 216-231
- Citations
- 4992
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
4992
OpenAlex
Cite This
Matteo Frigo,
Steven G. Johnson
(2005).
The Design and Implementation of FFTW3.
Proceedings of the IEEE
, 93
(2)
, 216-231.
https://doi.org/10.1109/jproc.2004.840301
Identifiers
- DOI
- 10.1109/jproc.2004.840301