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

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

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

$$\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 $\mathbf{x}$, and draw a relevant diagram for $n=8$.

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

(iv) For $n=4$ use the FFT method to find $\mathbf{x}=\mathcal{F}_{4}^{-1} \mathbf{y}$ when:

(a) $\mathbf{y}=(1,1,-1,-1)$,

(b) $\mathbf{y}=(1,-1,1,-1)$.