course | course_year | question_number | tags | title | year | |||
---|---|---|---|---|---|---|---|---|
Numerical Analysis |
II |
106 |
|
Paper 3, Section II, D |
2012 |
The inverse discrete Fourier transform
$$\mathbf{x}=\mathcal{F}{n}^{-1} \mathbf{y}, \quad \text { where } \quad x{l}=\sum_{j=0}^{n-1} \omega_{n}^{j l} y_{j}, \quad l=0, \ldots, n-1$$
Here,
(i) Show how to assemble
$$\mathbf{x}^{(E)}=\mathcal{F}{m}^{-1} \mathbf{y}^{(E)}, \quad \mathbf{x}^{(O)}=\mathcal{F}{m}^{-1} \mathbf{y}^{(O)}$$
are already known.
(ii) Describe the Fast Fourier Transform (FFT) method for evaluating
(iii) Find the costs of the FFT method for
(iv) For
(a)
(b)