Fast Fourier Transform definition 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
) 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].