The FFT: history and libraries
Optional · supplementary note 2 of 2 for IP 04 · Filtering in the Frequency Domain. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
The FFT is older than computers, and modern libraries go far beyond the textbook algorithm.
Heideman, Johnson and Burrus, “Gauss and the history of the fast Fourier transform” [5]. A historical review tracing FFT-style algorithms back to Gauss’s unpublished work around 1805 and through many rediscoveries before 1965. Main takeaway: the algorithmic idea is simple and was found many times; what changed in 1965 was that digital computers made it matter.
Modern libraries go much further than the textbook radix-2 algorithm. FFTW, described by Frigo and Johnson [6], handles arbitrary sizes, chooses among many algorithms at run time by measuring which is fastest on the actual machine, and generates its small “codelet” kernels automatically. In practice, sizes whose prime factors are small (2, 3, 5, 7) are fast; large primes are slower. scipy.fft.next_fast_len returns a good padded size.
References
- R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 4. publisher page
- C. E. Shannon, “Communication in the presence of noise,” Proceedings of the IRE, vol. 37, no. 1, pp. 10–21, 1949. doi
- M. Unser, “Sampling—50 years after Shannon,” Proceedings of the IEEE, vol. 88, no. 4, pp. 569–587, 2000. doi
- J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Mathematics of Computation, vol. 19, no. 90, 1965. doi
- M. T. Heideman, D. H. Johnson and C. S. Burrus, “Gauss and the history of the fast Fourier transform,” IEEE ASSP Magazine, vol. 1, no. 4, pp. 14–21, 1984. doi
- M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proceedings of the IEEE, vol. 93, no. 2, 2005. doi
- A. V. Oppenheim and J. S. Lim, “The importance of phase in signals,” Proceedings of the IEEE, vol. 69, no. 5, 1981. doi
- A. V. Oppenheim, R. W. Schafer and T. G. Stockham, “Nonlinear filtering of multiplied and convolved signals,” Proceedings of the IEEE, vol. 56, no. 8, pp. 1264–1291, 1968. doi
- M. Mathieu, M. Henaff and Y. LeCun, “Fast training of convolutional networks through FFTs,” arXiv:1312.5851, 2013. arXiv
- L. Chi, B. Jiang and Y. Mu, “Fast Fourier convolution,” Advances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020. proceedings
- Y. Rao, W. Zhao, Z. Zhu, J. Lu and J. Zhou, “Global filter networks for image classification,” NeurIPS, 2021. arXiv
- N. Rahaman, A. Baratin, D. Arpit, F. Draxler, M. Lin, F. A. Hamprecht, Y. Bengio and A. Courville, “On the spectral bias of neural networks,” ICML, 2019. arXiv
- Z.-Q. J. Xu, Y. Zhang and T. Luo, “Overview frequency principle/spectral bias in deep learning,” arXiv:2201.07395, 2022. arXiv
- Z. Li, N. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart and A. Anandkumar, “Fourier neural operator for parametric partial differential equations,” arXiv:2010.08895, 2020. arXiv
- N. Kovachki, Z. Li, B. Liu, K. Azizzadenesheli, K. Bhattacharya, A. Stuart and A. Anandkumar, “Neural operator: Learning maps between function spaces,” Journal of Machine Learning Research, vol. 24, 2023. arXiv
- K. Xu, M. Qin, F. Sun, Y. Wang, Y.-K. Chen and F. Ren, “Learning in the frequency domain,” CVPR, 2020. arXiv
- R. Zhang, “Making convolutional networks shift-invariant again,” ICML, 2019. arXiv
- T. Karras, M. Aittala, S. Laine, E. Härkönen, J. Hellsten, J. Lehtinen and T. Aila, “Alias-free generative adversarial networks,” arXiv:2106.12423, 2021. arXiv
- J. Frank, T. Eisenhofer, L. Schönherr, A. Fischer, D. Kolossa and T. Holz, “Leveraging frequency analysis for deep fake image recognition,” ICML, 2020. arXiv
- M. Tancik, P. P. Srinivasan, B. Mildenhall, S. Fridovich-Keil, N. Raghavan, U. Singhal, R. Ramamoorthi, J. T. Barron and R. Ng, “Fourier features let networks learn high frequency functions in low dimensional domains,” arXiv:2006.10739, 2020. arXiv
- NumPy developers, “numpy.angle,” NumPy reference documentation, accessed 5 November 2026. API documentation.