### fast Fourier transform

**(FFT)**
(efficient algorithm for calculating a discrete Fourier transform)

The term, **fast Fourier transform** (**FFT**) can refer
to any of a number of algorithms that calculate a
**discrete Fourier transform** (**DFT**) more efficiently than the
straight-forward method. This is accomplished by arranging the calculations
and using equivalences so some of the early calculations can be
reused. Its use reduces the complexity of the calculation from
O(N²) to O(N log N), making many more potential uses practical,
sometimes reducing weeks of required computation
to seconds or even millennia to weeks.

The *discrete Fourier transform* effectively applies
the Fourier transform to a finite set of
sample results of a function, from an evenly-spaced
set of sample values over an interval.
Assuming the function over that interval
is a single repetition of a periodic function,
it calculates the magnitude of each harmonic,
in effect, the magnitude of the sine waves that
could be individually phased so that summing them would
approximate the original function. Its defining formula is:

N-1
X_{k} = Σ x_{n}e^{-i2πkn/N}
n=0

For N input values, x_{k}, producing N output values,
X_{n}.

A commonly-used FFT algorithm uses a method of combining
DFT results for selections of the input data to produce
the DFT for the combinations of these selections,
carrying out the full calculation by doing this recursively.

The inverse of the DFT (**inverse discrete Fourier transform**, **IDFT**),
creating samples of a function that has a specific set of
harmonics, is also useful. (Applying the inverse does not
entirely "undo" the application of the DFT: phase information is lost.)
In fact, the bulk of the IDFT calculation is identical to that of the DFT,
and in referring to it, the word "inverse" is often skipped, i.e.,
when someone says DFT, they may be referring to the IDFT.
The efficient FFT algorithms also apply, and the terms "FFT" and
"fast Fourier transform" (with no "I" or "inverse" mentioned) are
typically used for this process as well.

(*mathematics,computation*)
**Further reading:**

http://en.wikipedia.org/wiki/Fast_Fourier_transform

http://en.wikipedia.org/wiki/Discrete_Fourier_transform

**Referenced by pages:**

fast folding algorithm (FFA)

Fast Fourier Transform Telescope

Fourier transform

imaging Fourier transform spectroscopy (IFTS)

numerical analysis

spectral correlator

spectral density

Index