Basic HTML version of Foils prepared April 22 2000

Foil 8 The 1D FFT in explicit detail I

From Parallel FFT and use in PDE Solvers Computational Science Class CPS615 -- Winter Semester 2000. by Geoffrey C. Fox
The basic discrete FFT is:
This in a naïve analysis takes O(N2) complex floating point additions and multiplications. However we can group terms together to reduce this to a time O(NlogN).
This can be done in many ways and starts with a factorization N=N1N2 (product of integers) and a recursive iteration of factorization to values N1, N2 where special algorithms exist.
  • The power of this general approach is made clear at FFTW web site
  • eptools web site describes case N1=2, 4 and a general prime

© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Mon Apr 24 2000