Use this tag for questions related to the fast Fourier transform, an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.
A fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components. Those components are individual sinusoidal oscillations at distinct frequencies each with its own amplitude and phase.
An FFT algorithm computes the discrete Fourier transform (DFT) of a sequence or its inverse (IFFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. A FFT computes such transformations rapidly by factoring the DFT matrix into a product of sparse matrices. As a result, a FFT reduces the complexity of computing the DFT from $O(n^2)$ if one applies the definition of the DFT to $O(n\log n)$ where $n$ is the data size.
Fast Fourier transforms are widely used for many applications in engineering, science, and mathematics.