A fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many different FFT algorithms involving a wide range of mathematics, from simple complex-number arithmetic to group theory and number theory; this article gives an overview of the available techniques and some of their general properties, while the specific algorithms are described in subsidiary articles linked below.
The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields (see discrete ...