Fast Fourier Transform
(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.
["Numerical Methods and Analysis", Buchanan and Turner].