FFT

Fast Fourier Transform
FFT

   <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} 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)
    

FFT
       Final Form Text