MA332 lecture notes, Fall 1998
Week 11 Thursday

Topics: discrete Fourier transform  (dft)
        fast Fourier transform (fft)

Big picture
-----------

1) start with the continuous Fourier transform.
2) discretize in time
3) discretize in frequency
4) develop the Fast Fourier Transform


DFT
---

Write the DFT using W = exp(2Pi i/N)

              N-1
      H_n = sum    W^nk h_k
              k=0

How long does it take to calculate one of these?

1) evaluate h(t) at N places
2) for each of N values of H_n,
      add up N terms, where each term is h_n * a power of W

Time proportional to N^2.

We can speed things up a bit by being smart about the
calculation of the W terms.

Build a matrix of Ws and multiply by the sequence of h_n.

That's nice, but we can get an even bigger speedup from
the following relationship.

    H_n = Even_n + W^n * Odd_n

Where Even_n is the DFT of the even elements of h_n,
Odd_n is the DFT of the odd elements of h_n.

Note: since Even and Odd are half the length of H_n, we
have to repeat them in order to get all the elements we need.

Is this faster?  Take N=64.

64x64 matrix mult is roughly N^2 mults and N^2 additions.
= 4096 mult/adds

2 32x32 matrix mults is = 2048 mult/adds, plus 64 mult adds
to zip up the halves.

   Factor of two savings!

Even neater, we can apply the technique recursively, so

     1 N problem becomes
     2 N/2 problems becomes
     4 N/4 problems becomes
     8 N/8 problems, etc.

     until N/something = 1, at which point H=h.

Stitching things back up takes O(n) work at every level,
and there are logN levels, so the total work is O(NlogN),
which is way better than N^2!