Direct implementation of the discrete Fourier Transform

Question Q6.8.1

Compare the speed of execution of NumPy's np.fft.fft algorithm and that of the direct implementation of the equation

$$ F_k = \sum_{m=0}^{n-1}f_m\exp\left( -\frac{2\pi i m k}{n} \right), \quad k=0,1,2,\cdots, n-1 $$

Hints: treat the direct equation as a matrix multiplication (dot product) of an array of $n$ function values (random ones will do) with the $n \times n$ array with entries $\exp(-2\pi i m k / n)$ ($m, k = 0, 1, \cdots, n-1$). Use IPython's %timeit magic.


Solution Q6.8.1