### fast Fourier transform

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

**Fast Fourier transform** (**FFT**) can refer to any of a number of
algorithms that calculate a **discrete Fourier transform** (**DFT**)
more efficiently than the obvious 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, reducing
weeks of required CPU to seconds or 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 answer, carrying out the full calculation 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 work is identical to the DFT, and the word
"inverse" is often skipped. 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*)
http://en.wikipedia.org/wiki/Fast_Fourier_transform

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

**Referenced by:**

Fast Fourier Transform Telescope

Fourier transform

imaging Fourier transform spectroscopy (IFTS)

numerical analysis

spectral density

index