FFTW
Encyclopedia
FFTW, for "Fastest Fourier Transform in the West", is a software library
for computing discrete Fourier transform
s (DFTs), developed by Matteo Frigo and Steven G. Johnson at the Massachusetts Institute of Technology
.
FFTW is known as the fastest free software
implementation of the Fast Fourier transform
(FFT) algorithm
(upheld by regular benchmarks
). 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: it chooses the one (a particular decomposition of the transform into smaller transforms) it estimates or measures to be preferable in the particular circumstances. It works best on arrays of sizes with small prime factor
s, with powers of two
being the optimal sizes and a (large) prime
size being the worst case [but still O
(n log n)]. To decompose transforms of composite
sizes into smaller transforms, it chooses among several variants of the Cooley–Tukey FFT algorithm (corresponding to different factorizations and/or different memory-access patterns), while for prime sizes it uses either Rader's
or Bluestein's FFT algorithm
. Once the transform has been broken up into subtransforms of sufficiently small sizes, FFTW uses hard-coded unrolled
FFTs for these small sizes that were produced (ahead of time, not at run time) by code generation
; these routines use a variety of algorithms including Cooley–Tukey variants, Rader's algorithm, and prime-factor FFT algorithm
s.
For a sufficiently large number of repeated transforms it is advantageous to use FFTW's 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
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 '
.
In 1999, FFTW won the J. H. Wilkinson Prize for Numerical Software
.
Library (computer science)
In computer science, a library is a collection of resources used to develop software. These may include pre-written code and subroutines, classes, values or type specifications....
for computing discrete Fourier transform
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
s (DFTs), developed by Matteo Frigo and Steven G. Johnson at the Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
.
FFTW is known as the fastest free software
Free software
Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
implementation of the Fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
(FFT) algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
(upheld by regular benchmarks
Benchmark (computing)
In computing, a benchmark is the act of running a computer program, a set of programs, or other operations, in order to assess the relative performance of an object, normally by running a number of standard tests and trials against it...
). It can compute transforms of real- and complex
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
-valued arrays of arbitrary size and dimension in O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n log n) time.
It does this by supporting a variety of algorithms: it chooses the one (a particular decomposition of the transform into smaller transforms) it estimates or measures to be preferable in the particular circumstances. It works best on arrays of sizes with small prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s, with powers of two
Power of two
In mathematics, a power of two means a number of the form 2n where n is an integer, i.e. the result of exponentiation with as base the number two and as exponent the integer n....
being the optimal sizes and a (large) prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
size being the worst case [but still O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n log n)]. To decompose transforms of composite
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
sizes into smaller transforms, it chooses among several variants of the Cooley–Tukey FFT algorithm (corresponding to different factorizations and/or different memory-access patterns), while for prime sizes it uses either Rader's
Rader's FFT algorithm
Rader's algorithm is a fast Fourier transform algorithm that computes the discrete Fourier transform of prime sizes by re-expressing the DFT as a cyclic convolution...
or Bluestein's FFT algorithm
Bluestein's FFT algorithm
Bluestein's FFT algorithm , commonly called the chirp z-transform algorithm , is a fast Fourier transform algorithm that computes the discrete Fourier transform of arbitrary sizes by re-expressing the DFT as a convolution...
. Once the transform has been broken up into subtransforms of sufficiently small sizes, FFTW uses hard-coded unrolled
Loop unwinding
Loop unwinding, also known as loop unrolling, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size...
FFTs for these small sizes that were produced (ahead of time, not at run time) by code generation
Automatic programming
In computer science, the term automatic programming identifies a type of computer programming in which some mechanism generates a computer program to allow human programmers to write the code at a higher abstraction level....
; these routines use a variety of algorithms including Cooley–Tukey variants, Rader's algorithm, and prime-factor FFT algorithm
Prime-factor FFT algorithm
The prime-factor algorithm , also called the Good–Thomas algorithm , is a fast Fourier transform algorithm that re-expresses the discrete Fourier transform of a size N = N1N2 as a two-dimensional N1×N2 DFT, but only for the case where N1 and N2 are relatively prime...
s.
For a sufficiently large number of repeated transforms it is advantageous to use FFTW's 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
Platform (computing)
A computing platform includes some sort of hardware architecture and a software framework , where the combination allows software, particularly application software, to run...
. 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
Interleaving
In computer science and telecommunication, interleaving is a way to arrange data in a non-contiguous way to increase performance.It is typically used:* In error-correction coding, particularly within data transmission, disk storage, and computer memory....
in memory).
FFTW has limited support for out-of-order transforms (using the MPI
Message Passing Interface
Message Passing Interface is a standardized and portable message-passing system designed by a group of researchers from academia and industry to function on a wide variety of parallel computers...
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
GNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
. It is also licensed commercially by MIT and is used in the commercial Matlab
MATLAB
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
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
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
language, but Fortran
Fortran
Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
and Ada
Ada (programming language)
Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
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 CamlObjective Caml
OCaml , originally known as Objective Caml, is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996...
.
In 1999, FFTW won the J. H. Wilkinson Prize for Numerical Software
J. H. Wilkinson Prize for Numerical Software
The J. H. Wilkinson Prize for Numerical Software is awarded every four years to honor outstanding contributions to the field of numerical software.- Overview :In honour of the outstanding contributions of James H...
.