Fast Fourier Transform
<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 realworld 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 online from the GAMS
server here.
["Numerical Methods and Analysis", Buchanan and Turner].
(19941109)
Nearby terms:
Fast ATA2 « Faster LEX « Fast Ethernet « Fast
Fourier Transform » Fast Packet » Fast Page Mode
Dynamic Random Access Memory » Fast SCSI
