FFTW
From Wikipedia, the free encyclopedia
FFTW, for "Fastest Fourier Transform in the West," is a software library for computing discrete Fourier transforms (DFTs), developed by Matteo Frigo and Steven G. Johnson at the MIT Laboratory for Computer Science.
FFTW is known as the fastest free software implementation of the Fast Fourier transform (FFT) algorithm. FFTW can compute transforms of arbitrarily sized arrays (including prime lengths). It works best on arrays which have sizes which have multiple factors, and uses a variety of algorithms to compute the transform. A particularly strong feature is the ability to run tests on a particular sized array on a particular processor. These tests determine the fastest method to compute the transform, and this knowledge, which the authors call "wisdom" can be stored in a file or string for later use. Given a large number of transforms to be computed, all of the same size, this method can yield a worthwhile gain in speed compared to the default case when FFTW uses a heuristically chosen algorithm.
FFTW can compute multi-dimensional transforms, and multiple transforms in one call (e.g. where the data is interleaved in memory). It handles real and complex valued transforms.
FFTW is licensed under the GNU General Public License. It is also licensed commercially by MIT and is used in the commercial Matlab matrix package for calculating Fast Fourier Transforms (FFTs) - that is, the Matlab functions which compute FFTs are actually based on FFTW. FFTW is written in the C language, but Fortran and Ada interfaces exist, as well as interfaces for a few other languages.
In 1999, FFTW won the J. H. Wilkinson Prize for Numerical Software.
There has been some controversy [1] concerning the benchmarks used to determine the speed of FFTW, spurred by Daniel J. Bernstein (the author of another FFT library, djbfft, which is limited to computing transforms with a length which is a power of 2, unlike FFTW).
[edit] External link
[edit] References
- Bernstein, Daniel. "The art of FFT benchmarking.". February 28, 2000, retrieved December 1, 2006.
