Algorithm Analysis Question

Write out all the steps to compute F12C by the FFT algorithm, using 213 for the numbers and using a = = 6 to generate the Fourier matrix, with 3 7 8 2 11 6 10 1 12 You must demonstrate the recursion down to the n = 3 level, and when you have a 3 by 3 Fourier matrix to multiply by a 3-vector, you should just go ahead and do the multiplication by the traditional algorithm (we can't divide and conquer on a 3 by 3 matrix, anyway). Your job on this exercise is to clearly explain all your steps to obtain the final, correct answer. You absolutely should use FormAndMultiply to check your work and to do the n = 3 level matrix-vector products. Write out all the steps to compute F12C by the FFT algorithm, using 213 for the numbers and using a = = 6 to generate the Fourier matrix, with 3 7 8 2 11 6 10 1 12 You must demonstrate the recursion down to the n = 3 level, and when you have a 3 by 3 Fourier matrix to multiply by a 3-vector, you should just go ahead and do the multiplication by the traditional algorithm (we can't divide and conquer on a 3 by 3 matrix, anyway). Your job on this exercise is to clearly explain all your steps to obtain the final, correct answer. You absolutely should use FormAndMultiply to check your work and to do the n = 3 level matrix-vector products