Search in: Word
Vietnamese keyboard: Off
Virtual keyboard: Show
Computing (FOLDOC) dictionary
Fast Fourier Transform
Jump to user comments
algorithm (FFT) An algorithm for computing the Fouriertransform 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.