In this exercise, we show how the Fast Fourier Transform is equivalent to a certain matrix factorization. Let
c = (c0, c1... ,c7)T
be vector of Fourier coefficients, and let
f(k) = (f0(k), f1(k),..., f7(k)T, k = 0,1,2,3,
be vectors containing the coefficients defined in the reconstruction algorithm Example 5.64.
(a) Show that
f(0) = M0c,f(1) = M1f(0)
f(2) = M2f(1),f = f(3) = M3f(2),
where M0, M1, M2, M3 are 8 × 8 matrices. Write down their explicit forms.
(b) Explain why the matrix product F8 = M3M2M1M0 reproduces the Fourier matrix derived in Exercise 5.7.9. Check the factorization directly.
(c) Write down the corresponding matrix factorization for the direct algorithm of Example 5.63.