Source : Free On-Line Dictionary of Computing

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 {polynomial}s.
     
        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)