FFT, eine Klasse numerischer Algorithmen zur Auswertung der diskreten Fourier-Transformation (vgl. auch diskrete Fourier-Analyse).

Es sei f : ℝ ↠ ℂ L-periodisch und an den Stützstellen x_n = nL/N, n = 0,…,N − 1, bekannt. Die diskrete Fourier-Transformation liefert mit \begin{eqnarray}\begin{array}{cc}{c}_{k}=\frac{1}{N}\displaystyle \sum _{n=0}^{N-1}{f}_{n}{e}^{-2i\pi nk/N},\end{array}\end{eqnarray}k = 0,…,N − 1, Näherungen für die FourierKoeffizienten von f. Für N = N₁N₂ gilt \begin{eqnarray}{c}_{k}=\frac{1}{{N}_{1}}\displaystyle \sum _{n=0}^{{N}_{1}-1}{\gamma }_{mn}{e}^{-2i\pi nk/N}\end{eqnarray} falls \begin{eqnarray}\begin{array}{cc}{\gamma }_{mn}=\frac{1}{{N}_{2}}\displaystyle \sum _{j=0}^{{N}_{2}-1}{f}_{n+j{N}_{1}}{e}^{-2i\pi jm/{N}_{2}}\end{array}\end{eqnarray} und 0 ≤ m < N₂, 0 ≤ n < N₁, k = m + nN₂. Diese Zerlegung ist Grundlage verschiedener effizienter Berechnungsverfahren, die als schnelle FourierTransformationen bezeichnet werden.

Ist N₂ = N₂₁N₂₂, so läßt sich dieses Verfahren erneut zur Bestimmung von (2) anwenden. Dies führt für N = 2^s = 2 · 2^s−1 = 2 · (2 · 2^s−2) = … zu folgendem rekursiven Algorithmus: \begin{eqnarray}\begin{array}{rll}{\gamma }_{0,n}^{s} & = & {f}_{n}\,\,\text{f}\mathrm{\ddot{u}}\text{r}\,\,\,0\le n\le N-1,\\ {\gamma }_{m,n}^{r-1} & = & \frac{1}{2}({\gamma }_{m,n}^{r}+{\alpha }_{mr}{\gamma }_{m,n+{2}^{r-1}}^{r})\,\,\text{f}\mathrm{\ddot{u}}\text{r}\,0\le n\le {2}^{r-1},\\ {\gamma }_{m+{2}^{s-r},n}^{r-1} & = & \frac{1}{2}({\gamma }_{m,n}^{r}-{\alpha }_{mr}{\gamma }_{m,n+{2}^{r-1}}^{r})\,\,\text{f}\mathrm{\ddot{u}}\text{r}\,0\le m\le {2}^{s-r},\end{array}\end{eqnarray} wobei α_mr = exp(−imπ2^r−s). Dieser Algorithmus erfordert ungefähr N log₂(N/2) Rechenoperationen, während eine Berechnung mit Formel (1) etwa N² Operationen verlangt.