Discrete Fourier transform

Summary

The discrete Fourier transform turns a finite list of $N$ complex numbers into another list of $N$ numbers, its frequency components. It is the Fourier transform of the finite cyclic group $\Z / N\Z$, built from the $N$-th roots of unity. It is invertible, it preserves energy up to the factor $N$, and it turns cyclic convolution into pointwise multiplication. The fast Fourier transform computes it in $O(N \log N)$ operations, which makes it one of the most used algorithms in numerical computing and signal processing. See the definition.