from
The Free On-line Dictionary of Computing (8 July 2008)
Fast Fourier Transform
FFT
<algorithm> (FFT) An {algorithm} for computing the {Fourier
transform} of a set of discrete data values. Given a finite
set of data points, for example a periodic sampling taken from
a real-world signal, the FFT expresses the data in terms of
its component frequencies. It also solves the essentially
identical inverse problem of reconstructing a signal from the
frequency data.
The FFT is a mainstay of {numerical analysis}. Gilbert Strang
described it as "the most important algorithm of our
generation". The FFT also provides the asymptotically fastest
known algorithm for multiplying two {polynomials}.
Versions of the algorithm (in {C} and {Fortran}) can be found
on-line from the GAMS server here
(http://gams.nist.gov/cgi-bin/gams-serve/class/J1.html).
["Numerical Methods and Analysis", Buchanan and Turner].
(1994-11-09)