FFT
       Final Form Text
       

Fast Fourier Transform
FFT

    (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>.

   ["Numerical Methods and Analysis", Buchanan and Turner].

   (1994-11-09)