6.4.2 Die FFT-Idee und ihre Parallelisierung

Die hier betrachtete FFT-Idee wird auch als radix-2 FFT bezeichnet.

Betrachten wir für $n=4$ die Matrix  $\ensuremath{{\cal F}}$ aus (6.8).

$$\ensuremath{{\cal F}} _4 \;=\; \begin{bmatrix} 1 & 1 & 1 &... ...& \omega^6 \\ 1 & \omega^3 & \omega^6 & \omega^9 \end{bmatrix}$$

Wegen $\; \omega^s = \omega^{s \mod 4} \;$ und $\; \omega_{n=4} = e^{-\frac{2\pi}{4} i} = - i \;$ ergibt sich

$$\ensuremath{{\cal F}} _4 \;=\; \begin{bmatrix} 1 & 1 & 1... ... 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{bmatrix} \enspace .$$ (6.9)

Eine Umgruppierung der Einträge in (6.9) mittels der $4\times 4$-Permutationsmatrix

  

Wegen $\; \ensuremath{{\cal F}} _2 = \begin{bmatrix}1 & 1 \\ 1 & -1 \end{bmatrix} \;$ und der Definition $\; \Omega_2 := \begin{bmatrix}1 & 0 \\ 0 & -i \end{bmatrix} = \text{diag}\{1,\omega_{n=4}\} \;$folgt

$$\ensuremath{{\cal F}} _4 \Pi_4 \:\;=\;\; \begin{bmatrix}\e... ... & -\Omega_2 \ensuremath{{\cal F}} _2 \end{bmatrix} \enspace ,$$ (6.10)

d.h. die Fourieranalyse mit $n=4$ läßt sich auf die Fourieranalyse mit $n=2$ zurückführen. Allgemein :

Sei $n=2m$, so gilt

$$\ensuremath{{\cal F}} _n \Pi_n \;=\; \begin{bmatrix}\ensu... ... & -\Omega_m \ensuremath{{\cal F}} _m \end{bmatrix} \enspace ,$$ (6.11)

mit $\Pi_n$ als even-odd-Permutation, welche die Vektorkomponenten umordnet

$$\underline{y}\;:=\; \Pi_n^T \underline{x} \hspace{1em}\Left... ...j=\overline{1,n-1:2} \makebox[0pt]{}} \end{bmatrix} \enspace$$ (6.12)

und $\Omega_m \,:=\, \text{diag}\{ \omega_{n=2m}^k, \,{\scriptstyle \overline{k=0,m-1}} \}$.
Wenn $n=2^P$ ist, so läßt sich (6.13) $P-1$-mal rekursiv anwenden. Damit reduziert sich eine FFT auf das $P-1$-malige Umordnen eines Vektors mit etwas zusätzlicher Arithmetik.


FFT mit $n=8$

$x(0,7:2)$ bezeichne im folgenden den Teilvektor von $x$, der ab Element $0$ bis Element $7$ jede zweite Komponente enthält, d.h. $x(0,7:2) = [x_j]_{j=\overline{0,7:2} \makebox[0pt]{}}$

  

Abbildung 6.7: Aufsplittung der Indizes

Der resultierende Vektor nach der Umordnung in Abbildung 6.7 ist nunmehr als $[x_0, x_4, x_2, x_6, x_1, x_5, x_3, x_7]^T$ geordnet.

Die Parallelisierung der Fouriertransformation  $\ensuremath{{\cal F}}$ (Umordnung und Arithmetik) auf einem Parallelrechner mit verteiltem Speicher ist in Bild 6.8 als sogenannter Butterfly-Algorithmus dargestellt. Hierin sieht man die gute Parallelisierbarkeit der Fouriertransformation, jedoch liegen die resultierenden Komponenten ungeordnet vor, deren Umordnung wiederum mit Zusatzkommunikation verbunden ist.
 

Zurückblickend auf das Beispiel zu Beginn dieses Abschnittes 6.4, ist an Stelle der diskreten Gleichung  $\Lambda \underline{u} = \underline{f}$ die Gleichung

$$\tfrac{1}{n} \ensuremath{{\cal F}}\Lambda \ensuremath{{\cal F... ...t \underline{u} \;=\; \ensuremath{{\cal F}}\cdot \underline{f}$$

zu lösen :

a)	Fourieranalyse :	$\underline{\gamma} \,:=\, \tfrac{1}{n} \ensuremath{{\cal F}}\underline{f}$	$\underline{\gamma}$ umgeordnet
b)	Operator  $\Lambda^{-1}$ :	$\beta_i \,:=\, \frac{\gamma_i}{\lambda_i}$	$\underline{\beta}$ umgeordnet
c)	Fouriersynthese :	$\underline{u} \,:=\, \ensuremath{{\cal F}}\underline{\beta}$	$\underline{u}$ richtig geordnet !!

Da zweimal die Fouriertransformation angewendet werden mußte, liegen zum Schluß die Komponenten der Lösung wieder in richtiger Reihenfolge vor !

$\Longrightarrow$

Die Kombination von Fourieranalyse und -synthese ist sehr gut parallelisierbar.