Fast Fourier transform

The Fast Fourier transform (FFT) is an efficient algorithm to calculate the discrete Fourier transform (DFT).

Note

The Fourier transform is related to the Fourier series, which was mentioned in the previous chapter—Chapter 5, Working with Matrices and ufuncs. The Fourier series represents a signal as a sum of sine and cosine terms.

FFT improves on more naïve algorithms and is of order O(N log N). DFT has applications in signal processing, image processing, solving partial differential equations, and more. NumPy has a module called fft that offers FFT functionality. Many functions in this module are paired; for those functions, another function does the inverse operation. For instance, the fft() and ifft() function form such a pair.