FFTW
From Wikipedia, the free encyclopedia
| FFTW | |
| Developer: | Matteo Frigo and Steven G. Johnson |
|---|---|
| Latest release: | 3.1.2 / 5 July 2006 |
| Available language(s): | C |
| Use: | Numerical software |
| License: | GPL, commercial |
| Website: | www.fftw.org |
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.[1]
FFTW is known as the fastest free software implementation of the Fast Fourier transform (FFT) algorithm. It can compute transforms of real- and complex-valued arrays of arbitrary size and dimension in O(n log n) time.
It does this by choosing from a variety of algorithms one it estimates or measures to be preferable. It works best on arrays of sizes with small prime factors, with powers of two being the optimal size and a (large) prime size being the worst case.
For a sufficently large number of repeated transforms it is advantageous to use FFTWs ability to choose the fastest algorithm by actually measuring the performance of (some or all of) the supported algorithms on the given array size and platform. These measurements, which the authors call wisdom can be stored in a file or string for later use.
FFTW has a guru interface, that intends to expose as much as possible of the flexibility in the underlying FFTW architecture. This allows among other things multi-dimensional transforms and multiple transforms in a single call (e.g. where the data is interleaved in memory).
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.
 |
This article may contain improper references to self-published sources. The source in dispute is: [2]. Please help improve this article by removing unreliable sources. A self-published source may only be cited as a primary source in an article about the author or source itself and not as an authority. |
There has been some controversy [2] concerning the benchmarks used to determine the speed of FFTW, spurred by Daniel J. Bernstein (the author of the unlicensed FFT library djbfft, which can only compute 1D transforms with a length which is a small integral power of 2, unlike FFTW).
[edit] References
- ^ Frigo, M. and Johnson, S. G., "The design and implementation of FFTW3", Proceedings of the IEEE, 93(2), February 2005, 216 - 231. DOI:10.1109/JPROC.2004.840301.
- ^ a b Bernstein, Daniel. "The art of FFT benchmarking.". February 28, 2000, retrieved December 1, 2006. See also the comp.benchmarks debate following.
