FFTW

Infobox Software
name = FFTW
logo =


caption =
author =
developer = Matteo Frigo and Steven G. Johnson
released =
latest release version = 3.1.2
latest release date = 5 July 2006
latest preview version =
latest preview date =
operating system =
platform =
language = C
genre = Numerical software
license = GPL, commercial
website = [http://www.fftw.org 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. [Frigo, M. and Johnson, S. G., " [http://www.fftw.org/fftw-paper-ieee.pdf The design and implementation of FFTW3] ", "Proceedings of the IEEE", 93(2), February 2005, 216 - 231. DOI:10.1109/JPROC.2004.840301.]

FFTW is known as the fastest free software implementation of the Fast Fourier transform (FFT) algorithm (upheld by regular benchmarks [Homepage, second paragraph [http://www.fftw.org/] , and benchmarks page [http://www.fftw.org/benchfft/] ] ). 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 supporting a variety of algorithms and choosing the one it estimates or measures to be preferable in the particular circumstances. 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 sufficiently 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 has limited support for "Out of order transforms" (using the MPI version). The data reordering incurs an overhead, which for in-place transforms of arbitrary size and dimension is non-trivial to avoid. It is undocumented for which transforms this overhead is significant.

FFTW is licensed under the GNU General Public License. It is also licensed commercially by MIT and is used in the commercial Matlab [ [http://www.mathworks.com/company/newsletters/news_notes/clevescorner/winter01_cleve.html Faster Finite Fourier Transforms: MATLAB 6 incorporates FFTW] ] 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. While the library itself is C, the code is actually generated from a program called 'genfft', which is written in Objective Caml. [http://www.fftw.org/faq/section2.html#languages "FFTW FAQ"] ]

In 1999, FFTW won the J. H. Wilkinson Prize for Numerical Software.

References