Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 2 / 39A (Numerical Analysis)

Use the printed unnormalized inverse discrete Fourier transform, with positive exponent: $x_{\ell }={\sum }_j{\omega }_n^{j\ell }{y}_j$. Its natural domain and codomain are ${\mathbb{C}}^n$; the printed real-to-real designation is not literal, as the first example below has complex output. There is no factor $1/n$ in the convention of this question.

Separate even and odd indices, using ${\omega }_{2m}^2={\omega }_m$. ThenThe second identity uses ${\omega }_{2m}^m=-1$. Each FFT butterfly uses one shared twiddle-factor product and two additions, so assembly costs $m$ multiplications and $2m$ additions.

The radix-two Fast Fourier transform recursively splits the input into even and odd subsequences until length one, then assembles the transforms using the FFT butterfly identities. For $n=8$, the recursive leaf order is the bit-reversed order $y_0,y_4,y_2,y_6,y_1,y_5,y_3,y_7$. The three assembly stages have block sizes two, four and eight. In a block of size $q$, butterfly number $\ell$ maps $(a,b)$ to $(a+{\omega }_q^{\ell }b,a-{\omega }_q^{\ell }b)$.

Counting every twiddle-factor product, including multiplication by one, the recurrence is $M(n)=2M(n/2)+n/2$, with $M(1)=0$. Each of the $p$ levels costs $n/2$ products, soIf products by one are omitted, every block saves one product. There are $n-1$ blocks across all stages, giving $M_{\mathrm{nonunit}}(n)=\frac{n}{2}{\log }_{2}n-n+1$. The conventional complexity in either convention is $O(n\log n)$; additional savings are possible by treating multiplication by $\pm i$ as component swaps and sign changes.

For $y=(1,1,-1,-1)$, the even and odd subsequences are both $(1,-1)$ and each length-two inverse discrete Fourier transform is $(0,2)$. Since ${\omega }_4=i$, the FFT butterfly givesFor $y=(1,-1,1,-1)$, the even transform is $(2,0)$ and the odd transform is $(-2,0)$. The same assembly gives