Da die DFT-Matrix symmetrisch ist, macht es keinen Unterschied, ob man sie von rechts oder von links auf einen Vektor multipliziert. Algorithmus 16 verwendet die Zerlegung von Satz 148 im Sinn einer Multiplikation von links. Entwerfen Sie einen alternativen Algorithmus, der die Zerlegung von Satz 148 im Sinn einer Multiplikation von rechts umsetzt. Zeigen Sie, dass Ihr Algorithmus ebenfalls die Komplexität O(n log n) hat.
Algorithmus 16:
Eingabe: Ein Vektor x = (x0; : : : ; xn-1) ∈ Kn mit n = 2k fur ein k ∈ ℕ, und eine primitive n-te Einheitswurzel ω ∈ K.
Ausgabe: DFTn(ω) x
1 wenn n = 1 ist, gib x als Ergebnis zurück und stop.
2 wende den Algo. auf (x0, x2, ... ; xn-2) und ω2 an. Das Ergebnis sei u = (u0, ..., un/2-1).
3 wende den Algo. auf (x1, x3, ... , xn-1) und ω2 an. Das Ergebnis sei v = (v0, ..., vn/2-1).
4 q = 1
5 für i = 0, ..., n/2-1:
6 yi = ui + qvi
7 yi+n/2 = ui - qvi
8 q = ωq
9 gib (y0, y1, ..., yn-1) als Ergebnis zurück.
Satz 148. (Cooley-Tuckey) Sei \( n \in \mathbb{N} \backslash\{0\} \) und sei \( \omega \) eine primitive \( 2 n \)-te Einheitswurzel.
Weiter sei
\( \Delta=\operatorname{diag}\left(1, \omega, \omega^{2}, \ldots, \omega^{n-1}\right) \in \mathbb{K}^{n \times n} \)
und \( P \in \mathbb{K}^{2 n \times 2 n} \) sei die Permutationsmatrix, für die gilt
\( P \cdot\left(x_{0}, x_{1}, x_{2}, x_{3}, \ldots\right)=\left(x_{0}, x_{2}, x_{4}, \ldots, x_{1}, x_{3}, x_{5}, \ldots\right) \text {. } \)
Dann gilt
\( \operatorname{DFT}_{2 n}^{(\omega)}=\left(\begin{array}{cc} I_{n} & I_{n} \\ I_{n} & -I_{n} \end{array}\right)\left(\begin{array}{cc} I_{n} & 0 \\ 0 & \Delta \end{array}\right)\left(\begin{array}{cc} \mathrm{DFT}_{n}^{\left(\omega^{2}\right)} & 0 \\ 0 & \mathrm{DFT}_{n}^{\left(\omega^{2}\right)} \end{array}\right) P \)
