Original version
Journal of Open Source Software (JOSS). 2019, 4 (36):1340, DOI: https://doi.org/10.21105/joss.01340
Abstract
The fast Fourier transform (FFT) is an algorithm that efficiently computes the discrete Fourier transform. Since the dawn of our digital society, the FFT has permeated to the heart of everyday life applications involving audio, image, and video processing. The importance of the FFT extends beyond signal processing into scientific computing because it diagonalizes the Poisson operator, which is ubiquitous in descriptions of electromagnetism, gravitation, acoustic and elastic waves, potential flow in fluids, stress in solids, Hamiltonians of the Schroedinger’s equation for probability distribution of electrons in quantum mechanics, and diffusion of internal energy, chemical species, and momentum. The FFT has been named the most important numerical algorithm of our time by Professor Gilbert Strang (Strang, 1994).