fast fourier transform

1 definition found

fast fourier transform - Free On-line Dictionary of Computing (26 May 2007) :

  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)