Schnelle Fouriertransformation (FFT)

Um die diskrete Fouriertransformation durchzuführen, genügt es, den Vektor $f$ mit der $N \times N$ -Matrix $F_N$ zu multiplizieren. Dies erfordert (neben den Additionen) $N^2$ Multiplikationen, für große $N$ ein zu hoher Aufwand.
Die schnelle Fouriertransformation beruht darauf, dass man im Fall $N = 2^d$ für ein $d \in \mathbb{N}$ nur $d \cdot N = N \cdot \log_2(N)$ Multiplikationen benötigt, wenn man gewisse Symmetrien ausnutzt. Dies machen wir uns am Beispiel $d = 2$ klar. Dann ist

$$\omega = \exp ( \frac{2 \pi i}{4} ) = \exp ( \frac{\pi}{2} i ) = i.$$

Es ergibt sich für $k = 0, \ldots, 3$

$$\hat{f}_k = f_0 + f_1 i^k + f_2 i^{2 k} + f_3 i^{3 k}$$

$$= f_0 + f_2 (i^2)^k + i^k ( f_1 + f_3 (i^2)^k ).$$

Wir setzen $g = ( f_0 , f_2 )^t$ und $u = ( f_1 , f_3 )^t$ . Dann lässt sich die Gleichung für $\hat{f}_k$ umformen. Für $k \leq 1 = N/2 - 1$ gilt

$$\hat{f}_{k, N} = \hat{g}_{k, N/2} + i^k \hat{u}_{k, N/2} .$$

(Wir haben dabei durch den zusätzlichen Index $N$ bzw. $N/2$ angedeutet, dass es sich um eine diskrete Fouriertransformation im $\mathbb{C}^N$ bzw. $\mathbb{C}^{N/2}$ handelt.)
Für $k = 2$ bzw. $3$ sei $k' = k$    mod $N/2$ . Dann ist $\hat{f}_{k, N} \, = \, \hat{g}_{k', N/2} + i^k \hat{u}_{k', N/2}$ .
Wir haben also Fouriertransformationen in $\mathbb{C}^{N/2}$ und eine anschließende ``Zusammensetzung'' erhalten. Allgemein ergibt sich das folgende rekursive Schema:

$$g (f) = ( f_0 , f_2, f_4, \ldots, f_{N-2} ), u (f) = ( f_1, f_3 , \ldots, f_{N-1} )$$

$$\hat{f}_{k, N} = \widehat{g(f)}_{k \mbox{ \rm mod }N/2 , N/2} + \overline{\omega}^k \widehat{u(f)}_{k \mbox{ \rm mod }N/2, N/2} \quad \quad k = 0, \ldots , N-1.$$

Die Rekursion kann man $d = \log_2(N)$ mal aufrufen. Wir geben hierfür ein Programm in einem Pseudocode an.

FUNCTION FFT( $f,d,\omega$ )
/* $f \in \mathbb{C}^{2^d}$ , $d \in \mathbb{N}_0$ , $\omega = \exp(- 2 \pi \, i/2^d)$ */
$N := 2^d;$

IF (N=1)	THEN	$\hat{f}$	$=$	$f$ ;
	ELSE	$M$	$:=$	N/2;
		$g$	$:=$	$(f_{2k})_{0 \le k \le M-1}$ ;
		$u$	$:=$	$(f_{2k+1})_{0 \le k \le M-1}$ ;
		$h_1$	$:=$	FFT( $g,d-1, \omega^2$ );
		$h_2$	$:=$	FFT( $u,d-1,\omega^2$ );
		FOR	$j=0$	TO $M-1$ DO
		$\hat{f}_j$	$:=$	$h_{1,j} + \omega^j\, h_{2,j}$ ;
		$\hat{f}_{j+M}$	$:=$	$h_1,j+ \omega^{M+j}\, h_{2,j}$ ;
		END;		/* FOR */
	END;			/* ELSE */
END;				/* IF */
AUSGABE	$\hat{f}$ .

Bemerkung:Die diskrete Fouriertransformation und ihre Berechnung durch die
schnelle Fouriertransformation ist nicht auf den Körper $\mathbb{C}$ beschränkt. Auch über endlichen Körpern oder in den Ringen $\mathbb{Z}/ n\mathbb{Z}$ wird sie angewendet, wobei die $N$ -te Einheitswurzel $\exp(\frac{2 \pi i}{N})$ ersetzt wird durch Elemente der Ordnung $N$ in der multiplikativen Einheitengruppe des endlichen Körpers oder Rings.
Anwendungen der schnellen Fouriertransformation sind zahlreich. Eines der bekanntesten Beispiele ist der Algorithmus von Schönhage und Strassen zur Multiplikation großer Zahlen, siehe [25]. Für eine Darstellung dieses Algorithmus in einem Lehrbuch, sowie für weitere Anwendungen (Datenkompression etc.) siehe [15].