R. Robinson 11/99, 4/01
Do one of either Lab 9 or Lab 10.
1. Write a Matlab routine to implement the DFT using matrix multiplication (the O(N2) algorithm). Be as efficient as you like as long as the heart of the routine is matrix multiplication. You may use the online Numerical Recipes book as a reference
2. Test your routine on some inputs v of various sizes, say 8, 64, 256, 1024 or larger. How large dous the input need to get before the direct method is impractical?
3. If you call your output w you can display it by graphing |w(i)|2 (the power spectrum). Try various choices for v including a square wave, various Gaussians v(t)=e(t^2)/s, sin waves of various frequencies, and random vectors.
4. While trying your routine, try out Matlab's built in fft routine. How does it compare in speed to yours?
5. Choose one of the following options:
(a) Implement the Cooley-Tukey radix 2 FFT algorithm of order 16.
(b) Implement the Danielson-Lanczos algorithm of order 2n
using recursion.