course | course_year | question_number | tags | title | year | |||
---|---|---|---|---|---|---|---|---|
Numerical Analysis |
II |
105 |
|
Paper 4, Section II, E |
2018 |
The inverse discrete Fourier transform
$$\boldsymbol{x}=\mathcal{F}{n}^{-1} \boldsymbol{y}, \quad \text { where } \quad x{\ell}=\sum_{j=0}^{n-1} \omega_{n}^{j \ell} y_{j}, \quad \ell=0, \ldots, n-1$$
Here,
(a) Show how to assemble
$$\boldsymbol{x}^{(\mathrm{E})}=\mathcal{F}{m}^{-1} \boldsymbol{y}^{(\mathrm{E})}, \quad \boldsymbol{x}^{(\mathrm{O})}=\mathcal{F}{m}^{-1} \boldsymbol{y}^{(\mathrm{O})}$$
are already known.
(b) Describe the Fast Fourier Transform (FFT) method for evaluating
(c) Find the cost of the FFT method for
(d) For