The 1D FFT in explicit detail I

• 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

Previous slide

Next slide

Back to first slide

View graphic version