The inverse discrete Fourier transform $\mathcal{F}_{n}^{-1}: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ is given by the formula

$$\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, $\omega_{n}=\exp \frac{2 \pi i}{n}$ is the primitive root of unity of degree $n$ and $n=2^{p}, p=1,2, \ldots$

(a) Show how to assemble $\boldsymbol{x}=\mathcal{F}_{2 m}^{-1} \boldsymbol{y}$ in a small number of operations if the Fourier transforms of the even and odd parts of $\boldsymbol{y}$,

$$\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 $\boldsymbol{x}$, and draw a diagram to illustrate the method for $n=8$.

(c) Find the cost of the FFT method for $n=2^{p}$ (only multiplications count).

(d) For $n=4$ use the FFT method to find $\boldsymbol{x}=\mathcal{F}_{n}^{-1} \boldsymbol{y}$ when: (i) $\boldsymbol{y}=(1,-1,1,-1)$, (ii) $\boldsymbol{y}=(1,1,-1,-1)$.