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

To access solutions, please obtain an access code from Cambridge University Press at the Lecturer Resources page for my book (registration required) and then sign up to scipython.com providing this code.