Vorlesungsskript

Effiziente numerische Algorithmen

Frank Natterer Institut für Numerische

und instrumentelle Mathematik

WS 1994/95, Di/Fr 11-13, M 5

This page intentionally left blank.

Inhaltsverzeichnis

1 Einleitung 3 1.1 Schnelle Multiplikation von Zahlen . . . . . . . . . . . . 3 1.2 Multiplikation und Inversion von Matrizen . . . . . . . . 7

2 Algebra 11 2.1 Darstellung endlicher Gruppen . . . . . . . . . . . . . . . 11 2.2 Charaktere endlicher Gruppen . . . . . . . . . . . . . . . 21 2.3 Der Chinesische Restsatz . . . . . . . . . . . . . . . . . . 31 2.4 Gruppentheorie . . . . . . . . . . . . . . . . . . . . . . . 36

3 Schnelle Fourier-Transformation 41 3.1 Fourier-Transformation und Faltung . . . . . . . . . . . . 41 3.2 Cooley-Tukey . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3 Primfaktoren . . . . . . . . . . . . . . . . . . . . . . . . 50 3.4 Schnelle Faltung nach Winograd . . . . . . . . . . . . . . 56 3.5 Die schnelle Fourier–Transformation nach Winograd … 64 3.6 Schnelle Poisson-Löser . . . . . . . . . . . . . . . . . . . 69 2 INHALTSVERZEICHNIS 4 Symmetrie 73

4.1 Matrizen mit Symmetrien . . . . . . . . . . . . . . . . . 73 4.2 Untergruppen . . . . . . . . . . . . . . . . . . . . . . . . 88 4.3 Direkte Produkte . . . . . . . . . . . . . . . . . . . . . . 91 4.4 Die Fourier-Transformation auf Gruppen . . . . . . . . . 95

5 Toeplitz-Matrizen 101 5.1 Der Algorithmus von Trench . . . . . . . . . . . . . . . . 101 5.2 Der Algorithmus von Morf . . . . . . . . . . . . . . . . . 106

Kapitel 1

Einleitung

Wir geben einige Beispiele für effiziente Algorithmen, die wir zum Teil später wieder aufgreifen und vertiefen werden. Zunächst geht es nur darum, einen ersten Einblick in die behandelten Probleme und verwendeten Methoden zu geben.

1.1 Schnelle Multiplikation von Zahlen

Seien x, y Zahlen in endlich b-adischer Darstellung, b > 1, also

\begin{aligned}x & = & x_{0} + x_{1}b + … + x_{n−1}b^{n−1} & , & 0 ≤ x_{i} < b , \\ y & = & y_{0} + y_{1}b + … + y_{n−1}b^{n−1} & , & 0 ≤ y_{i} < b \end{aligned}

mit ganzen Zahlen x_{i}, y_{i}. Gesucht ist das Produkt z = xy. Die Schulmethode soll an Hand eines Beispiels mit b = 10 und n = 3 erläutert werden:

\underline{214 · 713} ; 642 ; 214 ; \underline{1498} ; 152582

Offenbar benötigt die Schulmethode für eine Multiplikation der Länge n O(n^{2}) Rechenoperationen. Addiert man, sobald in einer Spalte alle Produkte berechnet sind, so kommt man mit O(n) Speicherplätzen aus.

Der Schulmethode stellen wir als effizienten Algorithmus die Karatsuba-Multiplikation gegenüber. Sei n gerade und n = 2m. Wir teilen x auf in

ξ_{0} = x_{0} + x_{1}b + … + x_{m−1}b^{m−1} , ξ_{1} = x_{m} + x_{m+1}b + … + x_{n−1}b^{m−1}

und entsprechend y = η_{0} + b^{m}η_{1}. Dann ist

\begin{aligned}xy & = & ξ_{0}η_{0} + (ξ_{0}η_{1} + ξ_{1}η_{0})b^{m} + ξ_{1}η_{1}b^{n} \\ & = & (1 + b^{m})ξ_{0}η − b^{m}(ξ_{1} − ξ_{0})(η_{1} − η_{0}) + (b^{m} + b^{n})ξ_{1}η_{1} . \end{aligned}

Wir können also eine Multiplikation der Länge n realisieren durch 3 Multiplikationen der Länge n/2 sowie O(n) zusätzliche Rechenoperationen. Ist also T (n) die Anzahl der Rechenoperationen, die wir für eine Multiplikation der Länge n benötigen, so gilt

T (n) ≤ 3T (\frac{n}{2}) + cn , T (1) = 1

mit einer von n unabhängigen Konstanten c. Ist nun n eine Zweierpotenz, also n = 2^{p}, so ist mit T_{p} = T (2^{p})

T_{p} ≤ 3T_{p−1} + c2^{p} , T_{0} = 1 .  (1.1.1)

Lemma 1.1.1 Seien T_{p}, q, r_{p} ≥ 0, und sei

T_{p+1} ≤ qT_{p} + r_{p} , p = 0, 1, ….

Dann ist

T_{p} ≤ q^{p}T_{0} + ∑_{j=0}^{p−1} q^{p−1−j}r_{j} .

Der Beweis durch vollständige Induktion ist trivial.

Satz 1.1.2 Für n = 2^{p} kann die Multiplikation der Länge n in O(n^{log_{2} 3}) Rechenoperationen durchgeführt werden.

Beweis: Wenden wir Lemma 1.1.1 auf (1.1.1) an, so entsteht

T_{p} ≤ 3^{p} + c ∑_{j=0}^{p−1} 3^{p−1−j}2^{j+1}

= 3^{p} + c3^{p} ∑_{j=0}^{p−1} (\frac{2}{3})^{j+1}

≤ 3^{p} + c3^{p} \frac{2}{3} \frac{1}{1 − 2/3} = (1 + 2c)3^{p}
= (1 + 2c)n^{log_{2} 3} .
□

Wegen log_{2} 3 = 1.585 < 2 ist dies eine Verbesserung gegenüber der O(n^{2})-Abschätzung für die Schulmethode, jedenfalls für große n. Das Karatsuba-Verfahren kann leicht durch ein rekursives Programm realisiert werden:

fmult (n, x, y, z)
{ if (n == 1) Schulmethode;

else

{ m = n/2;

ξ_{0} = (x_{0}, …, x_{m−1}); ξ_{1} = (x_{n}, …, x_{n−1}); η_{0} = (y_{0}, …, y_{m−1}); η_{1} = (y_{m}, …, y_{n−1}); fmult (m, ξ_{0}, η_{0}, α); fmult (m, ξ_{1} − ξ_{0}, η_{1} − η_{0}, β); fmult (m, ξ_{1}, η_{1}, γ) for (i = 0; i < n; i + +) z_{i} = 0; for (i = 0; i < n; i + +)

{ z_{i} = α_{i} + z_{i};
z_{i+m} = α_{i} − β_{i} + γ_{i} + z_{i+m};
z_{i+n} = γ_{i} + z_{i+n};
}

} } Der Karatsuba-Algorithmus ist ein typisches Beispiel für die oft verwendete “Divide-and-Conquer-Statgie”: Ein Problem wird in kleinere Teilprobleme zerlegt. Diese werden gelöst und aus den Lösungen die Lösung des ursprünglichen Problems zusammengesetzt. Dieser Prozeß wird in rekursiver Weise wiederholt.

1.2. MULTIPLIKATION UND INVERSION VON MATRIZEN 7

1.2 Schnelle Multiplikation und Inversion von Matrizen

Zur Multiplikation zweier (n, n)-Matrizen A, B nach der Schulmethode benötigt man bekanntlich O(n^{3}) Rechenoperationen. Das gleiche gilt für die Inversion einer (n, n)-Matrix. Wir wollen den Straßen-Algorithmus vorstellen, der beide Aufgaben in O(n^{log_{2} 7}), log_{2} 7 = ℓn7/ℓn2 = 2.807, Rechenoperationen erledigt.

Für eine (n, n)-Matrix A mit geradem n schreiben wir

A = ( \begin{matrix}A_{11} A_{12} \\ A_{21} A_{22} \end{matrix} )

mit (\frac{n}{2}, \frac{n}{2})-Matrizen A_{ij}.

Lemma 1.2.1 Sei C = AB mit (n, n)-Matrizen A, B, C. Dann gilt

\begin{aligned}C_{11} & = & I + IV − V + V II & , & C_{12} & = & III + V , \\ C_{21} & = & II + IV & , & C_{22} & = & I + III − II + V I \end{aligned}

mit

\begin{aligned}I & = & (A_{11} + A_{22})(B_{11} + B_{22}) \\ II & = & (A_{21} + A_{22})B_{11} \\ III & = & A_{11}(B_{12} − B_{22}) \\ IV & = & A_{22}(B_{21} − B_{11}) \\ V & = & (A_{11} + A_{12})B_{22} \\ V I & = & (A_{21} − A_{11})(B_{11} + B_{12}) \\ V II & = & (A_{12} − A_{22})(B_{21} + B_{22}) \end{aligned}

Beweis: Der Beweis durch einfaches Nachrechnen ist trivial.

Wer Schwierigkeiten hat, sei auf V. Straßen: Gaussian Elimination ist not optimal, Numer. Math. 13, 354-356 (1969), verwiesen.

□

Satz 1.2.2 Sei n = 2^{p}. Dann kann man zwei (n, n)-Matrizen in O(n^{log_{2} 7}) Rechenoperationen multiplizieren.

Beweis: Inspektion der Formel von Lemma 1.2.1 zeigt, daß man die Multiplikation zweier (n, n)-Matrizen durch 7 Multiplikationen und 18 Additionen von (\frac{n}{2}, \frac{n}{2})-Matrizen ausführen kann. Ist also n = m·2^{p} und M_{p} bzw. A_{p} die Anzahl der reellen Multiplikation bzw. Additionen, welche man zur Multiplikation zweier (n, n)-Matrizen benötigt, so gilt nach Lemma 1.2.1

\begin{aligned}M_{p+1} & ≤ & 7M_{p} & , & M_{0} ≤ m^{3} , \\ A_{p+1} & ≤ & 7A_{p} + 18(m · 2^{p})^{2} & , & A_{0} ≤ m^{3} . \end{aligned}

Nach Lemma 1.1.1 erhält man

M_{p} ≤ 7^{p}m^{3}
A_{p} ≤ 7^{p}m^{3} + 18m^{2} ∑_{j=0}^{p−1} 7^{p−1−j}2^{2j}
= 7^{p}m^{3} + 18m^{2}7^{p−1} ∑_{j=0}^{p−1}(\frac{4}{7})^{j}
≤ 7^{p}(m^{3} + 6m^{2})

Für m = 1 folgt wegen 7^{p} = n^{log_{2} 2} die Behauptung.

□

Für n = m2^{p} lautet der Straßen-Algorithmus

fmamu  (n, A, B, C)
{  if (n ≤= m) Schulmethode;

else

\{ fmamu (\frac{n}{2}, A_{11} + A_{22}, B_{11} + B_{22}, I);
⋮
fmamu (\frac{n}{2}, A_{12} − A_{22}, B_{21} + B_{22}, V II);
C_{11} = I + IV − V + V II; C_{12} = III + V;
C_{21} = II + IV; C_{22} = I + V I − II + V I;

} } Nun zur Matrizeninversion. Anstelle von Lemma 1.2.1 haben wir jetzt

Lemma 1.2.3 Sei A eine invertierbare (n, n)-Matrix mit geradem n, und seien die Matrizen A_{11} und A_{21}A_{11}^{−1}A_{12} − A_{22} invertierbar. Dann gilt mit

\begin{aligned}I & = & A_{11}^{−1} & , & II & = & A_{21}I & , & III & = & IA_{12} \\ IV & = & A_{21}III & , & V & = & IV − A_{22} & , & V I & = & V^{−1} \end{aligned}

für C = A_{−1}:

\begin{aligned}C_{12} & = & III V I & , & C_{12} & = & V I II & , & V II & = & III C_{21} , \\ C_{11} & = & I − V II & , & C_{22} & = & −V I & . \end{aligned}

Beweis: Durch triviales Nachrechnen.

□

Satz 1.2.4 Sei n = 2^{p} und A eine invertierbare (n, n)-Matrix. Unter der Voraussetzung V (siehe unten) kann A mit O(n^{log 7/ log 2}) Rechenoperationen invertiert werden.

Beweis: Durch Inspektion der Formeln von Lemma 1.2.3 sehen wir, daß eine (n, n)-Matrix durch 2 Inversionen, 6 Multiplikationen, und 2 Additionen von (\frac{n}{2}, \frac{n}{2})-Matrizen invertiert werden kann. Setzen wir wieder n = m2^{p} und bezeichnen wir mit δ_{p}, μ_{p}, α_{p} die Anzahl der reellen Divisionen, Multiplikationen und Additionen für die Inversion einer (n, n)-Matrix, so gilt also

\begin{matrix}δ_{p+1} ≤ 2δ_{p} & , & δ_{0} ≤ m , \\ μ_{p+1} ≤ 2μ_{p} + 6M_{p} & , & μ_{0} ≤ m^{3} , \\ α_{p+1} ≤ 2α_{p} + 6A_{p} + 2(m2^{p})^{2} & , & α_{0} ≤ m^{3} . \end{matrix}

Die Ungleichungen für p = 0 gelten, falls man für p = 0 das Eliminationsverfahren verwendet. Auf diese Rekursionen wenden wir wieder Lemma 1.1.1 an und erhalten

δ_{p} ≤ m^{3} ,
μ_{p} ≤ 2^{p}m^{3} + 6 ∑_{j=0}^{p−1} M_{j}2^{p−j−1}
≤ 2^{p}m^{3} + 6m^{3} ∑_{j=0}^{p−1} 7^{j}2^{p−j−1}
= 2^{p}m^{3} (1 + 3 ∑_{j=0}^{p−1}(\frac{7}{2})^{j})
= 2^{p}m^{3} (1 + 3\frac{(7/2)^{p}−1}{\frac{7}{2}})
≤ 7^{p}m^{3} · \frac{6}{5} ,
α_{p} ≤ (\frac{6}{5}m^{3} + 5m^{2}) 7^{p} .

Für m = 1 erhält man die Behauptung.

Natürlich können nur solche Matrizen auf diese Weise invertiert werden, für die bei allen Unterteilungen n → \frac{n}{2} → \frac{n}{4} … → m die Voraussetzungen von Lemma 1.2.3 erfüllt sind. Dies ist Inhalt der Voraussetzung V.

□

Algebra

2.1 Darstellung endlicher Gruppen

Wir setzen eine gewisse Vertrautheit mit der elementaren Gruppentheorie voraus. Sei G eine endliche Gruppe. Wir schreiben alle Gruppen multiplikativ. 1 ist das Einselement, |G| die Ordnung, d.h. die Anzahl der Elemente, von G.

Beispiele:

1) Die zyklische Gruppe C_{n} der Ordnung n. Sie wird erzeugt von einem Element q mit q^{n} = 1, so daß also C_{n} = {1, q, …, q^{n−1}}. C_{n} ist abelsch.

2) Die Gruppe S_{n} der Permutationen von n Elementen. Sie hat die Ordnung n! und ist nicht abelsch. S_{n} heißt die symmetrische Gruppe. Eine Permutation kann gerade oder ungerade sein. Die Untergruppe A_{n} der geraden Permutationen heißt alternierende Gruppe.

3) Die Diedergruppe D_{n}. Sie wird erzeugt von Rotationen r um den Winkel 2π/n und durch eine Spiegelung s an einer Geraden. Sie besteht also aus den Elementen 1, r, …, r^{n−1}, s, sr, …, sr^{n−1} und hat also die Ordnung 2n. Es ist r^{n} = 1, s^{2} = 1. D_{n} ist nur für n = 1, 2 abelsch.

Definition 2.1.1 Sei G eine endliche Gruppe und V ein d-dimensionaler Vektorraum über C. GL(V) sei die Gruppe der linearen invertierbaren Abbildungen V → V.

Ein Homomorphismus ρ : G → GL(V) heißt Darstellung von G in V. Ist ρ injektiv, so heißt die Darstellung treu. d heißt der Grad von ρ. Zwei Darstellungen ρ, ρ′ von G in V bzw. V′ heißen äquivalent, wenn es eine lineare invertierbare Abbildung τ : V → V′ gibt, so daß ρ′ = τρτ^{−1}.

Beispiele:

1) ρ(s) = 1 für alle s heißt Einheitsdarstellung.

2) Die reguläre Darstellung ρreg wird wie folgt definiert. Sei {e_{t} : t ∈ G} eine Basis von V. Dann setzt man

ρreg(s)e_{t} = e_{st}

(linksreguläre Darstellung). Es ist also

ρreg(s) ∑_{t∈G} x_{t}e_{t} = ∑_{t∈G} x_{t}ρreg(s)e_{t}
= ∑_{t∈G} x_{t}e_{st}
= ∑_{t∈G} x_{s^{−1}t}e_{t} .

ρreg übt also auf die Komponenten x_{t} die Permutation t → s^{−1}t aus. Der Grad von ρreg ist |G|. ρreg ist treu.

3) Sei G = C_{n} = {1, q, …, q^{n−1}} und ω eine n-te Einheitswurzel, also ω^{n} = 1. Dann ist

ρ(q^{k}) = ω^{k} , k = 0, 1, …, n − 1

eine Darstellung von C_{n} in C, der Grad also 1. ρ ist genau dann treu, wenn ω eine primitive n-te Einheitswurzel ist, d.h. wenn ω^{m} ≠ 1 für 0 < m < n. Sind ω_{1}, ω_{2} verschiedene n-te Einheitswurzeln, so sind die zugehörigen Darstellungen nicht äquivalent.

Wir berechnen die reguläre Darstellung von C_{n}. Mit e_{k} = e_{q^{k}}, x_{k} = x_{q^{k}} haben wir

ρreg(s^{ℓ}) ∑_{k=0}^{n−1} x_{k}e_{k} = ∑_{k=0}^{n−1} x_{k−ℓ}e_{k} , ℓ = 0, …, n − 1 ,

wobei k − ℓ modulo n genommen wird.

4) Sei G = S_{n}. Die alternierende Darstellung

ρalt(π) = \{ \begin{matrix}1 & , & π gerade , \\ −1 & , & π ungerade \end{matrix}

ist vom Grad 1 und für n > 2 nicht treu. Die natürliche Darstellung von S_{n} ist wie folgt definiert. Seien e_{1}, …, e_{n} die Einheitsvektoren in C und v = ∑_{i=1}^{n} x_{i}e_{i}. Dann ist

ρnat(π)v = ∑_{i=1}^{n} x_{i}e_{π(i)} .

Der Grad von ρnat ist n, und ρnat ist treu.

5) Sei G = D_{n} und n gerade. Für D_{n} haben wir 5 verschiedene Typen von Darstellungen

ρ(r^{k})  ρ(sr^{k})  Grad(ρ)  Bemerkungen
ρ_{1}  1  1  1  Einheitsdarstellung
ρ_{2}  1  −1  1
ρ_{3}  (−1)^{k}  (−1)^{k}  1
ρ_{4}  (−1)^{k}  (−1^{k+1}  1
ρ_{5}^{h} ( \begin{matrix}ω^{hk} & 0 \\ 0 & ω^{−hk} \end{matrix} ) ( \begin{matrix}0 & ω^{−hk} \\ ω^{hk} & 0 \end{matrix} )  2  \begin{matrix}ω = e^{2πi/n} , \\ h = 1, …, \frac{n}{2} − 1 . \end{matrix}

Die Beschränkung auf h < \frac{n}{2} ist sinnvoll, weil ρ_{5}^{h}, ρ_{5}^{n−h} äquivalent sind. Wegen ω_{n} = 1 ist nämlich

ρ_{5}^{n−h}(r^{k}) = ( \begin{matrix}ω^{(n−h)k} & 0 \\ 0 & ω^{−(n−h)k} \end{matrix} ) = ( \begin{matrix}ω^{−hk} & 0 \\ 0 & ω^{hk} \end{matrix} )
= ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}ω^{hk} & 0 \\ 0 & ω^{−hk} \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )
= τρ_{5}^{h}(r^{k})τ^{−1} ,
ρ_{5}^{n−h}(sr^{k}) = ( \begin{matrix}0 & ω^{(n−h)k} \\ ω^{−(n−h)k} & 0 \end{matrix} ) = ( \begin{matrix}0 & ω^{−hk} \\ ω^{hk} & 0 \end{matrix} )
= ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}0 & ω^{hk} \\ ω^{−hk} & 0 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )
= τρ_{5}^{h}(sr^{k})τ_{−1}

für alle k mit der nichtsingulären Matrix T = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ).

Definition 2.1.2 Eine Darstellung ρ von G in V heißt reduzibel, wenn es einen echten Unterraum V_{1} von V gibt mit ρ(s)V_{1} ⊆ V_{1} für alle s ∈ G. V_{1} heißt dann invarianter Unterraum von ρ.

Ist ρ nicht reduzibel, so nennt man ρ irreduzibel.

Beispiele:

1) Die Einheitsdarstellung ist für d > 1 reduzibel. Darstellungen vom Grad 1 sind stets irreduzibel.

2) ρreg ist für |G| > 1 reduzibel, denn (1, …, 1) spannt einen echten invarianten Unterraum auf.

Satz 2.1.3 Sei V = V_{1} ⊕ … ⊕ V_{r}, und seien ρ_{i} Darstellungen von G in V_{i}. Dann ist

ρ(s)v = ∑_{i=1}^{r} ρ_{i}(s)v_{i} für v = ∑_{i=1}^{r} v_{i} , v_{i} ∈ V_{i}

eine Darstellung von G in V mit den invarianten Unterräumen V_{i}.

Beweis: Natürlich ist ρ : G → GL(V) ein Homomorphismus. Ist v ∈ V_{i}, so ist auch ρ(s)v ∈ V_{i}.

□

Definition 2.1.4 Die Darstellung ρ aus Satz 2.1.3 heißt direkte Summe von ρ_{1}, …, ρ_{r}. Man schreibt ρ = ρ_{1} + … + ρ_{r}.

Wir wollen nun Darstellungen durch Matrizen beschreiben. Sei v_{1}, …, v_{d} eine Basis von V. ρ(s) wird dann beschrieben durch eine (d, d)-Matrix R(s), d.h.

ρ(s)v = ∑_{i=1}^{d} y_{i}v_{i} für v = ∑_{i=1}^{d} x_{i}v_{i}

mit y = R(s)x. Natürlich gilt R(st) = R(s)R(t). R ist nichts anderes als eine Darstellung von G in C^{d}.

Sei nun V_{1} invarianter Unterraum von ρ der Dimension m mit Basis v_{1}, …, v_{m}. Dann hat R die Gestalt

R(s) = ( \begin{matrix}R_{11}(s) & R_{12}(s) \\ O & R_{22}(s) \end{matrix} )

mit einer (m, m)-Matrix R_{11}(s) und einer (d−m, d−m)-Matrix R_{22}(s). Ist R_{12} = 0, so ist ρ = ρ_{1} + ρ_{2} mit den durch R_{11}, R_{22} beschriebenen Darstellungen ρ_{1}, ρ_{2}. Sind allgemeiner ρ_{1}, …, ρ_{r} Darstellungen von G in V_{1}, …, V_{r}, welche von den Matrizen R_{1}, …, R_{r} beschrieben werden, so wird ρ = ρ_{1} + … + ρ_{r} durch die Matrix

R = ( \begin{matrix}R_{1} & & & & O \\ & . & . & . \\ O & & & & R_{r} \end{matrix} )

beschrieben.

Satz 2.1.5 Sei ρ eine Darstellung von G in V. Dann gibt es ein Skalarprodukt in V, bezüglich dem ρ unitär ist.

Beweis: Sei ( , ) irgendein Skalarprodukt in V, und sei

⟨u, v⟩ = \frac{1}{|G|} ∑_{s∈G}(ρ(s)u, ρ(s)v) .

Dann ist auch ⟨ , ⟩ ein Skalarprodukt in V, und es gilt

⟨ρ(t)u, ρ(t)v⟩ = \frac{1}{|G|} ∑_{s∈G}⟨ρ(s)ρ(t)u, ρ(s)ρ(t)v⟩

= \frac{1}{|G|} ∑_{s∈G}⟨ρ(st)u, ρ(st)v⟩

= \frac{1}{|G|} ∑_{s∈G}⟨ρ(s)u, ρ(s)v⟩
= ⟨u, v⟩ .

Also ist ρ bezüglich ⟨ , ⟩ unitär.

□

Satz 2.1.6 Jede Darstellung einer Gruppe ist eine direkte Summe irreduzibler Darstellungen dieser Gruppe.

Beweis: Sei ρ eine Darstellung von G in V. Ohne Beschränkung der Allgemeinheit können wir annehmen, daß ρ bezüglich eines Skalarprodukts ⟨ , ⟩ in V unitär ist. Ist ρ irreduzibel, sind wir fertig. Andernfalls besitzt ρ einen invarianten Unterraum V_{1} ≠ {0}, ≠ V. Sei V_{2} das orthogonale Komplement von V_{1} in V bezüglich des Skalarprodukts ⟨ , ⟩. Wir zeigen, daß auch V_{2} invarianter Unterraum von ρ ist. Sei dazu v ∈ V_{2}. Für jedes u ∈ V_{1} ist

\begin{aligned}⟨ρ(s)v, u⟩ & = & ⟨ρ(s)v, ρ(s)ρ(s^{−1})u⟩ = ⟨v, ρ(s^{−1})u⟩ \\ & = & 0 , \end{aligned}

denn mit u ist auch ρ(s^{−1})u ∈ V_{1}. Also ist ρ(s)v ∈ V_{2}. Es sind also V_{1}, V_{2} invariante Unterräume von ρ, und es ist V = V_{1} ⊕V_{2}. Die Restriktionen ρ_{1}, ρ_{2} von ρ auf V_{1}, V_{2} sind Darstellungen von ρ in V_{1}, V_{2}, und es gilt ρ = ρ_{1} + ρ. ρ_{1}, ρ_{2} haben kleineren Grad als ρ.

Sind ρ_{1}, ρ_{2} irreduzibel, so sind wir fertig. Andernfalls zerfallen ρ_{1}, ρ_{2} ihrerseits in Darstellungen noch kleineren Grades. Durch Fortführen dieses Prozesses kommt man nach endlich vielen Schritten bei irreduziblen Darstellungen an.

□

Definition 2.1.7 Das Zerlegen einer Darstellung in irreduzible Darstellungen nach Satz 2.1.6 nennt man Ausreduzieren der Darstellung.

Beispiel:

Ausreduzieren der regulären Darstellung ρreg von C_{n}. Bezüglich der Basis e_{0}, …, e_{n−1} in V = C^{n} gilt

ρreg(s^{ℓ}) ∑_{k=0}^{n−1} x_{k}e_{k} = ∑_{k=0}^{n−1} x_{k−ℓ}e_{k} , ℓ = 0, …, n − 1 ,

wobei k − ℓ modulo n zu verstehen ist. Sei ω_{j} eine n-te Einheitswurzel und x^{j} = (1, ω_{j}, …, ω_{j}^{n−1}). Dann ist

ρreg(s^{ℓ})x^{j} = ∑_{k=0}^{n−1} ω_{j}^{k−ℓ}e_{k} = ω_{j}^{−ℓ} ∑_{k=0}^{n−1} ω_{j}^{k}e_{k}
= ω_{j}^{ℓ}x .

Also ist V_{j} = sp⟨x^{j}⟩ invarianter Unterraum von ρ, und ρ_{j}(s^{ℓ}) = ω_{j}^{ℓ} Darstellung von C_{n} in V_{j}. Für ω_{j} = e^{2πij/n}, j = 0, …, n−1 gilt V = V_{0}⊕ …⊕V_{n−1}, weil x^{0}, …, x^{n−1} linear unabhängig sind (Van der Mond’sche Determinante). Also ρ = ρ + … + ρ_{n−1}.

Satz 2.1.8 (Lemma von Schur) Seien ρ_{i} irreduzible Darstellungen einer Gruppe in V_{i}, i = 1, 2. Sei τ : V_{1} → V_{2} linear. Es gelte τρ_{1} = ρ_{2}τ. Dann gilt:

(i) Sind ρ_{1}, ρ_{2} nicht äquivalent, so ist τ = 0.

(ii) Ist ρ_{1} = ρ_{2}, so ist τ = λ mit λ ∈ C.

Beweis:

(i) Wir zeigen zunächst, daß W_{1} = τ^{−1}(0) invarianter Unterraum von ρ_{1} ist. Ist nämlich x ∈ W_{1}, so ist auch τρ_{1}(s)x = ρ_{2}(s)τx = 0.

Da ρ_{1} irreduzibel ist, ist also entweder W_{1} = {0} oder W_{1} = V_{1}. Im letzteren Fall sind wir fertig. Im ersten Fall ist τ injektiv. Wir zeigen, daß W_{2} = τV_{1} invarianter Unterraum von ρ_{2} ist. Für y ∈ W_{2} ist nämlich ρ_{2}(s)y = ρ_{2}(s)τx = τρ_{1}(s)x ∈ W_{2}. Da ρ_{2} irreduzibel ist, ist entweder W_{2} = {0} oder W_{2} = V_{2}. Im ersten Fall ist τ = 0, und wir sind fertig. Im zweiten Fall ist τ surjektiv. Da τ auch injektiv ist, ist τ bijektiv, und das ist nicht möglich, da ρ_{1}, ρ_{2} nicht äquivalent sind.

(ii) Für ρ_{1} = ρ_{2} ist V_{1} = V_{2} = V und τ : V → V hat mindestens einen Eigenwert λ und Eigenvektor x zu λ, also τx = λx, x ≠ 0. Sei τ′ = τ −λ und W′_{1} = τ^{′^{−1}}(0). W′_{1} ist invarianter Unterraum von ρ. Ist nämlich v ∈ W′_{1}, so ist τ′ρ(s)v = (τ − λ)ρ(s)v = ρ(s)(τ − λ)v = ρ(s)τ′v = 0. Also ist wieder entweder W′_{1} = {0} oder W′_{1} = V. Das erste ist nicht möglich, weil x ∈ W′_{1}. Also muß W′_{1} = V und damit τv = λv sein für alle v ∈ B. Also τ = λ.

□

Satz 2.1.9 Seien ρ_{1}, ρ_{2} irreduzible Darstellungen von G in V_{1}, V_{2}, und sei τ : V_{1} → V_{2} eine lineare Abbildung. Sei

τ′ = \frac{1}{|G|} ∑_{t∈G} ρ_{2}(t^{−1})τρ_{1}(t) .

Dann gilt:

(i) Sind ρ_{1}, ρ_{2} nicht äquivalent, so ist τ′ = 0.

(ii) Ist ρ_{1} = ρ_{2}, so ist τ′ = d^{−1} Spur (τ) mit dem Grad d von ρ_{1}.

Beweis: Für jedes s ∈ G ist

ρ_{2}(s)τ′ = \frac{1}{|G|} ∑_{t∈G} ρ_{2}(s)ρ_{2}(t^{−1})τρ_{1}(t)
= \frac{1}{|G|} ∑_{t∈G} ρ_{2}(st^{−1})τρ_{1}(t)
= \frac{1}{|G|} ∑_{t∈G} ρ_{2}(t^{−1})τρ_{1}(ts)
= \frac{1}{|G|} ∑_{t∈G} ρ_{2}(t^{−1})τρ_{1}(t)ρ_{1}(s)
= τ′ρ_{1}(s) .

Sind also ρ_{1}, ρ_{2} nicht äquivalent, so ist nach dem Lemma von Schur τ′ = 0. Ist ρ_{1} = ρ_{2} = ρ, so folgt ebenfalls nach dem Lemma von Schur τ′ = λ. Also gilt

λ = \frac{1}{|G|} ∑_{t∈G} ρ(t^{−1})τρ(t) .

Berechnen wir auf beiden Seiten die Spur, so folgt

λd = \frac{1}{|G|} ∑_{t∈G} Spur (ρ(t^{−1})τρ(t))
= \frac{1}{|G|} ∑_{t∈G} Spur ((ρ(t)^{−1}τρ(t))
= \frac{1}{|G|} ∑_{t∈G} Spur (τ)
= Spur (τ) .

Satz 2.1.10 (Orthogonalitätsrelationen) Seien ρ_{1}, ρ_{2} irreduzible Darstellungen von G in V_{1}, V_{2}, und seien ρ_{1}, ρ_{2} bezüglich bestimmter Basen in V_{1}, V_{2} durch die Matrizen R^{1}, R^{2} beschrieben. Dann gilt:

(i) Sind ρ_{1}, ρ_{2} nicht äquivalent, so ist für alle i, j, ℓ, k

\frac{1}{|G|} ∑_{t∈G} R_{iℓ}^{2}(t^{−1})R_{kj}^{1}(t) = 0

(ii) Ist ρ_{1} = ρ_{2}, so gilt mit d = Grad (ρ_{1})

\frac{1}{|G|} ∑_{t∈G} R_{iℓ}^{2}(t^{−1})R_{kj}^{1}(t) = \{ \begin{matrix}1/d & & falls i = j und ℓ = k , \\ 0 & , & sonst . \end{matrix}

Beweis: Sei T die (d_{2}, d_{1})-Matrix (d_{i} = Grad (ρ_{i}))

T_{mn} = \{ \begin{matrix}1 & , & m = ℓ und n = k , \\ 0 & , & sonst . \end{matrix}

Sei τ die lineare Abbildung von V_{1}, V_{2}, die bezüglich der gewählten Basen in V_{1}, V_{2} die Matrix T hat. Dann hat die lineare Abbildung τ′ aus Satz 2.1.9 bezüglich dieser Basen die Matrix T′ mit

T′_{ij} = \frac{1}{|G|} ∑_{t∈G} R_{iℓ}^{2}(^{−1})R_{kj}^{1}(t) .

Sind ρ_{1}, ρ_{2} nicht äquivalent, so ist nach Satz 2.1.9 T′ = 0 und damit

(i) bewiesen. Für ρ_{1} = ρ_{2} ist nach Satz 2.1.9 T′ = d^{−1}δ_{ℓk}, und daraus folgt (ii).

□

Beispiel: G = C_{n}. Seien ω_{1}, ω_{2} n-te Einheitswurzeln. Dann sind ρ_{1}(q^{k}) = ω_{1}^{k}, ρ_{2}(q^{k}) = ω_{2}^{k} irreduzible Darstellungen von C_{n} = {1, q, …, q^{n−1}}, die für ω_{1} ≠ ω_{2} nicht äquivalent sind. Nach Satz 2.1.10 (i), (ii) ist dann

\frac{1}{n} ∑_{r=0}^{n−1} ω_{2}^{−r}ω_{1}^{r} = \{ \begin{matrix}0 & , & ω_{1} ≠ ω_{2} , \\ 1 & , & ω_{1} = ω_{2} . \end{matrix}

Dies sind die bekannten Orthogonalitätsrelationen der Exponentialfunktion.

2.2 Charaktere endlicher Gruppen

Darstellungen von Gruppen sind recht komplizierte Gebilde. Für viele Fragen genügt es, einfachere Gebilde, nämlich Charaktere zu betrachten.

Definition 2.2.1 Sei ρ eine Darstellung von G in V. Dann heißt die Abbildung χ : G → C, welche durch

χ(s) = Spur(ρ(s))

definiert ist, der Charakter von ρ und ein Charakter von G. Charaktere von irreduziblen Darstellungen heißen irreduzible Charaktere.

Satz 2.2.2 (Eigenschaften von Charakteren):

1. Äquivalente Darstellungen haben den gleichen Charakter.

2. χ(1) = d = Grad(ρ).

3. χ(a^{−1}sa) = χ(s).

4. Sind χ_{1}, …, χ_{r} die Charaktere der Darstellungen ρ_{1}, …, ρ_{r}, dann hat ρ_{1} + … + ρ_{r} den Charakter χ_{1} + … + χ_{r}.

5. \overline{χ}(s) = χ(s^{−1}).

Beweis:

1. Ist ρ_{1} = τρ_{2}τ^{−1}, so gilt Spur (ρ_{1}) = Spur (ρ_{2}).

2. Spur (d-dimensionale Einheitsmatrix) = d.

3. Siehe 1.

4. Seien ρ_{1}, …, ρ_{r} bezüglich gewisser Basen beschrieben durch Matrizen R_{1}, …, R_{r}. Dann hat ρ_{1} + … + ρ_{r} die Matrix

( \begin{matrix}R_{1} \\ & . & . & . \\ & & & & R_{r} \end{matrix} ) ,

deren Spur gerade Spur (R_{1}) + … + Spur (R_{r}) ist.

5. Bezüglich eines geeigneten Skalarproduktes ist die Darstellung ρ unitär und damit

χ(s^{−1}) = Spur (ρ(s^{−1})) = Spur (ρ(s)^{∗}) = \overline{Spur(ρ(s))}
= \overline{χ}(s) .
□

In dem linearen Raum der komplexwertigen Funktionen auf G führen wir nun das Skalarprodukt

⟨φ, ψ⟩ = \frac{1}{|G|} ∑_{t∈G} φ(t)\overline{ψ}(t)

ein. Damit gilt

Satz 2.2.3 (Orthogonalität der Charaktere): Seien χ_{1}, χ_{2} die Charaktere der irreduziblen Darstellungen ρ_{1}, ρ_{2} von G. Dann gilt

⟨χ_{1}, χ_{2}⟩ = \{ \begin{matrix}1 & , & ρ_{1}, ρ_{2} äquivalent \\ 0 & , & sonst . \end{matrix}

Beweis: Seien χ_{1}, χ_{2} die Charaktere der Darstellungen ρ_{1}, ρ_{2} von G, und seien ρ_{1}, ρ_{2} bezüglich gewisser Basen beschrieben durch die Matrizen R^{1}, R^{2}. Dann ist

⟨χ_{1}, χ_{2}⟩ = \frac{1}{|G|} ∑_{t∈G} χ_{1}(t)\overline{χ}_{2}(t) = \frac{1}{|G|} ∑_{t∈G} χ_{1}(t)χ_{2}(t^{−1})
= ∑_{k,ℓ} \frac{1}{|G|} ∑_{t∈G} R_{kk}^{1}(t)R_{ℓℓ}^{2}(t^{−1}) .

Die Behauptung folgt aus Satz 2.1.10.

□

Für die direkte Summe von c zu einer Darstellung ρ äquivalenten Darstellungen schreiben wir in Zukunft einfach cρ. Mit dieser Schreibweise haben wir

Satz 2.2.4 Jede Darstellung ρ einer Gruppe G läßt sich eindeutig (bis auf die Reihenfolge) als direkte Summe

ρ = c_{1}ρ_{1} + … + c_{m}ρ_{m}

irreduzibler und paarweise nicht äquivalenter Darstellungen ρ_{1}, …, ρ_{m} schreiben. Sind χ, χ_{i} die Chraktere von ρ, ρ_{i}, so gilt

c_{i} = ⟨χ, ρ_{i}⟩ .

Beweis: Nach Satz 2.1.6 gibt es irreduzible Darstellungen ρ′_{1}, …, ρ′_{r}, so daß

ρ = ρ′_{1} + … + ρ′_{r} .

Sind χ′_{1}, …, χ′_{r} die Charaktere von ρ′_{1}, …, ρ′_{r}, so ist

⟨χ, χ′_{i}⟩ = ∑_{k=1}^{r}⟨χ′_{i}, χ′_{k}⟩ .

Nach 2.1.3 ist dies genau die Anzahl der zu ρ′_{i} äquivalenten Darstellungen unter den χ′_{1}, …, χ′_{r}. Fassen wir jeweils äquivalente Darstellungen zusammen, so folgt die Behauptung.

□

Definition 2.2.5 Die Zahlen c_{i} in Satz 2.2.4 heißen Vielfachheiten des Auftretens von ρ_{i} in ρ.

Satz 2.2.6 Darstellungen mit gleichem Charakter sind äquivalent.

Beweis: Seien ρ^{1}, ρ^{2} Darstellungen von G. Nach Satz 2.2.4 gibt es Zahlen c_{k}^{1}, c_{k}^{2} mit

ρ^{1} = ∑_{k=1}^{m} c_{k}^{1}ρ_{k} , ρ^{2} = ∑_{k=1}^{m} c_{k}^{2}ρ_{k} .

Dabei sind ρ_{1}, …, ρ_{m} irreduzible und paarweise nicht äquivalente Darstellungen von G und χ_{1}, …, χ_{m} ihre Charaktere. Haben nun ρ^{1}, ρ^{2} den gleichen Charakter χ, so gilt nach Satz 2.2.3

c_{k}^{1} = ⟨χ, χ_{k}⟩ = c_{k}^{2} .

Also sind ρ^{1}, ρ^{2} äquivalent.

□

Folgerung: Infolge von Satz 2.2.6 lassen sich die Orthogonalitätsrelationen der Charaktere (Satz 2.2.3) einfacher formulieren: Seien χ_{1}, χ_{2} irreduzible Charaktere einer Gruppe G. Dann gilt

⟨χ_{1}, χ_{2}⟩ = \{ \begin{matrix}1 & , & χ_{1} = χ_{2} , \\ 0 & , & sonst . \end{matrix}

Beispiel: Die Diedergruppe C_{n} besitzt für gerades n folgende Charaktere:

r^{k}  sr^{k} Bemerkungen
χ_{1}  1  1
χ_{2}  1  −1
χ_{3}  (−1)^{k}  (−1)^{k}
χ_{4}  (−1)^{k}  (−1)^{k+1}
χ_{5} 2 cos(2πhk/n)  0  h = 1, …, \frac{n}{2} − 1

Neben einer Reihe trivialer Beziehungen erhält man aus Satz 2.2.6 auch die Orthogonalitätsrelationen

∑_{k=0}^{n−1} cos(2πh_{1}k/n) cos(2πh_{2}k/n) = \{ \begin{matrix}\frac{n}{2} & , & h_{1} = h_{2} , \\ 0 & , & h_{1} ≠ h_{2} , \end{matrix}

mit 1 ≤ h_{1}, h_{2} < \frac{n}{2}.

Satz 2.2.7 Zu einer Gruppe G gibt es ein maximales endliches System irreduzibler paarweise inäquivalenter Darstellungen ρ_{1}, …, ρ_{m}. Jedes ρ_{i} ist in ρreg genau so oft enthalten, wie es sein Grad d_{i} angibt. Es ist

|G| = ∑_{i=1}^{m} d_{i}^{2} .  (2.2.1)

Beweis: Zunächst berechnen wir den regulären Charakter χreg der regulären Darstellung ρreg(s). Ist {e_{t_{1}}, …, e_{t_{n}}} eine Basis von V, so wird ρreg(s) beschrieben durch die Permutationsmatrix

P (s) = (e_{st_{1}}, …, e_{st_{n}}) ,

wo t_{1}, …, t_{n} die Elemente der Gruppe sind. Für s = 1 ist P (1) = I und damit χreg(1) = Spur (I) = |G|. Für s ≠ 1 hat P (s) in der Diagonale nur Nullen. Also χreg(s) = Spur (P (s)) = 0 für s ≠ 1.

Sei nun ρ_{1}, …, ρ_{m} ein System irreduzibler paarweise inäquivalenter Darstellungen von G und χ_{1}, …, χ_{m} die zugehörigen Charaktere. Dann ist

⟨χreg, χ_{i}⟩ = \frac{1}{|G|} ∑_{t∈G} χreg(t)\overline{χ}_{i}(t)
= \frac{1}{|G|} ∑_{t∈G} χreg(t)χ_{i}(t^{−1})
= χ_{i}(1) = d_{i} .

Wir können nach Satz 2.2.4 die ρ_{i} so wählen, daß

ρreg = ∑_{i=1}^{m} d_{i}ρ_{i} .

Bilden wir hiervon die Spur, so erhalten wir

|G| = χreg(1) = Spur (ρreg(1)) = ∑_{i=1}^{m} d_{i} Spur (ρ_{i}(1))

= ∑_{i=1}^{m} d_{i}χ_{i}(1) = ∑_{i=1}^{m} d_{i}^{2} .

Wäre nun ρ_{m+1} eine weitere irreduzible Darstellung von G, welche zu keinem der ρ_{1}, …, ρ_{m} äquivalent wäre, so wäre notwendig d_{m+1} = 0, ρ_{m+1} also vom Grade 0. Ein solches ρ_{m+1} kann es also nicht geben, d.h. ρ_{1}, …, ρ_{m} ist maximal.

Bemerkung: (2.1) charakterisiert also maximale Systeme paarweise inäquivalenter irreduzibler Darstellungen.

Satz 2.2.8 Ein Charakter χ ist genau dann irreduzibel, wenn ⟨χ, χ⟩ = 1.

Beweis: Sei χ der Charakter von ρ und ρ irreduzible. Dann ist ⟨χ, χ⟩ = 1 nach Satz 2.2.3. Sei umgekehrt ⟨χ, χ⟩ = 1. Sei ρ_{1}, …, ρ_{m} ein maximales System irreduzibler paarweise inäquivalenter Darstellungen und seien χ_{1}, …, χ_{m} die zugehörigen Charaktere. Dann gibt es ganze Zahlen c_{1}, …, c_{m} mit χ = c_{1}χ_{1} + … + c_{m}χ_{n}. Aus Satz 2.2.3 folgt

⟨χ, χ⟩ = ∑_{i=1}^{m} c_{i}^{2}⟨χ_{i}, χ_{i}⟩ .

Nun ist ⟨χ, χ⟩ = 1 und ⟨χ_{i}, χ_{i}⟩ = 1, weil die χ_{i} irreduzibel sind. Also gilt

1 = ∑_{i=1}^{m} c_{i}^{2} .

Da die c_{i} alle ganz sind, ist genau eines der c_{i} = 1, und alle anderen c_{i} sind Null. ρ ist also äquivalent zu einem der ρ_{i} und damit wie dieses irreduzibel. Also ist χ irreduzibel.

□

Beispiel: Wir wollen zeigen, daß das für D_{n}, n gerade, angegebene System von Darstellungen ein maximales System paarweise inäquivalenter irreduzibler Darstellungen ist.

Die Darstellungen ρ_{1}, …, ρ_{4} sind trivialerweise irreduzibel und paarweise nicht äquivalent. Wir haben oben schon nachgerechnet, daß

⟨χ_{5}^{h}, χ_{5}^{h}⟩ = \frac{2}{n} ∑_{k=0}^{n−1} cos^{2}(2πkh/n) = 1

ist für h = 1, …, \frac{n}{2} − 1. Wir haben damit

d_{1} = d_{2} = d_{3} = d_{4} = 1 , d_{5}^{h} = 2 , h = 1, …, \frac{n}{2} − 1

und damit

d_{1}^{2} + d_{2}^{2} + d_{3}^{2} + d_{4}^{2} = ∑_{h=1}^{\frac{n}{2} −1}(d_{5}^{h})^{2} = 2n = |G| .

Also haben wir ein maximales System.

Definition 2.2.9 a, b ∈ G heißen äquivalent, falls es s ∈ G gibt mit a = s^{−1}bs. Die zugehörigen Äquivalenzklassen seien A_{1}, …, A_{k}, und

es sei s ∈ A_{1}. Wir setzen g_{i} = |A_{i}| und g = |G|, also g = ∑_{i=1}^{k} g_{i}.

Eine Funktion h : G → C heißt Klassenfunktion, falls h auf jeder Äquivalenzklasse konstant ist.

Offenbar ist jeder Charakter von G eine Klassenfunktion. Der nächste Satz zeigt, daß dies im wesentlichen auch schon alle Klassenfunktionen sind.

Satz 2.2.10 Sei ρ_{1}, …, ρ_{m} ein maximales System irreduzibler und paarweise inäquivalenter Darstellungen von G und A_{1}, …, A_{k} wie in Definition 2.2.9. Dann gilt:

(i) m = k

(ii) Jede Klassenfunktion ist Linearkombination von Charakteren von G.

Beweis: Sei χ_{j} der Charakter von ρ_{j}. Dann können wir eine Funktion χ̃_{j} auf {A_{1}, ….A_{k}} definieren durch

χ̃_{j}(A_{i}) = \sqrt{\frac{g_{i}}{g}} χ_{j}(s) , s ∈ A_{i} .

Auf der Menge der Funktionen auf {A_{1}, …, A_{n}} definieren wir das Skalarprodukt

(u, v) = ∑_{i=1}^{k} u(A_{i})\overline{v}(A_{i}) .

Wir zeigen, daß die χ̃_{j} bezüglich dieses Skalarproduktes ein Orthonormalsystem ist. Es ist mit s_{i} ∈ A_{i}

⟨χ̃_{j}, χ̃_{ℓ}⟩ = ∑_{i=1}^{k} \sqrt{\frac{g_{i}}{g}} χ_{j}(s_{j})\sqrt{\frac{g_{i}}{g}} \overline{χ}_{ℓ}(s_{j})

= \frac{1}{g} ∑_{i=1}^{k} g_{i}χ_{j}(s_{i})\overline{χ}_{ℓ}(s_{i})

= \frac{1}{g} ∑_{i=1}^{k} ∑_{s∈A_{i}} χ_{j}(s)\overline{χ}_{ℓ}(s)

= \frac{1}{|G|} ∑_{s∈G} χ_{j}(s)\overline{χ}_{ℓ}(s)
= δ_{jℓ}

nach Satz 2.2.3.

Eine unmittelbare Folgerung ist m ≤ k. Denn k ist die Dimension des Raumes der Klassenfunktionen, und in diesem Raum gibt es die m linear unabhängigen Funktionen χ̃_{1}, …, χ̃_{m}.

Es bleibt zu zeigen, daß m ≥ k. Hierzu zeigen wir zunächst einmal: Ist ρ eine irreduzible Darstellung von G des Grades d und χ ihr Charakter, so gilt

\frac{1}{d}χ(a) = χ(b) = \frac{1}{|G|} ∑_{t∈G} χ(bt^{−1}at) .  (2.2.2)

Aus Satz 2.1.9 mit τ = ρ(a) und ρ_{1} = ρ_{2} = ρ folgt nämlich

τ′ = \frac{1}{|G|} ∑_{t∈G} ρ(t^{−1})ρ(a)ρ(t) = \frac{1}{d} Spur (τ) = \frac{χ(a)}{d} .

Linksmultiplikation mit ρ(b) ergibt

\frac{1}{|G|} ∑_{t∈G} ρ(bt^{−1}at) = \frac{χ(a)}{d}ρ(b) .

Gehen wir zum Charakter über, so folgt (2.2).

Wir wenden (2.2) an auf χ = χ_{ℓ}, a = s_{i} ∈ A_{i}, b^{−1} = s_{j} ∈ A_{j}, und summieren über ℓ. Es ergibt sich nach Satz 2.2.7

∑_{ℓ=1}^{m} χ_{ℓ}(s_{i})χ_{ℓ}(s_{j}^{−1}) = \frac{1}{|G|} ∑_{ℓ=1}^{n} d_{ℓ} ∑_{t∈G} χ_{ℓ}(s_{j}^{−1}t^{−1}s_{i}t)

= \frac{1}{|G|} ∑_{t∈G} ∑_{ℓ=1}^{n} d_{ℓ}χ_{ℓ}(s^{−1}t^{−1}s_{i}t)
= \frac{1}{|G|} ∑_{t∈G} χreg(s_{j}^{−1}t^{−1}s_{i}t) .

Da für i ≠ j die Elemente s_{i}, s_{j} aus verschiedenen Äquivalenzklassen sind, ist für i ≠ j stets s_{j}^{−1}t^{−1}s_{i} t ≠ 1. Also

χreg(s_{j}^{−1}t^{−1}s_{i}t) = 0

für i ≠ j und damit

∑_{ℓ=1}^{m} χ_{ℓ}(s_{i})\overline{χ}_{ℓ}(s_{j}) = 0  (2.2.3)

für i ≠ j. Wäre dies auch für i = j richtig, so wäre

∑_{ℓ=1}^{m} |χ_{ℓ}(s_{i})|^{2} = 0  (2.2.4)

und damit χ_{ℓ} = 0 auf A_{i} für ℓ = 1, …, m. Da ρ_{1}, …, ρ_{m} maximal sind, verschwände jeder Charakter auf A_{i}. Dies ist z.B. für den Einheitscharakter sicher nicht der Fall. Also kann (2.4) nicht richtig sein.

Zusammen mit (2.3) folgt dann, daß die k-Spalten der (m, k)-Matrix

( χ_{1}(s_{1}) , …, χ_{1}(s_{k}) ; ⋮ ; χ_{m}(s_{1}) , …, χ_{m}(s_{k}) )  (2.2.5)

linear unabhängig sind. Diese Matrix muß also mindestens k Zeilen haben. Damit ist m ≥ k gezeigt.

Daß jede Klassenfunktion sich als Linearkombination von Charakteren schreiben läßt, folgt nun unmittelbar aus der Tatsache, daß der Rang der Matrix (2.5) m = k ist.

□

2.3 Der Chinesische Restsatz

Sei R ein Ring mit Einselement, z.B. der Ring Z der ganzen Zahlen oder der Polynomring F [z] über einem Körper F. Ein Ring heißt kommutativ, wenn seine Multiplikation kommutativ ist. Ist R kommutativ, so sagen wir, a teilt b (a | b), falls es ein r gibt mit b = ar. Wir sagen a ≡ b mod p, falls p | a − b. Die Äquivalenzklassen dieser Äquivalenzrelation nennen wir Restklassen mod p. Diese bilden den Restklassenring R/p. Ein Ring heißt nullteilerfrei, wenn ab = 0 zur Folge hat, daß a = 0 oder b = 0.

Beispiele:

1) Z_{p} = Z/p = {0, 1, …, p−1}. In Z_{6} ist z.B. 2+5 = 1, 3·4 = 0. Also ist Z_{6} nicht nullteilerfrei. Aber Z_{p} ist nullteilerfrei für Primzahlen p.

2) Für den Ring F [z] und p = z^{n} + a_{1}z^{n−1} + … + a_{0} ist F [z]/p der Ring der Polynome vom Grade < n. Für p = z^{2} − 1 ist z.B. z(z + 1) = z^{2} + z ≡ 1 + z mod p.

3) Der Ring M_{n}[F] der (n, n)-Matrizen über F ist nicht nullteilerfrei:

( \begin{matrix}1 0 \\ 0 0 \end{matrix} ) ( \begin{matrix}0 0 \\ 0 1 \end{matrix} ) = ( \begin{matrix}0 0 \\ 0 0 \end{matrix} ) .

Definition 2.3.1 Ein kommutativer nullteilerfreier Ring R heißt euklidisch, wenn es für jedes a ∈ R, a ≠ 0, eine ganze Zahl g(a) ≥ 0 gibt mit

(i) g(ab) ≥ g(b)

(ii) Zu a, b ∈ R, a ≠ 0 gibt es q, r ∈ R

b = qa + r ,

wobei entweder r = 0 oder g(r) < g(a) ist.

Man nennt g den Grad.

Beispiele:

1) Z mit g(a) = |a| ist ein euklidischer Ring.

2) F [z] mit dem Polynomgrad als Grad ist ebenfalls euklidisch. Z.B.

ist

z^{3} + 2z^{2} + z + 1 = (z + 2)(z^{2} − 1) + 2z + 3

3) Der Ring Z + \sqrt{−3}Z ist nicht euklidisch.

Ein Element e ∈ R heißt Einheit, falls ein e′ ∈ R existiert mit ee′ = e′e = 1. Wir nennen e′ das Inverse zu e und schreiben e′ = e^{−1}. Beispiele:

1) Z hat die Einheiten +1, −1.

2) F [z] hat die Einheiten F mit Ausnahme der Null.

3) M_{n}[F] hat als Einheiten die invertierbaren Matrizen.

Ein Element p ∈ R heißt prim, falls p = p_{1}p_{2} nur möglich ist, wenn p_{1} oder p_{2} Einheit ist. Beispiele:

1) In Z sind genau die Elemente prim, für welche der Betrag eine Primzahl ist.

2) In F [z] nennt man die Primelemente irreduzibel über F. Z.B. ist

z^{2} − 1 = (z + 1)(z − 1) nicht prim für beliebiges F
z^{2} + 1  prim für F = IR, nicht prim für F = C
z^{2} − 2  prim für F = Γ = Körper der rationalen Zahlen,

aber nicht prim für F = R .

Folgende Sätze findet man in jedem Lehrbuch der Algebra.

Satz 2.3.2 In einem euklidischen Ring gibt es zu jedem Paar a, b ≠ 0 einen größten (im Sinne des Grades) gemeinsamen Teiler ggt(a, b). Es gibt p, q ∈ R mit ggt(a, b) = ap + bq.

Satz 2.3.3 In einem euklidischen Ring ist jedes Element eindeutig (bis auf Reihenfolge und Einheiten) als Produkt von Primelementen darstellbar.

Beispiele: In dem Ring Z+\sqrt{−3}Z gilt 4 = 2·2 = (1−\sqrt{−3})(1+\sqrt{−3}). Dieser Ring ist also nicht euklidisch.

Wir suchen nun Lösungen von simultanen Kongruenzen modulo p_{1}, …, p_{m}. Seien also a_{1}, …, a_{m} gegeben. Gesucht ist ein a mit

a ≡ a_{i} mod p_{i} ,  i = 1, …, m .  (2.3.1)

Der Chinesische Restsatz gibt ein Kriterium für Existenz und Eindeutigkeit von (3.1).

Satz 2.3.4 Sei R ein euklidischer Ring, und seien p_{1}, …, p_{n} ∈ R paarweise teilerfremd. Dann ist (3.1) für jede Wahl der a_{1}, …, a_{m} ∈ R lösbar. Die Lösung ist mod p_{1} … p_{m} eindeutig bestimmt.

Beweis: Wir zeigen zunächst: Die Gleichung ax ≡ b mod p ist genau dann lösbar, wenn ggt(a, p)|b. Ist diese Kongruenz nämlich lösbar, so gibt es y mit ax + py = b, und es folgt ggt(a, p)|b. Sei umgekehrt diese Bedingung erfüllt. Nach Satz 2.3.2 gibt es u, v mit ggt(a, p) = au + vp. Multiplikation mit q = b/ggt(a, p) ergibt b = aqu + qvp. Damit ist x = qu Lösung der Kongruenz.

Sei p = p_{1} … p_{m}. Dann ist ggt(\frac{p}{p_{i}} , p_{i}) = 1, und es gibt nach obigem ein x_{i} mit \frac{p}{p_{i}} x_{i} ≡ 1 mod p_{i}. Wir behaupten, daß

a = ∑_{i=1}^{n} \frac{p}{p_{i}} a_{i}x_{i}

Lösung von (3.1) ist. Wir schreiben für ein j

a = ∑_{i≠j} \frac{p}{p_{i}} a_{i}x_{i} + \frac{p}{p_{j}} a_{j}x_{j}

= p_{j} ∑_{i≠j} \frac{p}{p_{i}p_{j}} a_{i}x_{i} + a_{j} (\frac{p}{p_{j}} x_{j})

und dies ist kongruent a_{j} mod p_{j} nach Konstruktion von x_{j}.

Sind a, a′ Lösungen von (3.1), so ist a − a′ ≡ 0 mod p_{i} für i = 1, …, m und damit a ≡ a′ mod p.

□

Beispiel: R = R[z], p_{i} = z−z_{i}, z_{i} paarweise verschieden. Wir suchen ein a ∈ R mit a ≡ a_{i} mod p_{i}, d.h.

a(z_{i}) = d_{i} , i = 1, …, m .

Nach Satz 2.3.4 ist a modulo p = p_{1} … p_{m} eindeutig bestimmt. a ist also das Polynom vom Grad n − 1, das an den Stellen z_{i} die Werte a_{i} annimmt. a ergibt sich als

a = ∑_{i=1}^{m} \frac{p}{p_{i}} a_{i}x_{i} , \frac{p}{p_{i}} x_{i} ≡ 1 mode p_{i} .

Mit

ω_{i}(z) = \frac{p}{p_{i}} = ∏_{j≠i}(z − z_{j})

haben wir x_{i} = \frac{1}{ω_{i}(z_{i})} und damit

a = ∑_{i=1}^{m} \frac{ω_{i}(z)}{ω_{i}(z_{i})} a_{i} .

Dies ist die Lagrange’sche Interpolationsformel.

Seien R_{1}, R_{2} Ringe. Wir definieren dann einen weiteren Ring R_{1} ⊗ R_{2} folgendermaßen. R_{1} ⊗ R_{2} besteht aus den Paaren (a_{1}, a_{2}) mit a_{i} ∈ R_{i}.

Addition und Multiplikation in R_{1}⊗R_{2} sind komponentenweise erklärt, also

\begin{aligned}(a_{1}, a_{2}) + (b_{1}, b_{2}) & = & (a_{1} + b_{1}, a_{2} + b_{2}) \\ (a_{1}, a_{2})(b_{1}, b_{2}) & = & (a_{1}a_{2}, b_{1}b_{2}) . \end{aligned}

R_{1} ⊗ R_{2} heißt direktes Produkt von R_{1} und R_{2}.

Satz 2.3.5 Sei R ein euklidischer Ring und seien p_{1}, …, p_{m} paarweise teilerfremd. Sei p = p_{1} … p_{m}. Dann gilt

R/p = R/p_{1} ⊗ … ⊗ R/p_{m} .

Beweis: Wir definieren eine Abbildung φ : R/p_{1} ⊗ … R/p_{m} → R/p mit Hilfe des Satzes 2.3.4. Für (a_{1}, …, a_{m}) ∈ R/p_{1} ⊗ … ⊗ R/p_{m} sei a die Lösung aus (3.1). Diese ist in R/p wohlbestimmt. Ist (b_{1}, …, b_{m}) ∈ R/p_{1} ⊗ … ⊗ R/p_{m} und b die zugehörige Lösung von (3.1), so ist

\begin{aligned}a + b & ≡ & a_{i} + b_{i} & mod p_{i} \\ ab & ≡ & a_{i}b_{i} & mod p_{i} . \end{aligned}

φ ist also ein Ring-Homomorphismus. Ist a ∈ R und a_{i} ein Repräsentant von a mod p_{i}, so ist a = φ(a_{1}, …, a_{m}). Also ist φ surjektiv. Nach der Eindeutigkeitsaussage von Satz 2.3.4 ist φ injektiv. Also ist φ sogar ein Ring-Isomorphismus.

□

2.4 Gruppentheorie

Sei G eine endliche Gruppe und H eine Untergruppe von G. Dann können wir in G die Äquivalenzrelation

s ∼ t ⟺ t^{−1}s ∈ H

erklären. Sei s_{1}, …, s_{r} ein Repräsentantensystem dieser Äquivalenzrelation, also s_{1}H, …, s_{r}H die Äquivalenzklassen. Diese heißen (Links-) Nebenklassen von H. Es ist G = s_{1}H ∪ … ∪ s_{r}H und r|H| = |G|.

H heißt Normalteiler in G, falls tH = Ht für t ∈ G, d.h. falls die Linksnebenklassen gleich den Rechtsnebenklassen sind. Ist H Normalteiler von G, dann bilden die Nebenklassen wieder eine Gruppe, die Faktorgruppe G/H.

Sei a ∈ G. Die Ordnung m ist die kleinste natürliche Zahl m ≥ 1, für welche a^{m} = 1. Es bildet dann C_{m} = {1, a, a^{2}, …, a^{n−1}} eine Untergruppe von G der Ordnung m. C_{m} heißt zyklische Gruppe der Ordnung m. Sie ist isomorph der additiven Gruppe Z mod m.

Satz 2.4.1 Sei G abelsch, und haben a_{1}, …, a_{r} ∈ G die Ordnung m_{1}, …, m_{r}. Sei ggt(m_{i}, m_{j}) = 1 für i ≠ j. Dann hat a = a_{1} … a_{r} die Ordnung m = m_{1} · . . . · m_{r}.

Beweis: Sicher ist a^{m} = 1. Gäbe es ein n mit a^{n} = 1 und n < m, so könnten wir unter diesen n’s das kleinste wählen. Die n Elemente 1, …, a^{n−1} würden dann eine Untergruppe von C_{m} bilden, also n|m. Da die m_{i} paarweise teilerfremd sind, wäre sogar n|m_{i} für mindestens ein i, etwa i = 1. Dann wäre

a^{n} = a_{1}^{n}a_{2}^{n} … a_{r}^{n} = a_{2}^{n} … a_{r}^{n} = 1 .

Hätten wir die Behauptung für r−1 Faktoren schon bewiesen, so würde sie für r Faktoren folgen. Da r = 1 trivial ist, ist der Satz nach dem Prinzip der vollständigen Induktion bewiesen.

□

Ähnlich wie das direkte Produkt von Ringen ist das direkte Produkt von Gruppen definiert. Seien A, B Gruppen. Ihr direktes Produkt A⊗B besteht aus den Paaren (a, b) ∈ A × B mit kompetenterweiser Multiplikation: (a_{1}, b_{1})(a_{2}, b_{2}) = (a_{1}a_{2}, b_{1}b_{2}). Die Elemente (a, 1) bilden eine Untergruppe von A ⊗ B, die isomorph zu A ist. Wir schreiben A für diese Untergruppe, identifizieren also (a, 1) mit a. A wird so zu einer Untergruppe von A ⊗ B, und dasselbe gilt für B. Offenbar sind A, B sogar Normalteiler in A ⊗ B. Wegen (a, b) = (a, 1)(1, b) = (1, b)(a, 1) können wir ab oder ba für (a, b) schreiben. Damit haben wir folgende äquivalente Definition des direkten Produkts: Eine Gruppe G ist direktes Produkt seiner Untergruppen A, B genau dann, wenn

(i) Jedes g ∈ G sich eindeutig als g = ab mit a ∈ A, b ∈ B schreiben läßt.

(ii) ab = ba für a ∈ A, b ∈ B.

Satz 2.4.2 Seien n_{1}, n_{2} teilerfremd und n = n_{1}n_{2}. Dann ist

C_{n} = C_{n_{1}} ⊗ C_{n_{2}} .

Beweis: Wir identifizieren C_{n} mit der Gruppe Z mit Addition mod n. Dann können wir die Abbildung φ : C_{n_{1}} ⊗ C_{n_{2}} → C_{n} erklären durch φ(m_{1}, m_{2}) = m, wobei m die simultanen Kongruenzen m ≡ m_{i} mod n_{i}, i = 1, 2 löst. Da m mod n eindeutig bestimmt ist, ist φ injektiv. Da n_{1}, n_{2} teilerfremd sind, gibt es Zahlen q_{1}, q_{2} mit q_{1}n_{1} + q_{2}n_{2} = 1. Also ist (q_{1}m)n_{1} + (q_{2}m)n_{2} = m und damit m = φ(q_{2}mn_{2}, q_{1}mn_{1}) für jedes m ∈ C_{n}. Also ist φ surjektiv. Daß φ ein Homomorphismus ist, ist klar.

□ An Hand des Beispiels n_{1} = n_{2} = 2 macht sich leicht klar, daß die Voraussetzung n_{1}, n_{2} teilerfremd nicht gestrichen werden kann.

Sei M_{n} = {m ∈ Z : 1 ≤ m < n, ggt(m, n) = 1}. Mit der Multiplikation mod n wird M_{n} zur Gruppe. Es ist nämlich 1 ∈ M_{n}. Zu jedem m ∈ M_{n} kann man die Kongruenz x m ≡ 1 mod n lösen, und es ist ggt(x, n) = 1. Also ist x ∈ M_{n} und x = m^{−1}. Und schließlich ist offenbar m_{1}m_{2} ∈ M_{n}, falls m_{1}, m_{2} ∈ M_{n}.

Die Ordnung φ(n) = |M_{n}| heißt Euler’sche φ-Funktion, also

\begin{matrix}n & 2 & 3 & 4 & 5 & 6 \\ φ(n) & 1 & 2 & 2 & 4 & 3 \end{matrix}

Offenbar ist φ(p) = p − 1 für Primzahlen p, und φ(p^{r}) = p^{r} − p^{r−1} = (p − 1)p^{r−1}.

Satz 2.4.3 Sei p prim. Dann gilt

M_{p^{r}} = \{ \begin{matrix}C_{p^{n−1}(p−1)} & , & p > 2 , r ≥ 1 \\ C_{2} ⊗ C_{2^{r−2}} & , & p = 2 , r ≥ 2 \end{matrix}

Beweis: Siehe z.B. Hasse, Number Theory, Chapt. 4.5.

Für p > 2 ist M_{p^{r}} also zyklisch, d.h. es gibt a mit M_{p^{r}} = {1, a, …, a^{φ(p^{r})−1}}. Für r = 1 ist a die primitive Wurzel mod p. Diese finden sich für p < 10000 in Abramowitz/Stegun, Handbook of Mathematical Functions, pp. 864-869. Ein kleiner Auszug ist

\begin{matrix}p & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 \\ a & 2 & 2 & 3 & 2 & 2 & 3 & 2 & 5 \end{matrix}

Beispiele:

1) M_{5} = {1, 2, 3, 4}. Die Gruppentafel ist

1234 1 1234 2 2413 3 3142 4 4321

Nach Satz 2.4.3 ist M_{5} = C_{4} = {0, 1, 2, 3} mit Addition mod 4. Die Gruppentafel von C_{4} ist

0123 0 0123 1 1230 2 2301 3 3012

Die (i + 1)-te Zeile entsteht aus der i-ten durch Links-Ring-Schift.

Nach Satz 2.4.3 sind M_{5} und C_{4} isomorph. Die Isomoraphie wird hergestellt durch ein erzeugendes Element, etwa 2 aus der obigen Tabelle. Danach ist M_{5} = {1, 2, 3, 2^{2}, 2^{3}} = {1, 2, 4, 3}. Dadurch ergibt sich für M_{5} auch die Gruppentafel

1243 1 1243 2 2431 4 4312 5 3124

Diese Tafel ist in der Tat identisch zu der obigen Tafel von C_{4}: Die (i + 1)-te Zeile ergibt sich durch Links-Ring-Schift aus der i-ten Zeile.

2) M_{9} = {1, 2, 4, 5, 7, 8} hat als erzeugendes Element die Zahl 5, also M_{9} = C_{6} = {1, 5, 5^{2}, 5^{3}, 5^{4}, 5^{5}} = {1, 5, 7, 8, 4, 2}. Die Gruppentafel von M_{9} ist 40 KAPITEL 2. ALGEBRA

157842

1 157842
5 578421
7 784215
8 842157
4 421578
2 215784

Schnelle Fourier-Transformation

3.1 Fourier-Transformation und Faltung

Die diskrete Fouriertransformation, oder Fourier-Transformation der Länge n, ist definiert durch

ŷ_{k} = ∑_{j=0}^{n−1} e^{−2πijk/n}y_{j} , k = 0, …, n − 1 .

Mit Hilfe der Orthogonalitätsrelationen

\frac{1}{n} ∑_{j=0}^{n−1} e^{2πijk/n} = \{ \begin{matrix}1 & , & k = 0 , ±n , ±2n, …, \\ 0 & , & sonst \end{matrix}

zeigt man leicht die Inversionsformel

y_{j} = \frac{1}{n} ∑_{k=0}^{n−1} e^{2πijk/n}ŷ_{k} , j = 0, …, n − 1 .

Die Fourier-Transformation ist also eine lineare Abbildung in C^{n} mit der Matrix

W = ( 1 1  1  ⋯ 1 ; 1 ω  ω^{2}  ⋯ ω^{n−1} ; 1 ω^{2} ω^{4}  ⋯ ω^{2(n−1)} ; ⋮ ; 1 ω^{n−1} ω^{(n−1)2} ⋯ ω^{(n−1)(n−1)} ) , ω = e^{2πij/n} .

Wegen ω^{n} = 1 kann in dem Exponenten in W^{n} mod n gerechnet werden. Die Orthogonalitätsrelationen ergeben

W_{n}W_{n}^{∗} = nI .

Insbesondere ist also \frac{1}{\sqrt{n}}W_{n} eine Isometrie.

Für zwei Vektoren x, y ∈ C^{n}, deren Komponenten wir von 0 bis n − 1 numerieren, nennen wir den Vektor z mit den Komponenten

z_{k} = ∑_{j=0}^{n−1} x_{k−j}y_{j} , k = 0, …, n − 1

die (zyklische) Faltung von x und y. Dabei rechnen wir im Index von x mod n. Wir schreiben z = x ∗ y. In Matrix-Form lautet die Faltung z = Xy

X = ( x_{0} x_{n−1} ⋯ x_{1} ; x_{1} x_{0} ⋯ x_{2} ; ⋮ ; x_{n−1} x_{n−2} ⋯ x_{0} ) .

Die (i+1)-te Zeile dieser Matrix entsteht also aus der i-ten durch einen Rechts-Ring-Schift.

Satz 3.1.1 (Faltungssatz) Für x, y ∈ Z^{n} gilt

(x ∗ y)_{k}^{∧} = x̂_{k}ŷ_{k} , k = 0, …, n − 1 .

Beweis: Auch dies ist eine unmittelbare Folgerung aus den Orthogonalitätsrelationen.

□

3.2 Cooley-Tukey

Wir beschreiben nun verschiedene Versionen der schnellen Fourier-Transformation nach Cooley-Tukey. Wir nehmen an, die Länge n der Fourier-Transformation faktoriere gemäß n = mp. Den Fall p = 2 haben wir teilweise schon in der Einleitung behandelt.

1. Dezimierung in der Zeit

Wir haben auswerten

ŷ_{k} = ∑_{j=0}^{n−1} ω_{n}^{jk}y_{j} , k = 0, …, n − 1 ,

wo ω_{n} = e^{−2πi/n} eine n-te Einheitswurzel ist. Wir fassen in der Summe diejenigen Indizes j zusammen, welche der gleichen Restklasse mod p angehören. Dies ergibt

ŷ_{k} = ∑_{r=0}^{p−1} ∑_{ℓ=0}^{m−1} ω_{n}^{(pℓ+r)k}y_{pℓ+r} .

Nun ist ω_{n}^{p} = ω_{m}. Also folgt

ŷ_{k} = ∑_{r=0}^{p−1} ω_{n}^{rk} ∑_{ℓ=0}^{m−1} ω_{m}^{ℓk}y_{pℓ+r} .

Führen wir die Vektoren

y^{r} = ( y_{r} ; y_{p+r} ; ⋮ ; y_{(m−1)p+r} ) ∈ C^{m} , r = 0, …, p − 1

ein, so lautet dies

ŷ_{k} = ∑_{r=0}^{p−1} ω_{n}^{rk}(ŷ^{r})_{k} ,

wo ŷ^{r} die Fourier-Transformation der Länge m von y^{r} bedeutet. Diese hat die Periode m. Also gilt

ŷ_{k+ℓm} = ∑_{r=0}^{p−1} ω_{n}^{(k+ℓm)r}(ŷ^{r})_{k} , k = 0, …, m − 1 , ℓ = 0, …, p − 1

und wegen ω_{n}^{m} = ω_{p}

ŷ_{k+ℓm} = ∑_{r=0}^{p−1} ω_{p}^{ℓr}ω_{n}^{kℓ}(ŷ^{r})_{k} .  (3.2.1)

Bis auf die Multiplikation mit ω_{n}^{kℓ} sind dies m Fourier-Transformationen der Länge p. Die Fourier - Transformation der Länge n kann also ausgeführt werden durch p Fourier-Transformationen der Länge m und m Fourier-Transformationen der Länge p, zuzüglich einiger Multiplikationen mit Einheitswurzeln und Permutationen.

Wir wollen (3.2.1) in Matrixform schreiben. Mit W_{n}, W_{m}, W_{p} die Fourier-Transformation der Längen n, m, p und

D_{n} = ( \begin{matrix}1 \\ & ω_{n} \\ & & . & . & . \\ & & & & & ω_{n}^{m−1} \end{matrix} )

lautet (3.2.1), wenn wir zunächst die m Gleichungen für ℓ = 0, dann die m Gleichungen für ℓ = 1 usw. aufschreiben,

ŷ = ( \begin{matrix}I_{m} & I_{m} & ⋯ & I_{m} \\ I_{m} & ω_{p}I_{m} & ⋯ & ω_{p}^{p−1}I_{m} \\ ⋮ & ⋮ \\ I_{m} & ω_{p}^{p−1}I_{m} & ⋯ & ω^{(p−1)^{2}}I_{m} \end{matrix} ) ( \begin{matrix}D_{m}^{0} & & & & & O \\ & D_{m}^{1} \\ & & . & . & . \\ O & & & & & D_{m}^{p−1} \end{matrix} ) ∗  (3.2.2)

∗ ( \begin{matrix}W_{m} & & & & & O \\ & W_{m} \\ & & . & . & . \\ O & & & & & W_{m} \end{matrix} ) ( y^{0} ; y^{1} ; ⋮ ; y^{p−1} ) .

Hier führen wir folgende Schreibweise ein. Ist A eine (m, n)-Matrix und B eine (p, q)-Matrix, so bezeichnet das Tensorprodukt A ⊗ B die (mp, nq)-Matrix

( a_{11}B a_{12}B ⋯ a_{1m}B ; ⋮ ; a_{m1}B a_{m2}B ⋯ a_{mn}B ) .

Damit lautet (3.2.2)

W_{n} = (W_{p} ⊗ I_{m}) ( \begin{matrix}D_{m}^{0} \\ & D_{m}^{1} \\ & & . & . & . \\ & & & & & D_{m}^{p−1} \end{matrix} ) (I_{p} ⊗ W_{m})P_{p,m} (3.2.3)

mit einer Permutationsmatrix P_{p,m}. Ist y = (y_{0}, …, y_{n−1})^{T}, so ist P_{p,m}y der Vektor

(y_{0}, y_{p}, …, y_{(n−1)p}, y_{1}, y_{p+1}, …, y_{(m−1)p+1}, …, y_{m−1}, y_{p+m−1}, …, y_{(m−1)p+n−1}) .

Anders ausgedrückt: Ist 0 ≤ i < n und i = mq + r mit ganzen Zahlen 0 ≤ q < p, 0 ≤ r < m (Division mit Rest), so ist

(P y)_{i} = y_{rp+q} .

Ist n ein Produkt kleiner Faktoren, so nennt man n F T -freundlich. Wiederholte Anwendungen von (3.2.4) führt dann zu einem effizienten Algorithmus.

Das einfachste Beispiel von F T -freundlichen Zahlen sind Potenzen von

2. Diesen Fall wollen wir nun etwas ausführlicher betrachten. Wir führen dazu den butterfly der Ordnung m ein als die (m, m)-Matrix

B_{m} = ( \begin{matrix}I_{m/2} & D_{m/2} \\ I_{m/2} & −D_{m/2} \end{matrix} )

ein. Für p = 2 lautet (3.2.4)

\begin{aligned}W_{n} & = & (W_{2} ⊗ I_{n/2}) ( \begin{matrix}I_{n/2} & O \\ O & D_{n/2} \end{matrix} ) (I_{2} ⊗ W_{n/2})P_{2,n/2} \\ & = & B_{n}(I_{2} ⊗ W_{n/2})P_{2,n/2} . \end{aligned}

Rekursive Anwendung ergibt

W_{n} = B_{n}(I_{2} ⊗ B_{n/2})(I_{4} ⊗ W_{n/4})(I_{2} ⊗ P_{2,n/4})P_{2,n/2}
⋮
= (I_{1} ⊗ B_{n})(I_{2} ⊗ B_{n/2})(I_{4} ⊗ B_{n/4}) ⋯ (I_{n/2} ⊗ B_{2})P_{n}(3.2.4)
P_{n} =  (I_{n/4} ⊗ P_{2/2}) · · · · · (I_{2,n/4})(I_{1} ⊗ P_{2,n/2}) .  (3.2.5)

Dies ist die Radix-2-Version der Cooley-Tukey F F T.

Die Permutation P_{n} kann durch bitreversal angewendet werden. Die bitreversal-Funktion r_{n} von {0, …, n − 1} in sich ist für n = 2^{t} wie folgt definiert. Sei (b_{t−1}, …, b_{0})_{2} die Dualdarstellung von k, also

k = b_{t−1}2^{t−1} + ⋯ + b_{1}2 + b_{0}

mit b_{i} ∈ {0, 1}. Dann ist r_{n}(k) = (b_{0}, …, b_{t−1})_{2}.

Satz 3.2.1 Die Komponenten von x, P_{n}x seien von 0 bis n − 1 numeriert, und n = 2^{t}. Dann gilt

(P x)_{k} = x_{r_{n}(k)} , k = 0, …, n − 1 .

Beweis: Für t = 1 ist P_{2} = I_{2} und die Behauptung trivial. Sei die Behauptung richtig für t − 1, und sei m = 2^{t−1}.

Nach (3.2.5) ist

P_{n}x = (I_{2} ⊗ P_{m})P_{2,m}x = ( \begin{matrix}P_{m} & ( x_{0} ; x_{2} ; ⋮ ; x_{m−2} ) \\ P_{m} & ( x_{1} ; x_{3} ; ⋮ ; x_{m−1} ) \end{matrix} ) .

Nach Induktionsannahme können wir P_{m} durch bitreversal auswerten. Ist also k = (b_{t−2}, …, b_{0})_{2} und k′ = (b_{0}, …, b_{t−2})_{2}, so ist

(P_{m} ( x_{0} ; x_{2} ; ⋮ ; x_{m−1} ))_{k} = x_{2k′} , (P_{m} ( x_{1} ; x_{3} ; ⋮ ; x_{m−1} ))_{k} = x_{2k′+1} .

Nun ist aber für k = 0, …, m − 1

k = (0, b_{t−2}, …, b_{0})_{2} , 2k′ = (b_{t−2}, …, b_{0}, 0)_{2}

und für k = m, …, n − 1

k = (1, b_{t−2}, …, b_{0})_{2} , 2k′ + 1 = (b_{t−2}, …, b_{0}, 1)_{2} .

In jedem Fall erhält man den Index von x also durch bitreversal.

□

2. Dezimierung in der Frequenz

Jetzt fassen wir die Indizes k, welche zur gleichen Restklasse mod m gehören, zusammen, schreiben also

ŷ_{mℓ+r} = ∑_{j=0}^{n−1} ω_{n}^{j(mℓ+r)}y_{j}

= ∑_{j=0}^{n−1} ω_{n}^{jr}y_{j}

= ∑_{k=0}^{m−1} ∑_{j=0}^{p−1} ω_{p}^{j+kp)ℓ}ω_{n}^{(j+kp)r}y_{j+kp}

= ∑_{k=0}^{m−1} ω_{m}^{kr} ∑_{j=0}^{p−1} ω_{p}^{jℓ}ω_{n}^{rj}y_{j+kp} ,

wobei wir wieder ω_{n}^{p} = ω_{m} und ω_{n}^{m} = ω_{p} benutzt haben. Dieses Mal setzen wir

y^{k} = ( y_{kp} ; y_{kp+1} ; ⋮ ; y_{kp+p−1} ) ∈ C^{p} , k = 0, …, m − 1 .

Dann können wir schreiben

ŷ_{mℓ+r} = ∑_{k=0}^{m−1} ω_{m}^{kr} (D_{p}^{r}y^{k})_{ℓ}^{∧} ,

wobei rechts die Fourier-Transformation der Länge p steht und D_{p} entsprechend zu D_{m} erklärt ist. Schreiben wir diese Gleichungen erst für r = 0, dann für r = 1 usw. hin, dann entsteht

P_{m,p}ŷ = ( W_{p}D_{p}^{0}y^{0}  +  W_{p}D_{p}^{0}y^{1} + ⋯ +  W_{p}D_{p}^{0}y^{m−1} ; W_{p}D_{p}^{1}y^{0}  + ω_{m}W_{p}D_{p}^{1}y^{1} + ⋯ +  ω_{m}^{m−1}W_{p}D_{p}^{1}y^{m−1} ; ⋮ ; W_{p}D_{p}^{m−1}y^{0} + W_{p}D_{p}^{m−1}y^{1} + ⋯ + ω^{(m−1)^{2}}W_{p}D_{p}^{m−1}y^{m−1} )

= ( \begin{matrix}W_{p} \\ & W_{p} \\ & & . & . & . \\ & & & & & W_{p} \end{matrix} ) ( \begin{matrix}D_{p}^{0} \\ & D_{p}^{1} \\ & & . & . & . \\ & & & & & D_{p}^{m−1} \end{matrix} ) ∗

∗ ( I_{p} I_{p} ⋯ I_{p} ; I_{p} ω_{n}I_{p} ⋯ ω_{m}^{m−1}I_{p} ; ⋮ ; I_{p} ω_{n}^{m−1}I_{p} ⋯ ω_{m}^{(m−1)}I_{p} ) ( y^{0} ; y^{1} ; ⋮ ; y^{m−1} )

oder

P_{m,p}W_{n} = (I_{m} ⊗ W_{p}) ( \begin{matrix}D_{p}^{0} \\ & D_{p}^{1} \\ & & . & . & . \\ & & & & & D_{p}^{m−1} \end{matrix} ) (W_{m} ⊗ I_{p}) . (3.2.6)

3.2. COOLEY-TUKEY 49 Mit Hilfe von

P_{m,p}^{T} = P_{m,p}^{−1} = P_{p,m}  (3.2.7)

sieht man, daß (3.2.7) unmittelbar aus (3.2.4) folgt. Durch Transposition von (3.2.7) ergibt sich ja

W_{n}P_{m,p}^{T} = (W_{m} ⊗ I_{p}) ( \begin{matrix}D_{p}^{0} \\ & D_{p}^{1} \\ & & . & . & . \\ & & & & & D_{p}^{m−1} \end{matrix} ) (I_{n} ⊗ W_{p}) .

Wegen (3.2.7) ist dies identisch zu (3.2.3) mit vertauschten m, p.

3.3 Primfaktoren

Die Good’sche oder Primfaktor-FFT benutzt wie Cooley-Tukey auch eine Faktorisierung n = mp der Länge n. Die Faktoren m, p müssen jetzt aber teilerfremd sein. Wir beginnen mit dem Beispiel n = G = 2·3. Wir schreiben W_{6} in der Form

W_{6} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 2 & 4 & 0 & 2 & 4 \\ 0 & 3 & 0 & 3 & 0 & 3 \\ 0 & 4 & 2 & 0 & 4 & 2 \\ 0 & 5 & 4 & 3 & 2 & 1 \end{matrix} ) ,

d.h. wir notieren an der Stelle (k, ℓ) nicht ω_{6}^{kℓ} = e^{−2πi(k+ℓ)/6}, sondern nur k + ℓ mod 6. Ordnen wir die Zeilen von W_{6} in der Reihenfolge 0, 3, 4, 1, 2, 5 und die Spalten in der Reihenfolge 0, 3, 2, 5, 4, 1 an, so entsteht

W′_{6} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 3 & 0 & 3 \\ 0 & 0 & 2 & 2 & 4 & 4 \\ 0 & 3 & 2 & 5 & 4 & 1 \\ 0 & 0 & 4 & 4 & 2 & 2 \\ 0 & 3 & 4 & 1 & 2 & 5 \end{matrix} ) = ( \begin{matrix}1 & 1 & 1 \\ 1 & ω_{3} & ω_{3}^{2} \\ 1 & ω_{3}^{2} & ω_{5} \end{matrix} ) ⊗ ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ) .

Bis auf Zeilen- und Spaltenvertauschungen ist W_{6}, also das Tensor-Produkt von W_{3} und W_{2}. W_{6} kann also ausgeführt werden durch 3 Fourier - Transformation der Länge 2 und 2 Fourier-Transformation der Länge 3.

Satz 3.3.1 Sei n = n_{1}n_{2} und ggt(n_{1}, n_{2}) = 1. Dann gibt es Permutationsmatrizen P, Q, so daß

W_{n} = Q^{T} (W_{n_{1}} ⊗ W_{n_{2}})P .

Beweis: Wegen ggt(n_{1}, n_{2}) = 1 können wir zu j mit 0 ≤ j < Zahlen j_{1}, j_{2} mit 0 ≤ j_{1} < n_{1}, 0 ≤ j_{2} < n_{2} finden mit j = n_{1}j_{2} + n_{2}j_{1} mod n, und ebenso k = n_{1}k_{2} + n_{2}k_{1} mod n. Aus

ŷ_{k} = ∑_{j=0}^{n−1} ω^{jk}y_{j} , ω = e^{−2πi/n} , k = 0, …, n − 1

wird dann

ŷ_{n_{1}k_{2}+n_{2}k_{1}} = ∑_{j_{1}=0}^{n_{1}−1} ∑_{j_{2}=0}^{n_{2}−1} ω^{(n_{1}j_{2}+n_{2}j_{1})(n_{1}k_{2}+n_{2}k_{1})}y_{n_{1}j_{1}+n_{2}j_{1}} .

Mit ω^{n_{1}n_{2}} = 1, ω^{n_{1}} = e^{−2πi/n_{2}} = ω_{2}, ω^{n_{2}} = e^{−2πi/n_{1}} = ω_{1} folgt

ŷ_{n_{1}k_{2}+n_{2}k_{1}} = ∑_{j_{1}=0}^{n_{1}−1} ω_{1}^{n_{2}j_{1}k_{1}} ∑_{j_{2}=0}^{n_{2}−1} ω_{2}^{n_{1}j_{2}k_{2}}y_{n_{1}j_{2}+n_{2}j_{1}} .

Hier ist 0 ≤ k_{1} < n_{1}, 0 ≤ k_{2} < n_{2}. Zu jedem solchen Paar k_{1}, k_{2} können wir genau ein Paar (k′_{1}, k′_{2}) finden, so daß

n_{1}k′_{2} ≡ k_{2} mod n_{2} , n_{2}k′_{1} ≡ k_{1} mod n_{1} ,  (3.3.1)

denn ggt(n_{1}, n_{2}) = 1. Mit diesen Zahlen k′_{1}, k′_{2} gilt dann

ŷ_{n_{1}k′_{2}+n_{2}k′_{1}} = ∑_{j_{1}=0}^{n_{1}−1} ω_{1}^{n_{2}j_{1}k′_{1}} ∑_{j_{2}=0}^{n_{2}−1} ω_{2}^{n_{1}j_{2}k′_{2}}y_{n_{1}j_{2}+n_{2}j_{1}} .

Aufgrund der Wahl von k′_{1}, k′_{2} und wegen ω_{1}^{n_{1}} = ω_{2}^{n_{2}} = 1 gilt

ω_{1}^{n_{2}k′_{1}} = ω_{1}^{k_{1}} , ω^{n_{1}k′_{2}} = ω_{2}^{k_{2}} ,

also

ŷ_{n_{1}k′_{2}+n_{2}k′_{1}} = ∑_{j_{1}=0}^{n_{1}−1} ω_{1}^{j_{1}k_{1}} ∑_{j_{2}=0}^{n_{2}−1} ω_{2}^{j_{2}k_{2}}y_{n_{1}j_{2}+n_{2}j_{1}} .

Mit den n_{2}-Vektoren

\begin{aligned}y^{j_{1}} & = & (y_{n_{1}j_{2}+n_{2}j_{1}})_{0≤j_{2}<n_{2}} , \\ ŷ^{k_{1}} & = & (ŷ^{n_{1}k′_{2}+n_{2}k′_{1}})_{0≤k_{2}<n_{2}} \end{aligned}

lautet dies mit W_{2} = W_{n_{2}}

(ŷ^{k_{1}})_{k_{2}} = ∑_{j_{1}=0}^{n_{1}−1} ω_{1}^{j_{1}k_{1}}(W_{2}y^{j_{1}})_{k_{2}}

oder

( ŷ^{0} ; ⋮ ; ŷ^{n_{1}−1} ) = ( W_{2}  W_{2}  ⋯  W_{2} ; W_{2} ω_{1}W_{2} ⋯ ω_{1}^{n_{1}−1}W_{2} ; ⋮ ; W_{2} ω_{1}^{n_{1}−1}W_{2} ⋯ ω_{1}^{(n_{1}−1)^{2}}W_{2} ) ( y^{0} ; ⋮ ; y^{n_{1}−1} ) .

Also, mit W_{1} = W_{n_{1}},

Qŷ = W_{1} ⊗ W_{2}P y ,

und dies ist die Behauptung.

□

Dem Beweis kann man die Permutationen P, Q entnehmen. Es ist mit j = n_{2}j_{1} + j_{2}, 0 ≤ j_{2} < n_{2} (Division mit Rest)

(P y)_{j} = y_{n_{1}j_{2}+n_{2}j_{1}} .

Entsprechend ist mit k = n_{2}k_{1} + k_{2}, 0 ≤ k_{2} < n_{2},

(Qŷ)_{k} = ŷ_{n_{1}k′_{2}+n_{2}k′_{1}} .

Dabei sind k′_{1}, k′_{2} zu k_{1}, k_{2} gemäß (3.3.1) bestimmt. In jedem Fall ist in den Indizes mod n zu rechnen.

Beispiel: n = 2 · 3, also n_{1} = 2, n_{2} = 3. Wir berechnen P

\begin{matrix}j & j_{1} & j_{2} & n_{1}j_{2} + n_{2}j_{1} \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 \\ 2 & 0 & 2 & 4 \\ 3 & 1 & 0 & 3 \\ 4 & 1 & 1 & 5 \\ 5 & 1 & 2 & 1 \end{matrix} , also P ( \begin{matrix}0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{matrix} ) = ( \begin{matrix}0 \\ 2 \\ 4 \\ 3 \\ 5 \\ 1 \end{matrix} )

und Q

\begin{aligned}k & & k_{1} & k_{2} & k′_{1} & k′_{2} & n_{1}k′_{2} + n_{2}k′_{1} \\ & 0 & 0 & 0 & 0 & 0 & 0 \\ & 1 & 0 & 1 & 0 & 2 & 4 \\ & 2 & 0 & 2 & 0 & 1 & 2 \\ & 3 & 1 & 0 & 1 & 0 & 3 \\ & 4 & 1 & 1 & 1 & 2 & 1 \\ & 5 & 1 & 2 & 1 & 1 & 5 \end{aligned} , also Q ( \begin{matrix}0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{matrix} ) = ( \begin{matrix}0 \\ 4 \\ 2 \\ 3 \\ 1 \\ 5 \end{matrix} ) .

Wir bilden QW_{6}P^{T}, d.h. wir vertauschen die Zeilen gemäß Q und die Spalten gemäß P:

( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 2 & 4 & 0 & 2 & 4 \\ 0 & 3 & 0 & 3 & 0 & 3 \\ 0 & 4 & 2 & 0 & 4 & 2 \\ 0 & 5 & 4 & 3 & 2 & 1 \end{matrix} ) →^{Q} ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 2 & 0 & 4 & 2 \\ 0 & 2 & 4 & 0 & 2 & 4 \\ 0 & 3 & 0 & 3 & 0 & 3 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 5 & 4 & 3 & 2 & 1 \end{matrix} ) →^{P} ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 4 & 0 & 2 & 4 \\ 0 & 4 & 2 & 0 & 4 & 2 \\ 0 & 0 & 0 & 3 & 3 & 3 \\ 0 & 2 & 4 & 3 & 5 & 1 \\ 0 & 4 & 2 & 3 & 1 & 5 \end{matrix} ) = W_{2}⊗W_{3}

Oben haben wir schon den Fall n_{1} = 3, n_{2} = 2 behandelt.

Folgerung: Seien M(n), A(n) die Anzahl der Multiplikationen bzw. Additionen zur Fourier-Transformation der Länge n. Sei n = n_{1}n_{2} mit ggt(n_{1}, n_{2}) = 1. Dann gilt

\begin{aligned}M(n) & = & n_{1}M(n_{2}) + n_{2}M(n_{1}) \\ A(n) & = & n_{1}A(n_{2}) + n_{2}A(n_{1}) \end{aligned}

Wir wollen die entsprechenden Überlegungen nun für die Faltung der Länge n, also

z_{k} = ∑_{j=0}^{n−1} x_{k−j}y_{j} , k = 0, …, n − 1  (3.3.2)

durchführen. Äquivalent hierzu ist die Anwendung der Matrix

X_{n} = ( x_{0} x_{n−1} ⋯  x_{1} ; x_{1} x_{0} x_{n−1} ⋯ x_{2} ; ⋮ ; x_{n−1} x_{n−2} ⋯  x_{0} )

auf den Vektor y.

Satz 3.3.2 Sei n = n_{1}, n_{2} und ggt(n_{1}, n_{2}) = 1. Dann gibt es eine Permutationsmatrix P und Faltungen F_{0}, …, F_{n_{1}−1} der Länge n_{2}, so daß

X_{n} = P^{T} ( F_{0}  F_{n_{1}−1} …  F_{1} ; F_{1}  F_{0}  F_{n_{1}−1} … F_{2} ; ⋮ ; F_{n_{1}−1} F_{n_{1}−1} ⋯  F_{0} ) P .

Beweis: Für 0 ≤ k, j < n können wir mod n

\begin{matrix}k = k_{2}n_{1} + k_{1}n_{2} & , & j = j_{2}n_{1} + j_{1}n_{2} , \\ 0 ≤ j_{1}, k_{1} < n_{1} & , & 0 ≤ j_{2}, k_{2} < n_{2} \end{matrix}

schreiben, und zwar in eindeutiger Weise. Damit lautet (3.3.1)

z_{k_{2}n_{1}+k_{1}n_{2}} = ∑_{j_{1}=0}^{n_{1}−1} ∑_{j_{2}=0}^{n_{2}−1} x_{(k_{1}−j_{1})n_{2}+(k_{2}−j_{2})n_{2}}y_{j_{1}n_{2}+j_{2}n_{1}} .

Dabei wird in den Indizes mod n gerechnet. Die j_{2}-Summe ist eine Faltung der n_{2}-Vektoren

y^{j_{1}} = (y_{j_{1}n_{2}+j_{2}n_{1}})_{0≤j_{2}<n_{2}} , f^{k_{1}−j_{1}} = (x_{(k_{1}−j_{1})n_{2}+j_{2}n_{1}})_{0≤k<n_{2}} .

Mit dem n_{2}-Vektor

z^{k_{1}} = (z_{k_{2}n_{1}+k_{1}n_{2}})_{0≤k_{2}<n_{2}}

können wir daher schreiben

( z^{0} ; ⋮ ; z^{n_{1}−1} ) = ( \begin{matrix}F_{0} & F_{n_{1}−1} & ⋯ & & F_{1} \\ F_{1} & F_{0} & F_{n_{1}−1} & ⋯ & F_{2} \\ ⋯ \\ F_{n_{1}−1} & F_{n_{1}−2} & ⋯ & & F_{0} \end{matrix} ) ( y^{0} ; ⋮ ; y^{n_{1}−1} ) .

Dies ist die Behauptung.

□

Der Beweis ergibt eine explizite Darstellung für P. Setzen wir für 0 ≤ j < n j = j_{1}n_{2} + j_{2}, 0 ≤ j_{1} < n_{1}, 0 ≤ j_{2} < n_{2}, so ist

(P y)_{j} = y_{j_{1}n_{2}+j_{2}n_{1}} .

Beispiel: n = 2 · 3, also n_{1} = 2, n_{2} = 3. P bewirkt die Permutation (0, 1, 2, 3, 4, 5) → (0, 2, 4, 3, 5, 1). Entsprechende Vertauschungen von Zeilen und Spalten ergibt

( \begin{matrix}0 & 5 & 4 & 3 & 2 & 1 \\ 1 & 0 & 5 & 4 & 3 & 2 \\ 2 & 1 & 0 & 5 & 4 & 3 \\ 3 & 2 & 1 & 0 & 5 & 4 \\ 4 & 3 & 2 & 1 & 0 & 5 \\ 5 & 4 & 3 & 2 & 1 & 0 \end{matrix} ) → ( \begin{matrix}0 & 5 & 4 & 3 & 2 & 1 \\ 2 & 1 & 0 & 5 & 4 & 3 \\ 4 & 3 & 2 & 1 & 0 & 5 \\ 3 & 2 & 1 & 0 & 5 & 4 \\ 5 & 4 & 3 & 2 & 1 & 0 \\ 1 & 0 & 5 & 4 & 3 & 2 \end{matrix} ) → ( \begin{matrix}0 & 4 & 2 & 3 & 1 & 5 \\ 2 & 0 & 4 & 5 & 3 & 1 \\ 4 & 2 & 0 & 1 & 5 & 3 \\ 3 & 1 & 5 & 0 & 4 & 2 \\ 5 & 3 & 1 & 2 & 0 & 4 \\ 1 & 5 & 3 & 4 & 2 & 0 \end{matrix} )

= ( \begin{matrix}F^{0} & F^{1} \\ F^{1} & F^{0} \end{matrix} )

mit Faltungen F^{ℓ} der Länge 3.

Folgerung: Sei n = n_{1}n_{2} mit ggt(n_{1}, n_{2}) = 1. Seien M(n), A(n) die Anzahl der Multiplikationen bzw. A(n) der Länge n. Dann gilt

M(n) = M(n_{1})M(n_{2})
A(n) = M(n_{1})A(n_{2}) + n_{2}A(n_{1})

(Algorithmus von Cooley und Agarwal).

3.4 Schnelle Faltung nach Winograd

Wir benutzen nun den Chinesischen Restsatz, um Faltungen schnell auszuführen. Wir wissen, daß wir Faltungen der Länge n als Multiplikation von Polynomen in F [z] modulo p = z^{n} − 1 auffassen können. Es ist ja mod p

∑_{k=0}^{n−1} x_{k}z^{k} ∑_{ℓ=0}^{n−1} y_{ℓ}z^{ℓ} = ∑_{j=0}^{n−1} (∑_{ℓ=0}^{j} x_{j−ℓ}y_{ℓ}) z^{j} + ∑_{j=n}^{2n−2} ( ∑_{ℓ=j−n+1}^{n−1} x_{j−ℓ}y_{ℓ}) z^{j}

= ∑_{j=0}^{n−1} (∑_{ℓ=0}^{j} x_{j−ℓ}y_{ℓ} + ∑_{ℓ=j+1}^{n−1} x_{j−ℓ}y_{ℓ}) z^{j} = ∑_{j=0}^{n−1}(x ∗ y)_{j}z^{j} ,

wenn wir im Index mod n rechnen.

Ist nun p = p_{1}p_{2} mit teilerfremden p_{1}, p_{2}, so haben wir nach Satz 2.3.4

F [z]/p = F [z]/p_{1} ⊕ F [z]/p_{2} .

Dieser Isomorphismus ist leicht hergestellt. Nach Satz 2.3.4 gibt es Polynome q_{1}, q_{2} mit q_{2}p_{1} + q_{1}p_{2} = 1. Also gilt für f ∈ F [z] die Beziehung q_{2}p_{1}f + q_{1}p_{2}f = f. Wir definieren nun die Abbildung φ : F [z]/p → F [z]/p_{1} ⊕ F [z]/p_{2} durch

φ(f) = (q_{1}f, q_{2}f) .

Dies ist offenbar der gesuchte Isomorphismus. Die Multiplikation zweier Polynome f, g modulo p wird nun so ausgeführt: Zunächst ist

fg = q_{2}p_{1}fg + q_{1}p_{2}fg

oder, modulo p gerechnet,

fg = q_{2}p_{1}(fg mod p_{2}) + q_{1}p_{2}(fg mod p_{1}) .  (3.4.1)

Es genügt also, die Multiplikation mod p_{1} und mod p_{2} auszuführen. Dann läßt sich fg mod p leicht berechnen.

Wir betrachten zunächst den Fall n = 2. Hier ist p_{1} = z − 1, p_{2} = z + 1, und wir haben

−\frac{1}{2}(z − 1) + \frac{1}{2}(z + 1) = 1 ,

also q_{1} = +\frac{1}{2}, q_{2} = −\frac{1}{2}. Sei f = x_{0}+x_{1}z, g = y_{0}+y_{1}z und fg = w_{0}+w_{1}z mod (z^{2} − 1), also w_{0} = x_{0}y_{0} + x_{1}y_{1}, w_{1} = x_{0}y_{1} + y_{1}x_{0}.

Wir führen die Multiplikation fg mod p_{1} und mod p_{2} durch. Es ist

\begin{aligned}fg & mod(z − 1) & = & (fg)(1) & = & f(1)g(1) & = & (x_{0} + x_{1})(y_{0} + y_{1}) , \\ fg & mod(z + 1) & = & (fg)(−1) & = & f(−1)g(−1) & = & (x_{0} − x_{1})(y_{0} − y_{1}) . \end{aligned}

Nach (3.4.1) haben wir also mod (z^{2} − 1)

fg = −\frac{1}{2}(z − 1)(x_{0} − x_{1})(y_{0} − y_{1}) + \frac{1}{2}(z + 1)(x_{0} + x_{1})(y_{0} + y_{1}) .

Dies liefert den folgenden Algorithmus zur Faltung der Länge 2:

s_{1} = y_{0} + y_{1} , s_{2} = y_{0} − y_{1}
m_{1} = \frac{x_{0} + x_{1}}{2} s_{1} , m_{2} = \frac{x_{0} − x_{1}}{2} s_{2}  (3.4.2)
w_{0} = m_{1} + m_{2} , w_{1} = m_{1} − m_{2}

Zur Feststellung des Rechenaufwandes legen wir nun fest: Es zählen nicht die Rechnungen, die man auf den Koeffizienten x_{i} ausführt. Man stellt sich dazu vor, daß die x_{i} ein für allemal gewählt sind, so daß diese Rechnungen ein für allemal durchgeführt werden können. Bei dieser Zählweise erfordert (3.4.2) nur 4 Additionen und zwei Multiplikationen, im Gegensatz zu den 4 Multiplikationen und zwei Additionen der Schulmethode für die Faltung der Länge 2.

Nun zum Fall n = 3. Hier haben wir z^{3} − 1 = (z^{2} + z + 1)(z − 1), also p_{1} = z − 1, p_{2} = z^{2} + z + 1. Die Polynome q_{1}, q_{2} werden durch Division mit Rest berechnet. Es ist

p_{2} : p_{1} = z^{2} + z + 1 : z − 1 = z + z

\frac{z^{2} − z}{2z + 1}

\frac{2z − 2}{3}

also

z^{2} + z + 1 = (z − 1)(z + 2) + 3

und daher

−\frac{z + 2}{3}(z − 1) + \frac{1}{3}(z^{2} + z + 1) = 1 .

Dieser Beziehung entnehmen wir q_{2} = −(z + 2)/3, q_{1} = 1/3. Seien wieder f = x_{0} + x_{1}z + x_{2}z^{2}, g = y_{0} + y_{1}z + y_{2}z^{2} und fg mod (z^{3} − 1) = w_{0}+w_{1}z+w_{2}z^{2}. Die Berechnung von fg mod (z−1) und mod(z^{2}+z+1) ergibt nun

fg mod (z − 1)  = (fg)(1) = f(1)g(1) = (x_{0} + x_{1} + x_{2})(y_{0} + y_{1} + y_{2})
fg mod (z^{2} + z + 1) = fmod(z^{2} + z + 1) · g mod (z^{2} + z + 1)
= (x_{0} + x_{1}z − x_{2}(1 + z))(y_{0} + y_{1}z − y_{2}(1 + z))
= (x_{0} − x_{2} + (x_{1} − x_{2})z)(y_{0} − y_{2} + (y_{1} − y_{2})z)
= (x_{0} − x_{2})(y_{0} − y_{2}) + ((x_{1} − x_{2})(y_{0} − y_{2})
+(x_{0} − x_{2})(y_{1} − y_{2}))z − (x_{1} − x_{2})(y_{1} − y_{2})(1 + z)
= (x_{0} − x_{2})(y_{0} − y_{2}) − (x_{1} − x_{2})(y_{1} − y_{2})
+((x_{1} − x_{2})(y_{0} − y_{2}) + (x_{0} − x_{2})(y_{1} − y_{2})
−(x_{1} − x_{2})(y_{1} − y_{2}))z
= m′_{1} − m′_{2} + (m′_{1} − m′_{3})z ,

\begin{aligned}m′_{1} & = & (x_{0} − x_{2})(y_{0} − y_{2}) , \\ m′_{2} & = & (x_{1} − x_{2})(y_{1} − y_{2}) , \\ m′_{3} & = & (x_{0} − x_{1})(y_{0} − y_{1}) . \end{aligned}

Wir setzen auch noch

m′_{0} = (x_{0} + x_{1} + x_{2})(y_{0} + y_{1} + y_{2}) .

Zusammensetzen dieser Resultate mittels (3.4.1) ergibt

fg mod (z^{3} − 1) = −\frac{z+2}{3}(z − 1)(fg mod (z^{2} + z + 1))
+\frac{1}{3}(z^{2} + z + 1)fg mod z − 1
= −\frac{z+2}{3}(z − 1)(m′_{1} − m′_{2} + (m′_{1} − m′_{3})z)
+\frac{1}{3}(z^{2} + z + 1)(x_{0} + x_{1} + x_{2})(y_{0} + y_{1} + y_{2})
= \frac{2}{3}(m′_{1} − m′_{2}) + (−\frac{1}{3}(m′_{1} − m′_{2}) + \frac{2}{3}(m_{1} − m′_{3}) + \frac{1}{3}m′_{0})z

+(−\frac{1}{3}(m′_{1} − m′_{2}) − \frac{1}{3}(m′_{1} − m′_{3}) + \frac{1}{3}m_{0})z^{2} − \frac{1}{3}(m′_{1} − m′_{3})z^{3} .

Dies ergibt den Algorithmus

s_{0} = y_{0} + y_{1} + y_{2} , s_{1} = y_{0} − y_{2} , s_{2} = y_{1} − y_{2} , s_{3} = y_{0} − y_{1} ,
m_{0} = \frac{x_{0} + x_{1}x_{2}}{3} s_{0} , m_{1} = \frac{x_{0} − x_{2}}{3} s_{1} , m_{2} = \frac{x_{1} − x_{2}}{3} s_{2} , m_{3} = \frac{x_{0} − x_{1}}{3} s_{3}  (3.4.3)

w_{0} = m_{0} + m_{1} − 2m_{2} + m_{3} , w_{1} = m_{0} + m_{1} + m_{2} − 2m_{3} , w_{2} = m_{0} − 2m_{1} + m_{2} + m_{3} .

Er benötigt 4 Multiplikationen und 17 Additionen (Multiplikationen mit 2 werden durch Additionen realisiert). Die Anzahl der Multiplikationen hat sich gegenüber der Schulmethode für die Faltung der Länge 3 also gewaltig reduziert (von 9 auf 4). Die Anzahl der Additionen ist noch nicht endgültig.

Zur Reduzierung der Anzahl der Additionen führen wir nun das Hilfsmittel der Transposition ein. Es seien t Bilinearformen

w_{k} = ∑_{i=1}^{s} ∑_{j=1}^{r} a_{ijk}x_{i}y_{j} , k = 1, …, t  (3.4.4)

auszuwerten. Dafür stehe ein Algorithmus der Form

w_{k} = ∑_{ℓ=1}^{m} γ_{ℓk} (\frac{1}{f_{ℓ}} ∑_{i=1}^{s} α_{ℓi}x_{i}) (∑_{j=1}^{r} β_{ℓj}y_{j})  (3.4.5)

zur Verfügung mit ganzen Zahlen γ_{ℓk}, f_{ℓ}, α_{ℓi} β_{ℓj}. Zur Zählung der Operationen in (3.4.3) machen wir folgende Konventionen:

(a) Operationen auf den x_{i} werden nicht gezählt. Man stellt sich vor, daß die x_{i} immer die gleichen sind, so daß

\frac{1}{f_{ℓ}} ∑_{i=1}^{s} α_{ℓi}x_{i} , ℓ = 1, …, m

vorberechnet werden kann.

(b) Die Multiplikationen mit γ_{ℓk}, β_{ℓj} werden durch Additionen realisiert.

So gezählt benötigt (3.4.5) m Multiplikationen.

Faltungen mit festem x und Fourier-Transformationen sind Beispiele für (3.4.4). Die oben gefundenen Algorithmen für die Faltungen der Länge 2 und 3 sind Beispiele für (3.4.5).

Unter dem zu (3.4.4) transponierten System von Bilinearformen verstehen wir das System

∑_{k=1}^{t} ∑_{j=1}^{r} a_{ijk}z_{k}y_{j} , i = 1, …, s .  (3.4.6)

Wir erhalten das transponierte System aus (3.4.4), indem wir die kte Gleichung (3.4.4) mit z_{k} multiplizieren, über k summieren, und die Koeffizienten der x_{i} betrachten.

Wir wollen zeigen, daß (3.4.5) auch einen Algorithmus zur Auswertung des transponierten Systems (3.4.6) liefert, der ebenfalls mit m Multiplikationen auskommt. Dazu multiplizieren wir (3.4.6) mit x_{i} und summieren über i. Mit (3.4.5) ergibt sich

∑_{i=1}^{s} x_{i} ∑_{k=1}^{t} ∑_{j=1}^{r} a_{ijk}z_{k}y_{j} = ∑_{k=1}^{t} z_{k} ∑_{i=1}^{s} ∑_{j=1}^{r} a_{ijk}x_{i}y_{j}

= ∑_{k=1}^{t} z_{k} ∑_{ℓ=1}^{m} γ_{ℓk} (\frac{1}{f_{ℓ}} ∑_{i=1}^{s} α_{ℓi}x_{i}) (∑_{j=1}^{r} β_{ℓj}y_{j})

= ∑_{i=1}^{s} x_{i} ∑_{ℓ=1}^{m} α_{ℓi} (\frac{1}{f_{ℓ}} ∑_{k=1}^{t} γ_{ℓk}z_{k}) (∑_{j=1}^{r} β_{ℓj}y_{j}) .

Vergleichen wir den Koeffizienten von x_{i}, so erhalten wir

∑_{k=1}^{t} ∑_{j=1}^{r} a_{ijk}z_{k}y_{j} = ∑_{ℓ=1}^{m} α_{ℓi} (\frac{1}{f_{ℓ}} ∑_{l=1}^{t} γ_{ℓk}z_{k}) (∑_{j=1}^{r} β_{ℓj}y_{j}) . (3.4.7)

Dies ist ein Algorithmus zur Auswertung des transponierten Systems (3.4.6) mit m Multiplikationen.

Wir wenden die Transposition an auf die Faltung

w_{k} = ∑_{i=0}^{n−1} x_{i−k}y_{k} , k = 0, …, n − 1 .

Das dazu transponierte System ist

w′_{i} = ∑_{k=0}^{n−1} y_{k−i}z_{k} , i = 0, …, n − 1 ,

und dies ist auch eine Faltung. (3.4.7) ist also wieder ein Algorithmus zur Faltung mit m Multiplikationen, aber einer anderen (und hoffentlich geringeren) Anzahl von Additionen.

Wir führen die Transposition durch für den Algorithmus (3.4.3) zur Faltung der Länge 3. Die Koeffizienten f_{ℓ}, γ_{ℓk}, α_{ℓi}, β_{ℓj} sind in folgendem Schema zusammengestellt:

f  γ  α  β
3 1 1 1 1 1 1 1 1 1
3 1 1 −2 1 0 −1 1 0 −1
3 −2 1 1 0 1 −1 0 1 −1
3 1 −2 1 1 −1 0 1 −1 0
w_{0} w_{1} w_{2} x_{0} x_{1} x_{2} y_{0} y_{1} y_{2}

Die Anwendung von α und β zeilenweise erfordert jeweils 5 Additionen, die Anwendung von γ spaltenweise aber 12 (Multiplikation mit 2 wird durch Addition realisiert). In dieser Form benötigt der Algorithmus also 17 Additionen. Bei der Transposition wird α mit γ vertauscht, während β unverändert bleibt.

Die Anwendung von β (zeilenweise) erfordert nach wie vor 5 Additionen, die Anwendung von α (spaltenweise) aber nur noch 6 Additionen. Der transponierte Algorithmus (3.4.7) kommt also mit 11 (statt 17) Additionen und 5 Multiplikationen aus. Er lautetet:

s_{0} = y_{0} + y_{1} + y_{2} , s_{1} = y_{0} − y_{2} , s_{2} = y_{1} − y_{2} , s_{3} = y_{0} − y_{1} ,

m_{0} = \frac{z_{0} + z_{1} + z_{2}}{3} s_{0} , m_{1} = \frac{z_{0} + z_{1} − 2z_{2}}{3} s_{1} ,

m_{2} = \frac{−2z_{0} + z_{1} + z_{2}}{3} , m_{3} = \frac{z_{0} − 2z_{1} + z_{2}}{3}  (3.4.8)

w′_{0} = m_{0} + m_{1} + m_{3} , w′_{1} = m_{0} + m_{1} − m_{3} , w′_{2} = m_{0} − m_{1} − m_{2} .

Die Winograd-Faltung versucht mit möglichst wenig Multiplikationen auszukommen. Wir wollen eine Aussage über die benötigten Multiplikationen für Faltungen beliebiger Länge herleiten. Sie gilt für einen beliebigen Körper F der Charakteristik 0, also z.B. F = IR, C. Die Kreisteilungspolynome ϕ_{d} (siehe z.B. Fischer/Sacher: Einführung in die Algebra, S. 172 ff.) in einem solchen Körper sind Polynome mit der Eigenschaft

x^{n} − 1 = ∏_{d/n} ϕ_{d}(x) .

Ihre Anzahl k entspricht also der Anzahl der Teiler von n (einschließlich 1, n). Eine kleine Liste von Kreisteilungspolynomen ist

\begin{aligned}ϕ_{1} & = & x − 1 \\ ϕ_{2} & = & x + 1 \\ ϕ_{3} & = & x^{2} + x + 1 \\ ϕ_{4} & = & x^{2} + 1 \\ ϕ_{5} & = & x^{4} + x^{3} + x^{2} + x + 1 \end{aligned}

Sie haben folgende Eigenschaften:

(i) ϕ_{d} hat nur ganzzahlige Koeffizienten

(ii) ϕ_{d} ist irreduzibel

(iii) ϕ_{d}, ϕ′_{d} sind für d ≠ d′ teilerfremd.

Satz 3.4.1 Sei F ein Körper der Charakteristik 0 und k die Anzahl der Teiler von n, welche ≤ n sind (1 und n eingeschlossen). Dann kann man die Faltung der Länge n in F mit 2n − k Multiplikationen ausführen (Vorberechnungen auf einem der Faktoren werden nicht gezählt).

Beweis: Seien p_{1}, …, p_{k} die Kreisteilungspolynome zu n, also

x^{n} − 1 = p_{1}p_{2} ⋯ p_{n} .

Sei P_{2} = p_{2} ⋯ p_{k}. Wir wenden den Chinesischen Restsatz an und bestimmen q_{1}, q_{2} ∈ F [z], so daß

1 = q_{2}p_{1} + q_{1}P_{2} .

Dann ist wie oben für f, g ∈ F [z]

fg mod (z^{n} − 1) = q_{2}p_{1}((fg) mod P_{2}) + q_{2}P_{2}((fg) mod p_{1})

= q_{2}p_{1}(f mod P_{2})(g mod P_{2}) + q_{1}P_{2}(f mod p_{1})(g mod p_{1}) .

Da p_{1}, P_{2} nur ganzzahlige Koeffizienten haben, können f und g mod P_{2} bzw. mod p_{1} durch Additionen berechnet werden. Die Multiplikation zweier Polynome q, f vom Grade k, ℓ kann mit k+ℓ+1 Multiplikationen ausgeführt werden. man braucht ja nur k +ℓ+1 paarweise verschiedene Punkte z_{0}, …, z_{k+1} aus dem Primkörper von F zu wählen und für fg die Lagrange’sche Interpolationsformel hinzuschreiben, also

(fg)(z) = ∑_{j=0}^{ℓ+k} ω_{j}(z)f(z_{j})g(z_{j}) , ω_{j}(z) = ∏_{{i=0 \atop j≠j}}^{k+ℓ} \frac{z − z_{j}}{z_{i} − z_{j}} .

Da die ω_{j} Koeffizienten aus dem Primkörper von F haben, können die Koeffizienten von fg durch Addition berechnet werden, sobald die k + ℓ + 1 Produkte f(z_{j})g(z_{j}) bekannt sind. Also kann fg tatsächlich mit k + ℓ + 1 Multiplikationen berechnet werden.

Sei nun M(p) die Anzahl der Multiplikationen für die Berechnung von fg mod p, wobei p irgendein Polynom über dem Primkörper von F ist. Nach dem Chinesischen Restsatz gilt dann

\begin{aligned}M(x^{n} − 1) & = & M(p_{1}) + M(P_{2}) \\ & = & M(p_{1}) + M(p_{2}) + ⋯ + M(p_{k}) . \end{aligned}

Wir haben gerade gesehen, daß M(p) = 2 Grad (p) − 1. Also folgt

M(x^{n} − 1) = ∑_{i=1}^{k}(2 Grad(p_{i}) − 1) = 2n − k .

□

3.5 Die schnelle Fourier–Transformation nach Winograd

Winograd führt die Fourier-Transformation auf Faltungen zurück. Dazu definieren wir zunächst die Faltung auf einer beliebigen Gruppe G. Sei |G| = n, und seien x, y ∈ C^{n}. Wir interpretieren x, y als Funktionen auf G, schreiben also x = (x_{s})_{s∈G}, y = (y_{s})_{s∈G}. Die Faltung z = x ∗ y ist dann eine ebensolche Funktion auf G, und zwar ist

z_{g} = ∑_{{s,t∈G \atop ts=g}} x_{s}y_{t} = ∑_{t∈G} x_{t^{−1}g}y_{t} ,

= ∑_{t∈G} x_{tg}y_{t^{−1}} .

In Matrix-Form schreibt sich dies

z = XP y , X = (x_{tg})_{g,t∈G}

mit einer Permutationsmatrix P. Anders ausgedrückt: Eine Faltung auf G wird durch eine Matrix beschrieben, in der die n Komponenten des Vektors x entsprechend der Gruppentafel von G angeordnet sind.

Nun zur Fourier-Transformation W_{n} der Länge n, also

W_{n} = (ω^{kℓ})_{k,ℓ=0,...,n} , ω = e^{−2πi/n} .

Wegen ω_{n}^{n} = 1 kann man die Produkte im Exponenten mod n berechnen. Streicht man aus W_{n} die Zeilen und Spalten k mit k = 0 oder k|n, so bleibt übrig eine (φ(n), φ(n))-Matrix W̃_{n} (φ ist die Euler’sche φ-Funktion, vgl. 2.4), in welcher die φ(n) Elemente ω^{k}, 0 ≤ k < n − 1, k ≠ 0 und ggt(n, k) = 1 entsprechend der Gruppentafel von M_{n} angeordnet sind.

Wir haben eben gesehen, daß eine solche Matrix nichts anderes als eine Faltung auf M_{n} darstellt. Ein großer Teil der zur Anwendung von W_{n} notwendigen Rechenoperationen kann also als Faltung auf M_{n} ausgeführt werden.

3.5. DIE SCHNELLE FOURIER–TRANSFORMATION NACH WINOGRAD65

Aus Satz 2.4.3 wissen wir, daß M_{n} für n = p^{r}, p > 2, r > 1 zyklisch ist. Dann ist also W̃_{n} sogar eine Faltung auf C_{n}, und diese können nach den Methoden aus §4 schnell ausgeführt werden. Diese Art der schnellen Fourier-Transformation wird auch Rader FFT genannt. Wir führen dies nun für einige Beispiele durch.

Beginnen wir mit n = 3. Nach Satz 2.4.3 ist M_{3} ≅ C_{2}. In der Tat sind in

W_{3} = ( \begin{matrix}1 & 1 & 1 \\ 1 & ω & ω^{2} \\ 1 & ω^{2} & ω \end{matrix} ) , ω = e^{−2πi/3}

die beiden letzten Zeilen und Spalten eine Faltung der Länge 2. Diese können wir mit 2 Multiplikationen und 4 Additionen ausführen, dazu kommen dann nach 4 Additionen in Zeile und Spalte 0. Von den acht Additionen kann man noch zwei einsparen, wenn man

( \begin{matrix}ŷ_{1} − ŷ_{0} \\ ŷ_{2} − ŷ_{0} \end{matrix} ) = ( \begin{matrix}ω − 1 & ω^{2} − 1 \\ ω^{2} − 1 & ω − 1 \end{matrix} ) ( \begin{matrix}y_{1} \\ y_{2} \end{matrix} )

schreibt. Ausführung dieser Faltung mit schnellem Algorithmus ergibt

ŷ_{1} − ŷ_{0} = \frac{ω + ω^{2} − 2}{2}(y_{1} + y_{2}) + \frac{ω − ω^{2}}{2} (y_{2} − y_{2})
ŷ_{2} − ŷ_{0} = \frac{ω + ω^{2}2}{2}(y_{1} + y_{2}) − \frac{ω − ω^{2}}{2} (y_{1} − y_{2})

Damit kommen wir zu folgendem Algorithmus mit 2 Multiplikationen und 6 Additionen:

s_{1} = y_{1} + y_{2} , s_{2} = y_{1} − y_{2}

m_{1} = \frac{ω + ω^{2} − 2}{2}s_{1} , m_{2} = \frac{ω − ω^{2}}{2} s_{2}

(3.5.1)

ŷ_{0} = y_{0} + s_{1} , s_{3} = ŷ_{0} + m_{1}

ŷ_{1} = s_{3} − m_{2} , ŷ_{2} = s_{3} + m_{2} .

Wir bemerken, daß

\begin{aligned}\frac{ω+ω^{2}−2}{2} & = & \frac{ω+\overline{ω}−2}{2} & = & cos(2π/3) − 1 \\ \frac{ω−ω^{2}}{2} & = & \frac{ω−\overline{ω}}{2} & = & i sin(2π/3) \end{aligned}

reell bzw. rein imaginär sind, so daß sich die beiden Multiplikationen von (3.5.1) in insgesamt 4 reellen Multiplikationen ausführen lassen.

Im Falle n = 4 haben wir nach Satz 2.4.3 M_{4} = {1, 3} = C_{2}. Die entsprechende Umordnung von W_{4} ist

0 2 1 3
0 1 1 1 1
2 1 1 −1 −1
1 1 −1 i −i
3 1 −1 −i i

Ein schneller Algorithmus ist

s_{2} = y_{0} + y_{2} s_{1} = y_{1} + y_{3} , s_{2} = y_{0} − y_{2} , s_{3} = y_{1} − y_{3}

(3.5.2)

ŷ_{0} = s_{0} + s_{1} ŷ_{1} = s_{2} + is_{3} , ŷ_{2} = s_{0} − s_{1} , ŷ_{3} = s_{2} − is_{3} .

Dieser Algorithmus kommt also ganz ohne Multiplikation aus. Die Anzahl der Additionen ist 8.

Als nächstes nehmen wir n = 7. Dann ist M_{7} = C_{6} = {1, a, …, a^{5}} mit dem erzeugenden Element a = 3, vgl. Abschnitt 2.4. Also ist M_{7} = {1, 3, 2, 6, 4, 5}. Wir ordnen W_{7} so an, daß die Zeilen und Spalten 1, 2, 3, 4, 5, 6 in der Reihenfolge 1, 3, 2, 6, 4, 5 erscheinen. Notieren wir nur die Exponenten, so bedeutet dies

0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 \overrightarrow{Zeilen} 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 1 2 3 3 4 5 6 3 0 3 6 2 5 1 4 2 0 2 4 6 1 3 5 6 0 6 5 4 3 2 1 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 \overrightarrow{Spalten} 0 1 3 2 6 4 5 0 0 0 0 0 0 0 0 1 0 1 3 2 6 4 5 3 0 3 2 6 4 5 1 2 0 2 6 4 5 1 3 6 0 6 4 5 1 3 2 4 0 4 5 1 3 2 6 5 0 5 1 3 2 6 4

Es entsteht die Gruppentafel von C_{6}, wie es auf Grund der Isomorphie M_{7} ≅ C_{6} zu erwarten ist.

Dies wird in folgender Weise in einen Algorithmus umgesetzt. Die Faltung der Länge 6 realisieren wir durch eine Faltung der Länge 2 auf Blöcken, die ihrerseits Faltungen der Länge 3 sind. Die Faltungen der Länge 3 führen wir durch Algorithmus (3.4.8) aus (M(3) = 4, A(3) = 11), für die Faltungen der Länge 2 ist M(2) = 2, A(2) = 4. Nach 3.4 ist dann M(6) = M(2)M(3) = 8, A(6) = M(2)A(3) + 3A(2) = 34. Die Faltung der Länge 6 läßt sich also mit 8 Multiplikationen und 34 Additionen ausführen. Bei den Faltungen der Länge 3 fallen auch die Summen y_{1} + y_{2} + y_{3} und y_{4} + y_{5} + y_{6} an. Die Addition ŷ_{6} = (y_{1} + y_{2} + y_{3}) + (y_{4} + y_{5} + y_{6}) fällt bei der Blockfaltung an. Jetzt sind nur noch die 6 Additionen mit ŷ_{0} auszuführen. Nun ist aber jeder der beiden Faltungsalgorithmen für die Faltung der Länge 3 von der Form w′_{k} = m_{0} + ⋯, k = 0, 1, 2 (vgl. 3.4.8). Also braucht man für jede dieser Faltungen nur m_{0} + y_{0} zu bilden, kommt also mit 2 Additionen aus. Insgesamt reichen also 36 Additionen und 8 Multiplikationen.

Nehmen wir als weiteres Beispiel n = 9 = 3^{2}. Dann ist nach Satz 2.4.3 M_{9} = {1, 2, 4, 5, 7, 8} ≅ C_{6} = {1, a, …, a^{5}} mit a = 5 (wir könnten ebensogut a = 2 nehmen, nicht aber a = 4). Ordnen wir demgemäß M_{9} = {1, 5, 7, 8, 4, 2} an und schreiben wir in W_{9} erst die (nicht zu M_{9} gehörigen) Indizes 0, 3, 6 an, so nimmt W_{9} die Form

0 3 6 1 5 7 8 4 2
0 0 0 0 0 0 0 0 0 0
3 0 0 0 3 6 3 6 3 6
6 0 0 0 6 3 6 3 6 3
1 0 3 6 1 5 7 8 4 2
5 0 6 3 5 7 8 4 2 1
7 0 3 6 7 8 4 2 1 5
8 0 6 3 8 4 2 1 5 7
4 0 3 6 4 2 1 5 7 8
3 0 6 3 2 1 5 7 8 4

Man erkennt die Faltung der Länge 6 in den letzten 6 Zeilen und Spalten.

68 KAPITEL 3. SCHNELLE FOURIER-TRANSFORMATION Für die Winograd-FFT kann man folgende Tabelle verifizieren:

n Multiplikationen Additionen

Herleitung

2  0  2  −−
3  2  6  M_{3} ≅ C_{2}
4  0  8  M_{4} ≅ C_{2}
5  5  17  M_{5} ≅ C_{4}
7  8  36  M_{7} ≅ C_{2} ⊗ C_{3}
8  2  26  M_{8} ≅ C_{2} ⊗ C_{2}
9  10  45  M_{9} ≅ C_{6}
16  10  74  M_{1}6 ≅ C_{2} ⊗ C_{4}

Aus dieser Tabelle kann man nun mittels Primfaktorzerlegung und Tensorprodukten nach §3 Algorithmen für andere Längen n herleiten.

3.6 Schnelle Poisson-Löser

Als Anwendung der schnellen Fourier-Transformation wollen wir nun einen schnellen Algorithmus zur Lösung der Randwertaufgabe

Δu = f in Ω ,  u = 0 auf ∂Ω  (3.6.1)

für ein Rechteck Ω herleiten. Durch Diskretisierung auf einem Gitter der Schrittweise h wird (3.6.1) angenähert durch

−4u_{k,ℓ} + u_{k+1,ℓ} + u_{k−1,ℓ} + u_{k,ℓ−1} + u_{k,ℓ+1} = h^{2}f_{k,ℓ} , 0 < k < m, 0 < ℓ < n

(3.6.2)

u_{kℓ} = 0 , k = 0 oder m oder ℓ = 0 oder n .

Dabei ist u_{k,ℓ} eine Näherung für u in dem durch k, ℓ bezeichneten Gitterpunkt, und f_{k,ℓ} ist der dortige Funktionswert von f. Unser Ziel ist es, (3.6.2) in O(mn log(mn)) Rechenoperationen zu lösen.

Wir beginnen mit dem eindimensionalen Fall, also

u′′ = f in 0 < x < a ,  u(0) = u(a) = 0 .  (3.6.3)

Durch Diskretisierung geht dies über in

u_{k+1} − 2u_{k} + u_{k−1} = h^{2}f_{k} , 0 < k < m

(3.6.4)

u_{0} = u_{m} = 0 .

Führen wir die Vektoren und Matrizen

U = ( u_{1} ; ⋮ ; u_{m−1} ) , F = h^{2} ( f_{1} ; ⋮ ; f_{m−1} ) T_{m−1} = ( \begin{matrix}−2 & 1 & & & & & O \\ 1 & −2 & 1 \\ & 1 & −2 & & 1 \\ & & & . & . & . \\ O & & & & 1 & & −2 \end{matrix} )

ein, so schreibt sich (3.6.4) als

T_{m−1}U = F .  (3.6.5)

Da T_{m−1} tridiagonal ist, kann man dies durch Elimination in O(m) Rechenoperationen lösen. Wir gehen komplizierter vor und berechnen zunächst die Eigenwerte und Eigenvektoren von T_{m}. Dazu setzen wir

c_{k} = cos(θ) , s_{k} = sin(kθ)

und bekommen dann aus den Additionstheoremen

\begin{aligned}s_{k−1} & = & c_{1}s_{k} − s_{1}c_{k} & , & s_{k+1} & = & c_{1}s_{k} + s_{1}c_{k} , \\ c_{k−1} & = & c_{1}c_{k} + s_{1}s_{k} & , & c_{k+1} & = & c_{1}s_{k} − s_{1}s_{k} . \end{aligned}

Daraus folgt weiter

s_{k−1} − 2c_{1}s_{k} + s_{k+1} = 0 , c_{k−1} − 2c_{1}c_{k} + c_{k+1} = 0 .

Die erste Beziehung schreiben wir in der Form

s_{k−1} − 2s_{k} + s_{k+1} = −2(1 − c_{1})s_{k} = −4 sin^{2}(\frac{θ}{2})s_{k} ,

wobei wir 1 − cos θ = 2 sin^{2}(θ/2) benutzt haben. Setzen wir hier θ = θ_{j} = πj/m und bezeichnen wir mit s^{j} den zugehörigen Vektor (s_{1}, …, s_{m−1}), so ist s_{m} = 0 und damit s^{j} Eigenvektor zu T_{m−1} zum Eigenwert λ_{j} = −4 sin^{2}(πj/2m). Mit den Matrizen

S_{m−1} = (s^{1}, …, s^{m−1}) , Λ_{m−1} = ( \begin{matrix}λ_{1} \\ & . & . & . \\ & & & & λ_{m−1} \end{matrix} )

hat man als

S_{m−1}^{−1}T_{m−1}S_{m−1} = Λ_{m−1} .  (3.6.6)

Nun behandeln wir den zweidimensionalen Fall (3.6.2). Wir ordnen die u_{kℓ} zeilenweise an, definieren also einen (n − 1)(m − 1)-Vektor U mit den Komponenten (m = 4, n = 5)

u_{11}, u_{12}, u_{13}, u_{14}, u_{21}, u_{22}, u_{23}, u_{24}, u_{31}, u_{32}, u_{33}, u_{34} .

Schreiben wir die Gleichungen (3.6.2) ebenfalls zeilenweise hin, so entsteht

( \begin{matrix}−2 & 1 \\ 1 & −2 & 1 \\ & 1 & −2 & 1 \\ & & 1 & −2 \\ & & & & −2 & 1 \\ & & & & 1 & −2 & 1 \\ & & & & & 1 & −2 & 1 \\ & & & & & & 1 & −2 \\ & & & & & & & & −2 & 1 \\ & & & & & & & & 1 & −2 & 1 \\ & & & & & & & & & 1 & −2 & 1 \\ & & & & & & & & & & 1 & −2 \end{matrix} +

+ \begin{matrix}−2 & & & & 1 \\ & −2 & & & & 1 \\ & & −2 & & & & 1 \\ & & & −2 & & & & 1 \\ 1 & & & & −2 & & & & 1 \\ & 1 & & & & −2 & & & & 1 \\ & & 1 & & & & −2 & & & & 1 \\ & & & 1 & & & & −2 & & & & 1 \\ & & & & 1 & & & & −2 \\ & & & & & 1 & & & & −2 \\ & & & & & & 1 & & & & −2 \\ & & & & & & & 1 & & & & −2 \end{matrix} ) ( U_{1} ; U_{2} ; U_{3} ; \underline{U_{4}} ; U_{5} ; U_{6} ; U_{7} ; \underline{U_{8}} ; U_{9} ; U_{10} ; U_{11} ; U_{12} ) = ( F_{1} ; F_{2} ; F_{3} ; \underline{F_{4}} ; F_{5} ; F_{6} ; F_{7} ; \underline{U_{8}} ; F_{9} ; F_{10} ; F_{11} ; F_{12} ) .

Dies kann man in der Form

(I_{3} ⊗ T_{4} + T_{3} ⊗ I_{4})U = F

schreiben. Im allgemeinen erhält man

(I_{m−1} ⊗ T_{n−1} + T_{m−1} ⊗ I_{n−1})U = F .  (3.6.7)

Satz 3.6.1 Seien A_{n}, B_{m} (n, n)- bzw. (m, m)-Matrizen, und sei M = I_{m} ⊗ A_{n} + B_{m} ⊗ I_{n} invertierbar. Sei U_{n}^{−1}A_{n}U_{n} = Λ_{n} und V_{m}^{−1}B_{m}V_{m} = M_{m}. Dann gilt

M^{−1} = (V_{m} ⊗ U_{n})(I_{m} ⊗ Λ_{n} + M_{m} ⊗ I_{n})^{−1}(V_{m}^{−1} ⊗ U_{n}^{−1}) .

Beweis: Dies folgt sofort aus den Rechenregeln

(A ⊗ B)(C ⊗ D) = AC ⊗ BD , (A ⊗ B)^{−1} = A^{−1} ⊗ B^{−1} .
□

Sind Λ_{n}, M_{m} diagonal, so auch I_{n} ⊗ Λ_{n} + M_{n} ⊗ I_{n} und damit leicht zu invertieren. In der Anwendung auf (3.6.7) sind U_{n}, V_{m} die Sinus-Transformation, die n log n bzw. m log m Operationen erfordern. V_{m} ⊗ U_{n} verlangt also m Sinus-Transformationen der Länge n und n Sinus-Transformationen der Länge m, also

mn log n + nm log m = mn log(mn)

Operationen. Das gleiche gilt für V_{m}^{−1} ⊗ U_{n}^{−1}, und die Anwendung von (I_{m} ⊗ Λ_{n} + M_{m} ⊗ I_{n})^{−1} verlangt mn Operationen. Also kann (3.6.2) in O(mn log(mn) Operationen gelöst werden.

Symmetrie

4.1 Matrizen mit Symmetrien

Wir haben schon in der Einleitung gesehen, daß effiziente Algorithmen für Matrizen möglich sind, die gewisse Vertauschbarkeitsrelationen erfüllen. Dies wollen wir nun systematisch verfolgen.

Definition 4.1.1 Sei A eine (m, n)-Matrix, und seien P, Q Darstellungen einer Gruppe G in C^{m} bzw. C^{n}. Wir sagen, A besitze die Symmetrien von P, Q, falls

AP (s) = Q(s)A ,  ∀ s ∈ G .  (4.1.1)

Ist P = Q, so sagen wir, A besitze die Symmetrien von P.

Ein maximales System irreduzibler paarweise inäquivalenter Darstellungen nennen wir in Zukunft kurz MIP.

Sei U_{1}, …, U_{r} ein MIP von G, und zwar sei U_{j} : C^{n_{j}} → C^{n_{j}}, also vom Grade n_{j}. Die Vielfachheit von U_{j} in P, Q sei c_{j} bzw. d_{j}. Dann gibt es (m, m) bzw. (n, n)-Matrizen X, Y, so daß

P (s) = X ( \begin{matrix}I_{c_{1}} ⊗ U_{1}(s) \\ & . & . & . \\ & & & & I_{c_{r}} ⊗ U_{r}(s) \end{matrix} ) X^{−1} ,

(4.1.2)

Q(s) = Y ( \begin{matrix}I_{d_{1}} ⊗ U_{1}(s) \\ & . & . & . \\ & & & & I_{d_{r}} ⊗ U_{r}(s) \end{matrix} ) Y^{−1}

für alle s ∈ G.

Beispiele:

1) Faltungen. Sei X die (n, n)-Matrix aus 3.3.1, und sei P = (e_{1}, …, e_{n−1}, e_{0}) mit dem i-ten Einheitsvektor e_{i} in IR^{n} (Komponenten von 0 bis n − 1 numeriert). Dann ist P X = XP und damit P^{k}X = XP^{k}. Sei nun C_{n} = {1, a, …, a^{n−1}}. Die Abbildung

P (a^{k}) = P^{k} , k = 0, …, n − 1

ist eine Darstellung von C_{n} in C^{n}. X besitzt also die Symmetrien von P.

2) Fourier-Transformation. Mit der Matrix P aus i) und

Q = ( \begin{matrix}1 \\ & ω \\ & & . & . & . \\ & & & & & ω^{n−1} \end{matrix} ) , ω = e^{−2πi/n}

gilt für die Fourier-Transformation W_{n} der Länge n (vgl. III.3.1) die Beziehung W_{n}P = QW_{n} und damit W_{n}P^{k} = Q^{k}W_{n}. W_{n} hat also die Symmetrien der gleichen Darstellung P von C_{n} wie in i) und der Darstellung

Q(a^{k}) = Q^{k} , k = 0, 1, …, n − 1 .

3) Für die Block-Matrizen

A = ( \begin{matrix}A_{1} & A_{2} \\ A_{2} & A_{1} \end{matrix} ) , P = ( \begin{matrix}0 & I \\ I & 0 \end{matrix} )

gilt AP = P A. Definieren wir also eine Darstellung P von C_{2} = {1, a} durch P (a^{k}) = P^{k}, k = 0, 1, so hat A die Symmetrie dieser Darstellung.

4) Sei die (m, n)-Matrix A die Matrix eines linearen Systems mit n Eingängen und m Ausgängen. Dieses ordnet dem Input x_{1}, …, x_{n} den Output y_{1}, …, y_{n} zu gemäß y = Ax.

Wir wollen nun annehmen, das lineare System besitze Symmetrien, d.h. Input P x entspreche der Output Qy mit gewissen Permutationsmatrizen P, Q. Dann gilt für alle x

QAx = AP x

und damit AP = QA. Als Beispiele haben wir

(a) Eine spiegelsymmetrische Brücke:

Die x_{i} bedeuten etwa Belastungen, die y_{j} Auslenkungen. Seien die (n, n) bzw. (m, m)-Matrizen P, Q erklärt durch

P = ( \begin{matrix}& & & & & 1 \\ 0 & & & & 1 \\ & . & . & . \\ 1 & & & & & 0 \end{matrix} ) , Q = ( \begin{matrix}& & & & & 1 \\ 0 & & & & 1 \\ & . & . & . \\ 1 & & & & & 0 \end{matrix} ) .

Diese Matrizen beschreiben die Symmetrie des Systems. Die Symmetrie-Gruppe ist C_{2} = {1, a}, a^{2} = 1.

(b) Die quadratische Platte

hat als Symmetriegruppe D_{4}. Die Belastungen in den 9 Knoten seien x_{1}, …, x_{9}, und die zugehörigen Dehnungen y_{1}, …, y_{9}. Wieder ist y = Ax. Für q ∈ D_{4} sei π(g) die Permutation von 1, …, 9, die von der Anwendung von g auf die Platte bewirkt wird. Dann ist

P (g) ( x_{1} ; ⋮ ; x_{9} ) = ( x_{π(g)1} ; ⋮ ; x_{π(g)9} ) , g ∈ D_{4}

eine Darstellung von D_{4} in C^{9} definiert, und A hat die Symmetrie von P.

Satz 4.1.2 A besitze die Symmetrien von P, Q. Dann gibt es (d_{j}, c_{j})- Matrizen A_{j} mit

A = Y ( \begin{matrix}A_{1} ⊗ I_{n_{1}} \\ & . & . & . \\ & & & & A_{r} ⊗ I_{n_{r}} \end{matrix} ) X^{−1} .  (4.1.3)

Beweis: Mit B = Y^{−1}AX lautet (1.1)

B ( \begin{matrix}I_{c_{1}} ⊗ U_{1}(s) \\ & . & . & . \\ & & & & I_{c_{r}} ⊗ U_{r}(s) \end{matrix} ) = ( \begin{matrix}I_{d_{1}} ⊗ U_{1}(s) \\ & . & . & . \\ & & & & I_{d_{r}} ⊗ U_{r}(s) \end{matrix} ) B .

Schreiben wir B = (B_{jk}) mit (d_{j}n_{j}, c_{k}n_{k})-Matrizen B_{jk}, so geht dies über in

B_{jk}(I_{c_{k}} ⊗ U_{k}(s)) = (I_{d_{j}} ⊗ U_{j}(s))B_{jk} .

Schreiben wir weiter B_{jk} = (B_{jk,iℓ}) mit (n_{j}, n_{k})-Matrizen B_{jk,iℓ}, so entsteht

B_{jk,iℓ}U_{k}(s) = U_{j}(s)B_{ik,iℓ} .

Für k ≠ j sind U_{k}, U_{j} nicht äquivalent und irreduzibel. Nach Satz 2.1.8 folgt also B_{jk,iℓ} = 0 für k ≠ j. Für k = j folgt nach dem gleichen Satz B_{jj,iℓ} = λ_{jiℓ} mit gewissen Zahlen λ_{jiℓ}. Insgesamt ist also B_{jk} = 0 für j ≠ k und B_{jj} = A_{j} ⊗ I_{nj} mit (A_{j})_{iℓ} = λ_{jiℓ}.

□

Bemerkung: Für das praktische Rechnen ist es bequemer, Y^{−1}AX in der Form

( \begin{matrix}I_{n_{1}} ⊗ A_{1} & & & & O \\ & . & . & . \\ O & & & & I_{n_{r}} ⊗ A_{r} \end{matrix} )

zu haben. Dies kann durch eine Permutation von Zeilen und Spalten erreicht werden. Ignoriert man einmal die Matrizen X, Y, so bietet diese Form von A folgende Vorteile:

Statt der Anwendung der (m, n)-Matrix A hat man nur n_{j} mal die (d_{j}, c_{j})-Matrix A_{j} anzuwenden, j = 1, …, r.

Ist P = Q (also n = m und c_{j} = d_{j}), so hat man statt des Gleichungssystems Ax = b der Dimension n nur n_{j} mal ein Gleichungssystem A_{j}x_{j} = b_{j} der Dimension c_{j} (also immer mit gleicher Matrix A_{j}) zu lösen, j = 1, …, r. Ebenso reduziert sich das (n, n)-Eigenwertproblem auf n_{j} Eigenwertprobleme der Dimension c_{j}, j = 1, …, r, für die Matrizen A_{j} (mit Konsequenzen für die Vielfachheiten der Eigenwerte von A).

Wir wollen uns nun Gedanken darüber machen, was (4.1.2) bedeutet und wie man diese Faktorisierung von P, Q herstellt. Sei zunächst X = (X_{1}, …, X_{r}) eine entsprechende Zerlegung von X, d.h. X_{j} hat c_{j}n_{j} Spalten, und sei V_{j} der von diesen Spalten aufgespannte Teilraum der Dimension c_{j}n_{j}. Dann ist

P X_{j} = X_{j}(I_{c_{j}} ⊗ U_{j}) , j = 1, …, r .

Ist also x ∈ V_{j}, d.h. x = X_{j}v mit v ∈ C^{c_{j}n_{j}}, so ist

P v = P X_{j}v = X_{j}(I_{c_{j}} ⊗ U_{j})v ∈ V_{j} .

V_{j} ist also invarianter Unterraum von P, und in der Basis X_{j} von V_{j} ist P gegeben durch I_{c_{j}} ⊗ U_{j}. V_{j} zerfällt also noch weiter in invariante Unterräume V_{j,1,...,}V_{j,c_{j}} der Dimension n_{j}, und es ist X_{j} = (X_{j,1,...,}X_{j,c_{j}}) mit Matrizen X_{j,ν} von n_{j} Spalten, welche eine Basis von V_{j,ν} bilden. Es ist

P X_{j,ν} = X_{j,ν}U_{j} .  (4.1.4)

Wie oben sieht man, daß V_{j,ν} invariante Unterräume von P sind, und daß P in der Basis X_{j,ν} in V_{j,ν} durch U_{j} gegeben ist.

Das Auffinden von X für gegebenes P wird durch folgenden Satz ermöglicht.

Satz 4.1.3 Sei für 1 ≤ k, ℓ ≤ n_{j} mit dem k, ℓ-Element U_{j}^{kℓ} von U_{j}

T_{j}^{kℓ} = \frac{n_{j}}{|G|} ∑_{g∈G} u_{j}^{kℓ}(g^{−1})P (g) .

Dann ist für ν = 1, …, c_{j}

T_{j}^{kℓ}X_{jν} = \{ \begin{matrix}X_{jν}I_{n_{j}}^{ℓk} & , & i = j & , \\ 0 & , & sonst & , \end{matrix}

wo I_{n_{j}}^{ℓk} an der Stelle (ℓ, k) eine 1 und sonst nur Nullen hat.

Beweis: Wir erinnern an die Orthogonalitätseigenschaften von Darstellungen (Satz 2.1.10). Danach gilt

\frac{n_{j}}{|G|} ∑_{g∈G} U_{j}^{kℓ}(g^{−1})U_{i}^{mn}(g) = \{ \begin{matrix}1 & , & i = j, k = n und ℓ = m , \\ 0 & , & sonst . \end{matrix}

Es folgt

\frac{n_{j}}{|G|} ∑_{g∈G} U_{j}^{kℓ}(g^{−1})U_{i}(g) = \{ \begin{matrix}I_{n_{j}}^{ℓk} & , & i = j , \\ 0 & , & sonst . \end{matrix}  (4.1.5)

(4.1.2) bedeutet

T_{j}^{kℓ}X = X \frac{n_{j}}{|G|} ∑_{g∈G} U_{j}^{kℓ}(g^{−1}) ( \begin{matrix}I_{c_{1}} ⊗ U_{1}(g) \\ & . & . & . \\ & & & & I_{c_{r}} ⊗ U_{r}(g) \end{matrix} ) .

Mit X = (X_{1}, …, X_{r}) und X_{j} = (X_{j,1}, …, X_{j,c_{j}}) folgt der Satz direkt aus (4.1.5).

□

Ist also X_{jνi} die i-te Spalte von X_{jν}, so gilt

T_{j}^{kℓ}X_{jνi} = \{ \begin{matrix}X_{jνℓ} & , & i = k , \\ 0 & , & sonst . \end{matrix}  (4.1.6)

Insbesondere haben wir

T_{j}^{kℓ}X_{jνk} = X_{jνℓ}  (4.1.7)

Als unmittelbare Folgerung aus dem Satz notieren wir: Ist χ_{j} der Charakter von U_{j} und

T_{j} = \frac{n_{j}}{|G|} ∑_{g∈G} χ_{j}(g^{−1})P (g) ,

so ist

T_{j}X_{k} = \{ \begin{matrix}X_{j} & , & j = k , \\ 0 & , & sonst . \end{matrix}

80 KAPITEL 4. SYMMETRIE

Insbesondere ist also T_{j} eine Projektion auf V_{j}. Nun können wir einen Algorithmus zur Berechnung einer Matrix X aufstellen, die (4.1.2) erfüllt. Für j = 1, …, r:

Finde Basis für ℓ = 1, …, n_{j}

X′_{jνℓ} = T_{j}^{1ℓ}X′_{jν1} , ν = 1, …, c_{j} .

Setze X′_{jν} = (X′_{jν1,...,}V′_{jνn_{j}}), X′_{j} = (X′_{j1}, …, X′_{jc_{j}}), X′ = (X_{1}, …, X_{r}).

Satz 4.1.4 Für die Matrix X′ gilt (4.1.2).

Beweis: Wir haben nur (4.1.4) für X′ nachzuweisen. Wegen (4.1.6) ist X′_{jν1} eine Linearkombination der X_{jμ1}, etwa

X′_{jν1} = ∑_{μ=1}^{c_{j}} α_{jνμ}X_{jμ1} .

Nach (4.1.7) folgt

X′_{jνℓ} = ∑_{μ=1}^{c_{j}} α_{jνμ}X_{jμℓ} .

Für die Matrizen X′_{jν} bedeutet dies

X′_{jν} = ∑_{μ=1}^{c_{j}} α_{jνμ}X_{jμ} .

Nun folgt nach (4.1.4)

P X′_{jν} = ∑_{μ=1}^{c_{j}} α_{jνμ}P X_{jμ}
= ∑_{μ=1}^{c_{j}} α_{jνμ}X_{jμ}U_{j}
= X′_{jν}U_{j}

und dies ist (4.1.4) für X′.

□

Beispiele:

1) Wir greifen das obige Beispiel 4a) auf. Dort ist G = C^{2} = {1, s}, P (s^{k}) = P^{k}, k = 0, 1, mit

P = ( \begin{matrix}& & & & & 1 \\ 0 & & & & 1 \\ & . & . & . \\ 1 & & & & & 0 \end{matrix} ) .

Ein MIP ist gegeben durch U_{1}(s^{k}) = 1, U_{2}(s^{k}) = (−1)^{k}, k = 0, 1. Also ist P = c_{1}u_{1} + c_{2}U_{2}. Seien χ, ρ_{1}, ρ_{2} die Charaktere von P, U_{1}, U_{2}, also

\begin{aligned}& 1 & s \\ χ & n & par(n) \\ ρ_{1} & 1 & 1 \\ ρ_{2} & 1 & −1 \end{aligned} par(n) = \{ \begin{matrix}0 & , & n gerade \\ 1 & , & n ungerade . \end{matrix}

Nach Satz 2.2.4 gilt c_{j} = ⟨χ, χ_{j}⟩, also

\begin{aligned}c_{1} & = & \frac{1}{2}(χ(1)ρ_{1}(1) + χ(s)ρ_{2}(s)) & = & \frac{1}{2}(n + par(n)) \\ c_{2} & = & \frac{1}{2}(χ(1)ρ_{1}(1) + χ(s)ρ_{2}(s)) & = & \frac{1}{2}(n − par(n)) . \end{aligned}

Die Zerlegung von X lautet X = (X_{1}, X_{2}), wobei X_{j} c_{j} Spalten hat, welche den invarianten Unterraum V_{j} von P aufspannen. V_{1}, V_{2} sind hier leicht zu erraten: Je nachdem n gerade oder ungerade ist, hat man die Basen von V_{1}, V_{2}

n gerade (8)  n ungerade (7)
X_{1}  X_{2}  X_{1}  X_{2}

\begin{matrix}1 & 1 & & & & 1 \\ 2 & & 1 & & & & 1 \\ 3 & & & 1 & & & & 1 \\ 4 & & & & 1 & & & & 1 \\ 5 & & & & 1 & & & & −1 \\ 6 & & & 1 & & & & −1 \\ 7 & & 1 & & & & −1 \\ 8 & 1 & & & & −1 \end{matrix} \begin{matrix}1 & 1 & & & & 1 \\ 2 & & 1 & & & & 1 \\ 3 & & & 1 & & & & 1 \\ 4 & & & & 1 \\ 5 & & & 1 & & & & −1 \\ 6 & & 1 & & & & −1 \\ 7 & 1 & & & & −1 \end{matrix}(4.1.8)

Die Anzahl der gefundenen linear unabhängigen Vektoren entspricht jeweils genau der Dimension von V_{1}, V_{2}. Jeder der gefundenen Vektoren spannt einen eindimensionalen invarianten Unterraum von P auf, auf denen P durch U_{1} oder U_{2} gegeben ist, je nachdem er zu V_{1} oder V_{2} gehört. Das ist aber gerade das, was (4.1.2) für die Spalten von X_{1}, X_{2} aussagt. Wir können also für X die gefundenen Vektoren (4.1.8) nehmen. Zur Bestätigung bilden wir noch

T_{1} = \frac{1}{2}(I + P) , T_{2} = \frac{1}{2}(I − P) .

Tatsächlich projeziert T_{1} auf V_{1}, T_{2} auf V_{2}.

2) Im obigen Beispiel 4b) ist G = D_{4} = {1, r, r^{2}, r^{3}, s, sr, sr^{2}, sr^{3}}. D_{4} hat das MIP U_{1}, U_{2}, U_{3}, U_{4}, U_{5} mit den Geraden 1, 1, 1, 1, 2. Die Tabelle der Charaktere χ_{j} von U_{j} ist

\begin{aligned}& r^{k} & sr^{k} \\ χ_{1} & 1 & 1 \\ χ_{2} & 1 & −1 \\ χ_{3} & (−1)^{k} & (−1)^{k} \\ χ_{4} & (−1)^{k+1} & (−1)^{k+1} \\ χ_{5} & i^{k} + (−i)^{k} & 0 \end{aligned} k = 0, 1, 2, 3 .

Für den Charakter χ von P gilt

χ(g) = Anzahl der Knoten, die bei g fest bleiben.

Damit erhält man ohne Mühe

\begin{matrix}g & 1 & r & r^{2} & r^{3} & s & sr & sr^{2} & sr^{3} \\ χ(g) & 9 & 1 & 1 & 1 & 3 & 3 & 3 & 3 \end{matrix}

Für die Vielfachheiten c_{j}, mit denen U_{j} in P enthalten ist, ergibt sich

c_{1} = ⟨χ, χ_{1}⟩ = \frac{1}{8}(9 + 1 + 1 + 1 + 3 + 3 + 3 + 3) = 3

c_{2} = 0 ,  c_{3} = c_{4} = 1 ,  c_{5} = 2 .

Die invarianten Unterräume V_{1}, V_{2}, V_{3}, V_{4}, V_{5} haben damit der Reihe nach die Dimensionen 3, 0, 1, 1, 4. Basen findet man wie beim ersten Beispiel (aber etwas mühsamer) durch Suchen nach unter P invarianten Vektoren und Unterräumen.

X_{1,1} X_{1,2} X_{1,3}  X_{3}  X_{4}  X_{5,1}  X_{5,2}

\begin{matrix}0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & −1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & −1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & −1 & −1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & −1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & −1 & 0 & 1 & −1 & 0 & −1 \end{matrix}

Die Matrix A zerfällt bezüglich dieser Basis in

( \begin{matrix}A_{1} & & & & & & O \\ & A_{1} \\ & & A_{1} \\ & & & A_{3} \\ & & & & A_{4} \\ & & & & & A_{5} \\ O & & & & & & A_{5} \end{matrix} )

mit (1, 1)-Matrizen A_{1}, A_{3}, A_{4} und einer (2, 2)-Matrix A_{5}.

Bleibt noch das Problem der Invertierung von X bzw. Y. Diese wird durch folgenden Satz erleichtert.

3) Das obige Beispiel 1) ist besonders einfach. Die Faltung A hat die Symmetrien der regulären Darstellung P von C_{n}, und

U_{j}(a^{k}) = ω^{k_{j}} , ω = e^{−2πi/n} , j = 0, …, n − 1

definiert ein MIP von C_{n}. Jedes U_{j} kommt genau einmal in P vor. Wir haben also c_{j} = n_{j} = 1, j = 0, …, n − 1 und damit

A = X ( \begin{matrix}A_{0} \\ & . & . & . \\ & & & & A_{n−1} \end{matrix} ) X^{−1}

mit komplexen Zahlen A_{0}, …, A_{n−1}. Die Spalten der Matrix

X = W_{n} = (ω^{k_{j}})_{k,j=0,...,n−1}

sind invariante Unterräume von P. A wird also durch W_{n} diagonalisiert. Dies haben wir in Satz 3.3.1 schon gesehen.

Man kann eine rationale Form von X erhalten, wenn man die invarianten Unterräume geeignet zusammenfaßt. Seien ϕ_{d} die Kreisteilungspolynome, und sei X_{d} die Matrix der Spalten von W_{n}, welche zu den Nullstellen von ϕ_{d} gehören. Da die Kreisteilungspolynome ganzzahlige Koeffizienten haben, gibt es in dem von X_{d} aufgespannten invarianten Unterraum V_{d} eine ganzzahlige Basis X′_{d}. Setzen wir X′ = (X′_{d})_{d/n}, so ist

A = X′ ( \begin{matrix}A_{1} \\ & . & . & . \\ & & & & A_{r} \end{matrix} ) (X′)^{−1} .

Dabei gehört jede Matrix A_{j} zu einem Teiler von n, und die Dimension von A_{j} entspricht dem Grad des zugehörigen Kreisteilungspolynoms.

Wir führen dies für den Fall n = 6 durch. Es ist

z^{6} − 1 = ϕ_{1}ϕ_{2}ϕ_{3}ϕ_{6}

mit

ϕ_{1} = z − 1 , ϕ_{2} = z + 1 , ϕ_{3} = z^{2} + z + 1 , ϕ_{6} = z^{2} − z + 1 .

Ganzzahlige Basen der eindimensionalen invarianten Unterräume V_{1}, V_{2} sind leicht gefunden, nämlich

X′_{1} = ( \begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix} ) , X′_{2} = ( \begin{matrix}1 \\ −1 \\ 1 \\ −1 \\ 1 \\ −1 \end{matrix} ) .

Sei (x_{0}, …, x_{5}) ∈ V_{3}. Er ist eine Linearkombination von Vektoren (1, ω, …, ω^{5}) mit ϕ_{3}(ω) = ω^{2} + ω + 1 = 0. Also gilt

x_{0} + x_{1} + x_{2} = 0 ,
x_{1} + x_{2} + x_{3} = 0 ,
x_{2} + x_{3} + x_{4} = 0 ,
x_{4} + x_{5} + x_{6} = 06.

Dieses System besitzt zwei linear unabhängige ganzzahlige Lösungen, nämlich

X′_{3} = ( \begin{matrix}1 & −1 \\ 0 & 2 \\ −1 & −1 \\ 1 & −1 \\ 0 & 2 \\ −1 & −1 \end{matrix} ) .

Für V_{4} findet man auf die gleiche Art eine Basis

X′_{4} = ( \begin{matrix}1 & −1 \\ 1 & 1 \\ 0 & 2 \\ −1 & 1 \\ −1 & −1 \\ 0 & −2 \end{matrix} ) .

Man berechnet X^{′T} X′ = diag (6, 6, 4, 12, 4, 12) und hat damit

A = X^{′T} ( \begin{matrix}A_{1} \\ & A_{2} \\ & & A_{3} \\ & & & A_{4} \end{matrix} ) X′

mit (1, 1)-Matrizen A_{1}, A_{2} und (2, 2)-Matrizen A_{3}, A_{4}. Die Faltung der Länge 6 läßt sich also durch 1 + 1 + 4 + 4 = 10 Multiplikationen realisieren.

Satz 4.1.5 Sind P, U_{1}, …, U_{r} unitär und werden die Vektoren X′_{jν1}, ν = 1, …, c_{j} orthonormal gewählt, so ist X′ unitär.

Beweis: Wir schreiben X für X′. Ist P unitär, so gilt für alle g ∈ G

X_{jν}^{∗}X_{iμ} = (P (g)X_{jν})^{∗}P (g)X_{iμ}

und damit

X_{jν}^{∗}X_{iμ} = \frac{1}{|G|} ∑_{g∈G}(P (g)X_{jν})^{∗}P (g)X_{iμ}

= \frac{1}{|G|} ∑_{g∈G}(X_{jν}U_{j}(g))^{∗}X_{iμ}U_{i}(g)

wegen (4.1.4). Da die U_{j} unitär sind, ist U_{j}^{∗}(g) = U_{j}(g^{−1}), also

X_{jν}^{∗}X_{iμ} = \frac{1}{|G|} ∑_{g∈G} U_{j}^{∗}(g)X_{jν}^{∗}X_{iμ}U_{i}(g)

= \frac{1}{|G|} ∑_{g∈G} U_{j}(g^{−1})X_{jν}^{∗}X_{iμ}U_{i}(g) .

Aus den Orthogonalitätsrelationen (Satz 2.1.10) folgt nun

X_{jν}^{∗}X_{iμ} = 0 , i ≠ j .

Für i ≠ j sind also alle Spalten von X_{j} orthogonal zu allen Spalten von X_{i}. Für i = j setzen wir S = X_{jν}^{∗}X_{jμ}. Dann gilt

S_{kℓ} = \frac{1}{|G|} ∑_{g∈G} ∑_{m,n=1}^{n_{j}} U_{j}^{km}(g^{−1})S_{mn}U_{j}^{nℓ}(g) .

Wieder nach den Orthogonalitätsrelationen folgt S_{kℓ} = 0 für k ≠ ℓ. Also sind X_{jνℓ}, X_{jμk} orthogonal für ℓ ≠ k und alle ν, μ. Bleibt noch zu sagen, daß

X_{jνℓ}^{∗}X_{jμℓ} = δ_{νμ} , ν, μ = 1, …, c_{j} .

Nach (4.1.7) ist

X_{jνℓ}X_{jμℓ} = (T_{j}^{1ℓ}X_{jν1})^{∗}X_{jμℓ}
= X_{jν1}^{∗}(T_{j}^{1ℓ})^{∗}X_{jμℓ} .  (4.1.9)

4.1. MATRIZEN MIT SYMMETRIEN 87 Da P und U_{j} unitär sind, gilt

(T_{j}^{1ℓ})^{∗} = \frac{n_{j}}{|G|} ∑_{g∈G} \overline{U}_{j}^{1ℓ}(g^{−1})P^{∗}(g)
= \frac{n_{j}}{|G|} ∑_{g∈G} \overline{U}_{j}^{1ℓ}(g^{−1})P (g^{−1})
= \frac{n_{j}}{|G|} ∑_{g∈G} \overline{U}_{j}^{1ℓ}(g)P (g)
= T_{j}^{ℓ1} .

Nach (4.1.7) folgt also schließlich aus (4.1.9)

X_{jνℓ}^{∗}X_{jμℓ} = X_{jν1}^{∗}T_{j}^{ℓ1}X_{jμℓ}
= X_{jν1}^{∗}X_{jμ1} = δ_{νμ} ,

weil die X_{jν1} ja als Orthonormalsystem konstruiert wurden.

□

4.2 Untergruppen

Seien P, Q wieder Darstellungen der Gruppe G. Wir betrachten nun den Fall, daß G eine Untergruppe H besitzt. Seien U_{1}, …, U_{r} ein MIP für H. Dann gilt also mit gewissen Matrizen X, Y und gewissen natürlichen Zahlen c_{j}, d_{j} für h ∈ H

P (h) = X ( \begin{matrix}I_{c_{1}} ⊗ U_{1}(h) \\ & . & . & . \\ & & & & I_{c_{r}} ⊗ U_{r}(h) \end{matrix} ) X^{−1} ,

(4.2.1)

Q(h) = Y ( \begin{matrix}I_{d_{1}} ⊗ U_{1}(h) \\ & . & . & . \\ & & & & I_{d_{r}} ⊗ U_{r}(h) \end{matrix} ) Y^{−1}.

Satz 4.2.1 A besitze die Symmetrien von P, Q. Die Untergruppe H von G liege im Zentrum von G. Dann gibt es Darstellungen P_{1}, …, P_{r} der Grade c_{1}, …, c_{r} und Q_{1}, …, Q_{r} der Grade d_{1}, …, d_{r} von G, so daß

A = Y ( \begin{matrix}A_{1} \\ & . & . & . \\ & & & & A_{r} \end{matrix} ) X^{−1}  (4.2.2)

mit (c_{j}, d_{j})-Matrizen A_{j}, welche die Symmetrien von P_{j}, Q_{j} besitzen. Auf H sind P_{j}, Q_{j} Vielfache der Einheitsmatrix.

Beweis: A besitzt die Symmetrien der Restriktionen P_{H}, Q_{H} von P, Q auf H. Deshalb ist (4.2.2) eine unmittelbare Folgerung aus Satz 4.1.2. Da H im Zentrum von G liegt, ist gh = hg für h ∈ H und g ∈ G, also P (g)P (h) = P (h)P (g), und entsprechend für Q. Es besitzt also jede Matrix P (g) die Symmetrien von P_{H}, jede Matrix Q(g) diejenigen von Q_{H}. Wieder nach Satz 4.1.2 folgt

P (g) = X ( \begin{matrix}P_{1}(g) \\ & . & . & . \\ & & & & P_{r}(g) \end{matrix} ) X^{−1} ,

(4.2.3)

Q(g) = Y ( \begin{matrix}Q_{1}(g) \\ & . & . & . \\ & & & & Q_{r}(g) \end{matrix} ) Y^{−1}

mit (c_{j}, c_{j})-Matrizen P_{j}(g) und (d_{j}, d_{j})-Matrizen Q_{j}(g). Offenbar sind P_{j}, Q_{j} Darstellungen von G. Vergleich mit (4.2.1) ergibt, daß für h ∈ H

P_{j}(h) = I_{c_{j}} ⊗ U_{j}(h) , Q_{j}(h) = I_{d_{j}} ⊗ U_{j}(h)

ist. Da H im Zentrum von G liegt, ist H abelsch. Also hat U_{j} den Grad 1, und wir haben sogar

P_{j}(h) = U_{j}(h)I_{c_{j}} , Q_{j}(h) = U_{j}(h)I_{d_{j}} .

P_{j}, Q_{j} sind also auf H Vielfache der Einheitsmatrix. Daß A_{j} die Symmetrien von P_{j}, Q_{j} hat, rechnet man mit Hilfe von (4.2.2), (4.2.3) und AP = QA unmittelbar nach.

□

Betrachten wir den Satz auf der Faktorgruppe G/H, so gewinnt er einen weiteren Aspekt. Dazu müssen wir allerdings den Begriff der Darstellung etwas erweitern.

Definition 4.2.2 Sei G eine endliche Gruppe und V ein Vektorraum über C. Eine Abbildung ρ: G → GL(V) heißt projektive Darstellung von G in V, falls

ρ(st) = α(s, t)ρ(s)ρ(t) , s, t ∈ G

mit α(s, t) ∈ C.

Projektive Darstellungen verhalten sich für die von uns diskutierten Fragen genau so wie Darstellungen. Satz 4.2.1 kann jetzt eleganter formuliert werden.

Satz 4.2.3 A besitze die Symmetrien von P, Q. Die Untergruppe H von G liege im Zentrum von G. Dann gibt es projektive Darstellungen P_{1}, …, P_{r} der Grade c_{1}, …, c_{r} und Q_{1}, …, Q_{r} der Grade d_{1}, …, d_{r} von G/H, so daß

A = Y ( \begin{matrix}A_{1} \\ & . & . & . \\ & & & & A_{r} \end{matrix} ) X^{−1}

mit (c_{j}, d_{j})-Matrizen, welche die Symmetrien von P_{j}, Q_{j} besitzen.

Beweis: Seien P_{j}, Q_{j} die Darstellungen von G aus Satz 4.2.1. Sei g_{1}, …, g_{m} ein Repräsentantenssystem von G/H, also G/H = {g_{1}H, …, g_{m}H}. Wir setzen

P̃_{j}(g_{k}H) = P_{j}(g_{k})

und zeigen, daß P̃_{j} eine projektive Darstellung von G/H ist. Zu k, ℓ gibt es i mit g_{k}g_{ℓ}H = g_{i}H, d.h. es gibt h ∈ H (abhängig von g_{k}, g_{ℓ}) mit g_{k}g_{ℓ}h = g_{i}. Also ist

P̃_{j}(g_{k}Hg_{ℓ}H) = P̃_{j}(g_{i}H) = P_{j}(g_{i})
= P_{j}(g_{k}g_{ℓ}H)
= P_{j}(g_{k}g_{ℓ})P_{j}(h)
= P_{j}(g_{k})P_{j}(g_{ℓ})P_{j}(h)
= P̃_{j}(g_{k}H)P̃_{j}(g_{ℓ}H)P_{j}(h) .

Auf H ist P_{j} ein Vielfaches der Einheitsmatrix, also P_{j}(h) = α_{j}(h)I_{c_{j}}. Damit haben wir schließlich

P̃_{j}(g_{k}Hg_{ℓ}H) = α_{j}(h)P̃_{j}(g_{k}H)P̃_{j}(g_{ℓ}H) ,

d.h. P̃_{j} ist eine projektive Darstellung von G/H. Entsprechend definiert man die projektive Darstellung Q̃_{j} von G/H. Für P̃_{j}, Q̃_{j} gilt

A_{j}P̃_{j}(g_{k}H) = A_{j}P_{j}(g_{k}) = Q_{j}(g_{k})A_{j} = Q̃_{j}(g_{k}H)A_{j} ,

d.h. A_{j} hat die Symmetrien von P̃_{j}, Q̃_{j}.

□

4.3 Direkte Produkte

Sei G das direkte Produkt der Gruppen G_{1}, G_{2}, also G = G_{1} ⊗ G_{2}. Sind R_{i}, Q_{i} Darstellungen von G_{i} der Grade n_{i}, m_{i}, so sind

P (st) = P_{1}(s) ⊗ P_{2}(t) , Q(st) = Q_{1}(s) ⊗ Q_{1}(t) , s ∈ G_{1} , t ∈ G_{2}

Darstellungen von G der Grade n = n_{1}n_{2}, m = m_{1}m_{2}.

Satz 4.3.1 Die (m, n)-Matrix A hat genau dann die Symmetien von P, Q, wenn A eine (m_{1}, n_{1})-Matrix von (m_{2}, n_{2})-Matrizen A_{j,k} = (A_{j,k}^{ν,μ}) ist mit folgenden Eigenschaften: A_{j,k} hat die Symmetrien von P_{2}, Q_{2}, und die (m_{1}, n_{1})-Matrizen A^{ν,μ} = (A_{j,k}^{ν,μ}) haben die Symmetrien von P_{1}, Q_{1}.

Beweis: Wegen der Rechenregeln des Tensorproduktes gilt A(P_{1} ⊗ P_{2}) = (Q_{1} ⊗ Q_{2})A genau dann, wenn A(I_{n_{1}} ⊗ P_{2}) = (I_{m_{1}} ⊗ Q_{2})A und A(P_{1} ⊗ I_{n_{2}}) = (Q_{1} ⊗ I_{m_{2}})A gilt. Die erste dieser Beziehungen bedeutet A_{j,k}P_{2} = Q_{2}A_{j,k}, d.h. A_{j,k} hat die Symmetrien von P_{2}, Q_{2}. Die zweite Beziehung lautet ausführlich geschrieben

( A_{11}, …, A_{1,n_{1}} ; ⋮ ; A_{n_{1},1}, …, A_{m_{1},n_{1}} ) ( p_{1}^{1,1}I_{n_{2}}, …, p_{1}^{1,n_{1}}I_{n_{2}} ; ⋮ ; p_{1}^{n_{1},1}I_{n_{2}}, …, p_{1}^{n_{1},n_{1}}I_{n_{2}} )

= ( q_{1}^{1,1}I_{m_{2}}, …, q_{1}^{1,m_{1}}I_{m_{2}} ; ⋮ ; q_{1}^{m_{1},1}I_{m_{2}}, …, q_{1}^{m_{1},m_{1}}I_{m_{2}} ) ( A_{1,1}, …, A_{1,n_{1}} ; ⋮ ; A_{m_{1},1}, …, A_{m_{1},n_{1}} ) ,

wo natürlich P_{1} = (P_{1}^{iℓ}), Q_{1} = (q_{1}^{iℓ}) ist. Dies bedeutet

∑_{k=1}^{n_{1}} A_{j,k}p_{1}^{k,ℓ} = ∑_{k=1}^{m_{1}} q_{1}^{j,k}A_{k,ℓ} , j = 1, …, m_{1}, ℓ = 1, …, n_{1} ,

oder, elementweise

∑_{k=1}^{n_{1}} A_{j,k}^{ν,μ}p_{1}^{k,ℓ} = ∑_{k=1}^{m_{1}} q_{1}^{j,k}A_{k,ℓ}^{ν,μ} .

Dies bedeutet aber gerade A^{ν,μ}P_{1} = Q_{1}A^{ν,μ}, d.h. A^{ν,μ} hat die Symmetrien von P_{1}, Q_{1}.

□

Diesen Satz wollen wir auf Faltungen auf G anwenden.

Diese haben wir schon in III.3.5 eingeführt durch

(x ⋆ y)_{g} = ∑_{{u,s∈G \atop us=g}} x_{s}y_{u} = ∑_{u∈G} x_{u^{−1}g}y_{u} .

Sei P die reguläre Darstellung von G, d.h.

P (t)x = ∑_{g∈G} x_{t^{−1}g}e_{g} für x = ∑_{g∈G} x_{g}e_{g}

mit einer Basis (e_{g})_{g∈G} des Darstellungsraumes von P. Dann ist

P (t)(x ⋆ y) = ∑_{g∈G}(x ⋆ y)_{t^{−1}g}e_{g} = ∑_{g∈G} ∑_{us=t^{−1}g} x_{s}y_{u}e_{g}
= ∑_{g∈G} ∑_{vs=g} x_{s}y_{t^{−1}v}e_{g} = x ⋆ P (t)y .

Die Faltung X = (x_{u^{−1}t})_{t,u∈G} hat also die Symmetrien von ρ, und umgekehrt ist jede (|G|, |G|)-Matrix X mit dieser Eigenschaft eine Faltung.

Diesen Satz wollen wir auf Faltungen auf G anwenden.

Sei P die reguläre Darstellung von G. Diese läßt sich aus den regulären Darstellungen P_{1}, P_{2} von G_{1}, G_{2} leicht gewinnen.

Satz 4.3.2 Seien P_{1}, P_{2} die reguläre Darstellungen von G_{1}, G_{2}. Dann gilt für die reguläre Darstellung P von G_{1} ⊗ G_{2}

P (st) = P_{1}(s) ⊗ P_{2}(t) , s ∈ G_{1} , t ∈ G_{2} .

Beweis. Sei G_{1} = {s_{1}, …, s_{n}}, G_{2} = {t_{1}, …, t_{m}} und G = {s_{1}t_{1}, …, s_{1}t_{m}, s_{2}t_{1}, …, s_{2}t_{m}, …, s_{n}t_{1}, …, s_{n}t_{m}}. Es ist nach Definition der regulären Darstellung

P_{1}(s_{j}) ( x_{1} ; ⋮ ; x_{n} ) = ( x_{π_{j}(1)} ; ⋮ ; x_{π_{j}(n)} ) , P_{2}(t_{k}) ( x_{1} ; ⋮ ; x_{m} ) = ( x_{σ_{k}(1)} ; ⋮ ; x_{σ_{k}(m)} ) ,

wobei π_{j} die Permutation mit s_{j}^{−1}s_{ℓ} = s_{π_{j}(ℓ)} ist; entsprechend ist σ die Permutation mit t_{k}^{−1}t_{i} = t_{σ_{k}(i)}. Sei nun x ∈ C^{nm} aufgespaltet in

x = ( x_{1} ; ⋮ ; x_{n} ) ∈ C^{m} .

Der Vektor P_{1}(s_{j}) ⊗ P_{2}(t_{k})x entsteht dann aus x durch zwei Operationen.

1. Man übt auf die Komponenten jedes x_{i} der Permutation σ_{k} aus.

2. Man übt auf ( x_{1} ; ⋮ ; x_{n} ) die Permutation π_{j} aus.

Genau diese Permutation übt aber auch P (s_{j}t_{k}) aus, denn es ist

(s_{j}t_{k})^{−1}s_{ℓ}t_{i} = t_{k}^{−1}s_{j}^{−1}s_{ℓ}t_{i}
= s_{j}^{−1}s_{ℓ}t_{k}^{−1}t_{i}
= s_{π_{j}(ℓ)}t_{σ_{k}(i)} .

Also ist P (s_{j}t_{k}) = P_{1}(s_{j}) ⊗ P_{2}(t_{k}).

□

Bemerkung: Diese Formel gilt nur, wenn G so angeordnet wird (lexikographisch), wie es im Beweis gemacht wurde.

Satz 4.3.3 Sei A die Faltung auf G und G = G_{1} ⊗ G_{2}. Die Faltung auf G_{1} werden beschrieben durch die Permutation π_{j}, d.h. sie sind von der Gestalt

( x_{π_{1}(1)} ⋯ x_{π_{1}(n)} ; ⋮ ; x_{π_{n}(1)} ⋯ x_{π_{n}(n)} )

94 KAPITEL 4. SYMMETRIE Dann gibt es Faltungen A_{1}, …, A_{n} auf G_{2}, so daß

A = ( A_{π_{1}(1)} ⋯ A_{π_{1}(n)} ; ⋮ ; A_{π_{n}(1)} ⋯ A_{π_{n}(n)} ) .

Beweis: Folgt sofort aus den beiden vorigen Sätzen.

□

4.4 Die Fourier-Transformation auf Gruppen

Sei G eine endliche Gruppe und Ĝ ein MIP von G. Ist G abelsch, so ist Ĝ wieder eine Gruppe, der Dual von G.

Definition 4.4.1 Sei f eine komplexwertige Funktion auf G. Dann heißt die Funktion f̂ auf Ĝ, welche durch

f̂(ξ) = \frac{1}{n} ∑_{g∈G} f(g)ρ(g) , ρ ∈ Ĝ

definiert ist, Fourier-Transform von f.

Bemerkungen:

1) Da Ĝ durch G nicht eindeutig bestimmt ist, gibt es in Wahrheit viele Fourier-Transformationen auf G. Wir ignorieren diese Mehrdeutigkeit, denken uns Ĝ also ein für allemal gewählt.

2) Ist d_{ρ} der Grad von ρ, so gilt nach Satz 2.2.7 ∑_{ρ∈Ĝ} d_{ρ}^{2} = |G|.

Da f̂(ρ) für jedes ρ durch d_{ρ}^{2} Matrix-Element bestimmt ist, enthält f̂ die gleiche Anzahl von Freiheitsgraden wie f, nämlich ∑_{ρ∈Ĝ} d_{ρ}^{2} = |G|. Wir

können die Fourier-Transformation ansehen als lineare Abbildung von C^{n}, n = |G| in ⨁_{ρ∈Ĝ} C^{d_{ρ}^{2}}, oder aber als lineare Abbildung von C^{n} in C^{n}.

3) Die Anzahl der Rechenoperationen (= 1 komplexe Multiplikation + 1 komplexe Addition) für die Fourier-Transformation ist offenbar

∑_{ρ∈Ĝ} |G|d_{ρ}^{2} = |G|^{2} .

Bespiele:

1) G = C_{n} = {1, a, …, a^{n−1}}, a^{n} = 1, Ĝ = {ρ_{0}, …, ρ_{n−1}} mit ρ_{j}(a^{k}) = ω^{jk}, ω = e^{−2πi/n}. Dann ist f̂ die gewöhnliche Fourier-Transformation der Länge n.

2) Sei G = C_{n_{1}} ⊗ ⋯ ⊗ C_{n_{p}} = {a_{1}^{k_{1}}a_{p}^{k_{p}} : 0 ≤ k_{r} < n_{r}}, a_{r}^{n_{r}} = 1, und Ĝ = {ρ_{j_{1},...,j_{r}} : 0 ≤ j_{r} < n_{r}, r = 1, …, p},

ρ_{j_{1},...,j_{p}}(a_{1}^{k_{1}} ⋯ a_{p}^{k_{p}}) = ω_{1}^{j_{1}k_{1}} ⋯ ω_{p}^{j_{p}k_{p}}

mit ω_{r} = e^{−2πi/n_{r}}. Dann ist

f̂(ρ_{j_{1},...,j_{p}}) = \frac{1}{n_{1} ⋯ n_{p}} ∑_{k_{1}=0}^{n_{1}−1} ⋯ ∑_{k_{p}=0}^{n_{p}−1} f(a_{1}^{k_{1}} ⋯ a_{p}^{k_{p}})
ω_{1}^{j_{1}k_{1}} ⋯ ω_{p}^{j_{p}k_{p}} .

Dies ist die p-dimensionale Fourier-Transformation.

3) G = C_{2} ⊗ ⋯ ⊗ C_{2} (p mal). Dann erhalten wir aus Beispiel 2 - in geringfügig geänderter Notation -

f̂_{j_{1},...,j_{p}} = 2^{−p} ∑_{0≤k_{1},...,k_{p}≤1} f_{k_{1},...,k_{p}}(−1)^{j_{1}k_{1}+···+j_{p}k_{p}} .

Dies ist die Hadamard-Walsh-Transformation.

Satz 4.4.2 Die Fourier-Transformation ist injektiv, und es gilt

f(g) = ∑_{ρ∈Ĝ} d_{ρ}tr(f̂(ρ)ρ(g^{−1})) ,

wobei d_{ρ} der Grad von ρ ist.

4.4. DIE FOURIER-TRANSFORMATION AUF GRUPPEN 97 Beweis: Es ist

∑_{ρ∈Ĝ} d_{ρ}tr(f̂(ρ))ρ(g^{−1}) = \frac{1}{|G|} ∑_{ρ∈Ĝ} d_{ρ}tr (∑_{t∈G} f(t)ρ(t)ρ(g^{−1}))
= \frac{1}{|G|} ∑_{ρ∈Ĝ} d_{ρ}tr (∑_{t∈G} f(t)ρ(tg^{−1}))
= \frac{1}{|G|} ∑_{ρ∈Ĝ} d_{ρ}tr (∑_{s∈G} f(sg)ρ(s))
= \frac{1}{|G|} ∑_{s∈G} f(sg) ∑_{ρ∈Ĝ} d_{ρ}tr(ρ(s))
= \frac{1}{|G|} ∑_{s∈G} f(sg)χreg(s) ,

mit dem regulären Charakter χreg, vgl. II.2. Nun ist aber

χreg(s) = \{ \begin{matrix}|G| & , & s = 1 , \\ 0 & , & sonst . \end{matrix}

Also folgt

∑_{ρ∈Ĝ} d_{ρ}tr(f̂(ρ))ρ(g^{−1}) = f(g) .

□

Bemerkung: Auch die inverse Fourier-Transformation erfordert

|G| ∑_{ρ∈Ĝ} d_{ρ}^{2} = |G|^{2}

Rechenoperationen. Satz 4.4.3 Sei f ⋆ g die Faltung von f, g auf G. Dann gilt

(f ⋆ g)^{∧}(ρ) = |G|f̂(ρ)ĝ(ρ) .

Beweis: Es ist

(f ⋆ g)^{∧}(ρ) = \frac{1}{|G|} ∑_{t∈G}(f ⋆ g)(t)ρ(t)

= \frac{1}{|G|} ∑_{t∈G} ∑_{s∈G} f(s^{−1}t)g(s)ρ(t)

= \frac{1}{|G|} ∑_{s∈G} g(s)ρ(s) ∑_{t∈G} ρ(s^{−1}t)f(s^{−1}t)

= \frac{1}{|G|} ∑_{s∈G} g(s)ρ(s) ∑_{t∈G} f(t)ρ(t)
= |G|ĝ(ρ)f̂(ρ) .
□

Aus 4.3 wissen wir, daß die (n, n)-Matrix A (n = |G|) genau dann eine Faltung auf G ist, wenn sie mit der regulären Darstellung P von G vertauschbar ist. Nach Satz 4.1.2 zerfällt A also in |Ĝ| Matrizen I_{d_{ρ}} ⊗A_{ρ} mit (d_{ρ}, d_{ρ})-Matrizen A_{ρ}. Die Anwendung von A auf einen Vektor x der Länge n = |G| ist also äquivalent der Anwendung der Matrizen A_{ρ} auf d_{ρ} Vektoren der Länge d_{ρ}, ρ ∈ Ĝ. Die Komplexität von x → Ax fällt also von |G|^{2} auf

∑_{ρ∈Ĝ} d_{ρ}^{3} ≤ |G| \begin{matrix}Max \\ ρ ∈ Ĝ \end{matrix} |d_{ρ}| .

Dabei haben wir die Matrix X = Y in (4.1.3) noch nicht berücksichtigt. Den gleichen Rechenaufwand erhält man, wenn man Ax nach Satz 4.4.3 berechnet. X wird also - wie im Falle G = C_{n} - durch die Fourier-Transformation geliefert.

Nun zur Fourier-Transformation. Wir berechnen

(P (g)f)^{∧}(ρ) = \frac{1}{|G|} ∑_{t∈G}(P (g)f)(t)ρ(t)

= \frac{1}{|G|} ∑_{t∈G} f(g^{−1}t)ρ(t) = \frac{1}{|G|} ∑_{s∈G} f(s)ρ(gs)
= ρ(g)f̂(ρ) .

Ist also W_{G} : C^{n} → ⨂_{ρ∈Ĝ} C^{d_{ρ}^{2}} die Fourier-Transformation auf G und

Q(g) = ⨂_{ρ∈Ĝ} ρ(g), so ist

W_{G}P (g) = Q(g)W_{G} , ∀g ∈ G

d.h. W_{G} hat die Symmetrien von P, Q. Damit können wir alle Methoden zur Konstruktion schneller Fourier-Transformationen, die wir für zyklische Gruppen kennengelernt haben, auf allgemeine Gruppen übertragen. Wir wollen dies am Beispiel von direkten Produkten durchführen.

Satz 4.4.4 Sei G = G_{1}⊗⋯⊗G_{r}. Dann läßt sich die Fourier-Transformation auf C in

|G| ∑_{j=1}^{p} |G_{j}|

Rechenoperationen durchführen.

Beweis: Wir zeigen den Satz für G = A ⊗ B. Sind Â, B̂ MIP’s für A, B, so ist durch

ρ(ab) = σ(a) ⊗ τ(b) , σ ∈ Â , τ ∈ B̂ , a ∈ A , b ∈ B

ein MIP Ĝ für G definiert, und es ist

f̂(σ ⊗ τ) = \frac{1}{|A||B|} ∑_{{a∈A \atop b∈B}} f(ab)σ(a) ⊗ τ(b)

= \frac{1}{|A||B|} ∑_{a∈A} σ(a) ⊗ ∑_{b∈B} f(ab)τ(b) .

Die Auswertung der b-Summe für ein a benötigt |B|d_{τ}^{2} Rechenoperationen, die Ausführung des Tensorprodukts für ein a deren d_{σ}^{2}d_{τ}^{2} (d_{σ}, d_{τ} sind natürlich die Grade von σ, τ). Damit verlangt f̂

|A| ∑_{τ∈B̂} |B|d_{τ}^{2} + ∑_{σ∈Â} ∑_{τ∈B̂} |A|d_{σ}^{2}d_{τ}^{2}
= |A| |B|^{2} + |A|^{2}B = |G|(|A| + |B|)

Rechenoperationen.

□

100 KAPITEL 4. SYMMETRIE

Toeplitz-Matrizen

5.1 Der Algorithmus von Trench

Im letzten Abschnitt haben wir effiziente Algorithmen zur zyklischen Faltung definiert. Wir hatten gezeigt, daß die Faltung zweier Vektoren der Anwendung einer Matrix A entspricht mit A = P^{t}AP und P = (e_{2}, e_{3}, …, e_{n}, e_{1}). Hierbei bewirkt die Rechtsmultiplikation mit P eine zyklische Verschiebung der Spalten nach links, eine Linksmultiplikation mit P^{t} eine zyklische Verschiebung der Zeilen nach oben.

Wir definieren nun die Toeplitz-Matrizen als Erweiterung des Matrizenraums der zyklischen Faltung.

Definition 5.1.1 Eine (n, n)–Matrix der Form

A = ( \begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−2} & a_{n−1} \\ a_{−1} & ... & ... & & a_{n−2} \\ ⋮ & ... & ... & ... & ⋮ \\ a_{−(n−2)} & & ... & ... & a_{1} \\ a_{−(n−1)} & a_{−(n−2)} & ⋯ & a_{−1} & a_{0} \end{matrix} )

heißt Toeplitz–Matrix. A ist symmetrische Faltung genau dann, wenn a periodisch ist mit Periode n.

Bemerkung: Für alle Toeplitz–Matrizen A gilt rang(A − P^{t}AP) ≤ 2, denn

A − P^{t}AP = ( \begin{matrix}0 & ⋯ & 0 & a_{n−1} − a_{−1} \\ ⋮ & & ⋮ & ⋮ \\ 0 & & 0 & a_{1} − a_{n+1} \\ a_{−(n−1)} − a_{1} & ⋯ & a_{−1} − a_{n−1} & 0 \end{matrix} ) .

Der Rang ist also zwar nicht mehr unbedingt 0, aber klein.

Satz 5.1.2 Für eine (n, n) Toeplitz–Matrix A und einen Vektor x kann Ax durch eine zyklische Faltung der Länge M ≥ 2n − 1 berechnet werden.

Beweis: Wir erweitern A sinnvoll so, daß sich eine zyklische Faltung ergibt. Sei A definiert durch den Vektor a_{k}, k = −n − 1 … n − 1. Definiere den Vektor α_{k} aus C^{M}, k = −M − 1 … M − 1, durch

α_{k} := \{ \begin{matrix}a_{k} & −n − 1 ≤ k ≤ n − 1 \\ a_{k−M} & k > M − n \\ a_{k+M} & k < n − M \\ 0 & sonst. \end{matrix} .

Der so definierte Vektor ist periodisch mit der Periode M. α definiert eine (M, M)–Toeplitz–Matrix A′, die eine zyklische Faltung ist, und deren linke obere (n, n)–Untermatrix mit A übereinstimmt. Wir wenden A′ auf den Vektor

x′ = ( \begin{matrix}x \\ 0 \end{matrix} ) ∈ C^{M}

an. Da A_{i,k} = A′_{i,k} für i = 1 … n, k = 1 … n gilt

A′x′ = ( \begin{matrix}Ax \\ y \end{matrix} )

und wir haben Ax berechnet. Dieses Vorgehen heißt aus naheliegenden Gründen “zero-padding”.

Beispiel: Wir betrachten ein Beispiel mit n = 3 und M = 6. Dann gilt

A = ( \begin{matrix}a_{0} & a_{1} & a_{2} \\ a_{−1} & a_{0} & a_{1} \\ a_{−2} & a_{−1} & a_{0} \end{matrix} )

und

A′ = ( \begin{matrix}a_{0} & a_{1} & a_{2} & 0 & a_{−2} & a_{−1} \\ a_{−1} & a_{0} & a_{1} & a_{2} & 0 & a_{−2} \\ a_{−2} & a_{−1} & a_{0} & a_{1} & a_{2} & 0 \\ 0 & a_{−2} & a_{−1} & a_{0} & a_{1} & a_{2} \\ a_{2} & 0 & a_{−2} & a_{−1} & a_{0} & a_{1} \\ a_{1} & a_{2} & 0 & a_{−2} & a_{−1} & a_{0} \end{matrix} ) .

Bemerkung: Wir haben insbesondere gezeigt, daß sich jede zyklische Faltung der Länge n auch als zyklische Faltung der Länge M mit M > n berechnen läßt. Daher beschränken sich viele Bibliotheken auf die Betrachtung von Faltungen z.B. der Länge 2^{p}.

Bemerkung: Fouriertransformationen von der Ordnung p^{n} mit p ≠ 2 prim lassen sich im wesentlichen als Faltungen schreiben. Der Satz liefert uns damit auch Verfahren zur schnellen Durchführung von Fouriertransformationen, wenn nur wenige Faltungsalgorithmen implementiert sind.

Bemerkung: Toeplitz–Matrizen tauchen zum Beispiel in der Computer– Tomographie auf. Es muß das Gleichungssystem Ax = b mit einer Toeplitz–Matrix A gelöst werden. Wir untersuchen daher jetzt den Aufwand zur Lösung dieses Gleichungssystems.

Satz 5.1.3 Sei A eine (n, n) Toeplitz–Matrix. Alle Hauptminoren von A seien ungleich null (z.B. A positiv definit). Dann kann das Gleichungssystem Ax = b mit \frac{13}{4}n^{2} + O(n) Operationen gelöst werden.

Beweis: Wir definieren eine Hierarchie von Matrizen A_{k} für k = −(n− 1) … (n − 1), A_{0} := A. Für k > 0 sind k Nebendiagonalen oberhalb der Hauptdiagonalen 0, für k < 0 sind k Nebendiagonalen unterhalb der Hauptdiagonalen 0. Es gilt also für k > 0

A_{k} = ( \begin{matrix}∗ & 0 & ⋯ & 0 & ∗ & ⋯ & ∗ \\ ⋮ & ... & ... & & ... & ... & ⋮ \\ ⋮ & & ... & ... & & ... & ∗ \\ ⋮ & & & ... & ... & & 0 \\ ⋮ & & & & ... & ... & ⋮ \\ ⋮ & & & & & ... & 0 \\ ∗ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ∗ \end{matrix} ) .

A_{−k} hat die transponierte Gestalt, aber nicht notwendig mit denselben Einträgen für die Elemente mit ∗.

Wir beschreiben den Algorithmus für n = 4, indem wir elementare Zeilenumformungen von A angeben, die A_{k} erzeugen. Wir starten mit der Matrix A = A_{0} und konstruieren A_{−1} und A_{1} gleichzeitig.

A_{0} = ( \begin{matrix}a_{0}^{0} & a_{1}^{0} & a_{2}^{0} & a_{3}^{0} \\ a_{−1}^{0} & a_{0}^{0} & a_{1}^{0} & a_{2}^{0} \\ a_{−2}^{0} & a_{−1}^{0} & a_{0}^{0} & a_{1}^{0} \\ a_{−3}^{0} & a_{−2}^{0} & a_{−1}^{0} & a_{0}^{0} \end{matrix} ) , A_{0} = ( \begin{matrix}a_{0}^{0} & a_{1}^{0} & a_{2}^{0} & a_{3}^{0} \\ a_{−1}^{0} & a_{0}^{0} & a_{1}^{0} & a_{2}^{0} \\ a_{−2}^{0} & a_{−1}^{0} & a_{0}^{0} & a_{1}^{0} \\ a_{−3}^{0} & a_{−2}^{0} & a_{−1}^{0} & a_{0}^{0} \end{matrix} ) .

Aus der linken Matrix konstruieren wir A_{−1}. Die oberste Zeile hat bereits die richtige Form. Für k > 1 ziehen wir von Zeile k das \frac{a_{−1}^{0}}{a_{0}^{0}} –fache der k −1. Zeile der rechten Matrix ab. In der rechten Matrix ziehen wir für k < n von Zeile k das \frac{a_{1}^{0}}{a_{0}^{0}} –fache der k + 1. Zeile der linken Matrix ab. Dadurch erhalten wir folgende Matrizen:

A_{−1} = ( \begin{matrix}a_{0}^{0} & a_{1}^{0} & a_{2}^{0} & a_{3}^{0} \\ 0 & a_{0}^{−1} & a_{1}^{−1} & a_{2}^{−1} \\ a_{−2}^{−1} & 0 & a_{0}^{−1} & a_{1}^{−1} \\ a_{−3}^{−1} & a_{−2}^{−1} & 0 & a_{0}^{−1} \end{matrix} ) , A_{1} = ( \begin{matrix}a_{0}^{1} & 0 & a_{2}^{1} & a_{3}^{1} \\ a_{−1}^{1} & a_{0}^{1} & 0 & a_{2}^{1} \\ a_{−2}^{1} & a_{−1}^{1} & a_{0}^{1} & 0 \\ a_{−3}^{0} & a_{−2}^{0} & a_{−1}^{0} & a_{0}^{0} \end{matrix} ) .

Die Operation ist durchführbar, denn a_{0}^{0} ist der erste Hauptminor der Matrix A und damit nicht Null. Zur Durchführung dieses Schritts müssen wir einmal dividieren und links und rechts 2n−2 Elemente neu berechnen. Da dieselbe Rechnung auch auf der rechten Seite (b) durchgeführt werden muß, benötigen wir insgesamt 2(3n−3) Rechenoperationen und eine Division.

Im nächsten Schritt bringen wir die nächste Diagonale auf Null. Man sieht schnell, daß dies nicht durch elementare Zeilenumformungen innerhalb der Matrizen möglich ist. Da wir aber wissen, daß gleichzeitig A_{−1}x = b_{−1} und A_{1}x = b_{1}, können wir auch Zeilen der rechten Matrix auf die linke addieren und umgekehrt. Für k ≤ 2 hat A_{−1} bereits die richtige Form. Für k > 2 addieren wir zu Zeile k der linken Matrix das \frac{a_{−2}^{−1}}{a_{0}^{1}} –fache der (k − 2). Zeile der rechten Matrix. Für k < n + 1 − 2

addieren wir zur Zeile k der rechten Matrix das \frac{a_{2}^{1}}{a_{0}^{−1}} –fache der (k + 2). Zeile der linken Matrix. Wir erhalten

A_{−2} = ( \begin{matrix}a_{0}^{0} & a_{1}^{0} & a_{2}^{0} & a_{3}^{0} \\ 0 & a_{0}^{−1} & a_{1}^{−1} & a_{2}^{−1} \\ 0 & 0 & a_{0}^{−2} & a_{1}^{−2} \\ a_{−3}^{−2} & 0 & 0 & a_{0}^{−2} \end{matrix} ) , A_{2} = ( \begin{matrix}a_{0}^{2} & 0 & 0 & a_{3}^{2} \\ a_{−1}^{2} & a_{0}^{2} & 0 & 0 \\ a_{−2}^{1} & a_{−1}^{1} & a_{0}^{1} & 0 \\ a_{−3}^{0} & a_{−2}^{0} & a_{−1}^{0} & a_{0}^{0} \end{matrix} ) .

Die Divisionen sind wieder ausführbar. Die obere linke (2, 2)-Teilmatrix von A_{1} ist durch elementare Zeilenumformungen aus der oberen linken (2, 2)-Teilmatrix von A hervorgegangen (genauer Beweis in den Aufgaben). Diese ist invertierbar, denn der zweite Hauptminor ist nicht Null, also ist a_{0}^{2} nicht Null. Der Rechenaufwand für diesen Schritt ist eine Division und 2(3n − 6) Operationen.

Wir beschreiben nun Schritt j. Seien also A_{j−1} und A_{−(j−1)} bereits berechnet. Addiere für j + 1 ≤ k ≤ n auf die k. Zeile der linken Matrix das \frac{a_{−j}^{−j+1}}{a_{0}^{j−1}} –fache der (k − j). Zeile der rechten Matrix. Addiere für 1 ≤

k ≤ n − j das \frac{a_{j}^{j−1}}{a_{0}^{−(j−1)}} –fache der (k + j). Zeile der linken Matrix auf die k. Zeile der rechten Matrix.

Der Aufwand zur Umformung einer Matrix und seiner rechten Seite beträgt damit 3(n−j) für Schritt j. Insgesamt erhalten wir einen Aufwand von

∑_{j=1}^{n−1} 2(3n − j) = 3n^{2} + O(n).

Wir müssen das Gleichungssystem nun noch lösen durch Rückwärtsund Vorwärtseinsetzen. Für die ersten \frac{n}{2} Variablen benutzen wir A_{−(n−1)} und Vorwärtseinsetzen, für den Rest A_{n−1} und Rückwärtseinsetzen, macht noch einmal 2\frac{1}{2} (\frac{n}{2})^{2} Operationen, insgesamt also 13\frac{n^{2}}{4} Rechenoperationen.

5.2 Der Algorithmus von Morf

Wir wollen den Begriff der Toeplitz–Matrix noch einmal verallgemeinern. Wir hatten oben bereits gesehen, daß für den Rang d der Matrix A − P^{t}AP einer Toeplitz–Matrix A immer d ≤ 2 gilt. Wir definieren den +– und −–Verschiebungsrang.

Definition 5.2.1 Sei M die (n, n)–Matrix (e_{2}, e_{3}, …, e_{n}, 0). Für eine (n, n)–Matrix A nennen wir

α_{+}(A) := rk(A − MAM^{t})
α_{−}(A) := rk(A − M^{t}AM)

den +– bzw. −–Verschiebungsrang von A.

Sei A = (a_{ik}), i = 1, …, n, k = 1, …, n. Dann ist

MAM^{t} = ( \begin{matrix}0 & 0 & ⋯ & 0 \\ 0 & a_{1,1} & ⋯ & a_{1,n−1} \\ ⋮ & ⋮ & & ⋮ \\ 0 & a_{n−1,1} & ⋯ & a_{n−1,n−1} \end{matrix} )

und

M^{t}AM = ( \begin{matrix}a_{2,2} & ⋯ & a_{2,n} & 0 \\ ⋮ & & ⋮ & ⋮ \\ a_{n,2} & ⋯ & a_{n,n} & 0 \\ 0 & ⋯ & 0 & 0 \end{matrix} )

Beispiel: Toeplitz–Matrizen haben den Veriebungsrang α_{+}(A) = α_{−}(A) ≤ 2.

Satz 5.2.2 Für invertierbare Matrizen gilt:

α_{+}(A) = α_{−}(A^{−1}).

Beweis: Wir zeigen zunächst den Hilfssatz:

Für beliebige (n, n)–Matrizen A und B gilt:

rk(I − AB) = rk(I − BA)

Beweis des Hilfssatzes: Sei (x_{1}, …, x_{m}) eine Basis des Kerns von (I − AB), und y_{i} := Bx_{i}. Die y_{i} sind linear unabhängig, denn sonst wären die Ay_{i} = ABx_{i} = x_{i} linear abhängig. Außerdem gilt

(I − BA)y_{i} = (I − BA)Bx_{i} = B(I − AB)x_{i} = 0

und die y_{i} sind im Kern von (I − BA) enthalten. Die Dimension des Kerns von (I − BA) ist also mindestens so groß wie die Dimension des Kerns von (I − AB) und es gilt

rk(I − BA) ≤ rk(I − AB).

Durch Vertauschen von A und B erhält man den Hilfssatz.

Beweis des Satzes:

α_{+}(A) = rk(I − MAM^{t})
= rk((I − MAM^{t}A^{−1})A)
= rk(I − MAM^{t}A^{−1})
= rk(I − M^{t}A^{−1}MA)  nach dem Hilfssatz
= rk(A^{−1} − M^{t}A^{−1}MAA^{−1})
= rk(A^{−1} − M^{t}A^{−1}M)
= α_{−}(A^{−1}).

Für unsere weiteren Betrachtungen ist fundamental, daß sich Matrizen mit kleinem Verschiebungsrang als Summe einfacher Matrizen darstellen lassen. Wir definieren zunächst die unteren und oberen Dreiecks– Toeplitz– Matrizen durch

Definition 5.2.3 Sei x ∈ C^{n}, x = (x_{i}), i = 0, …, n − 1. Dann definieren wir die zugehörige untere (n, n) Dreiecks–Toeplitz–Matrix durch

L(x)_{i,i−l} := \{ \begin{matrix}x_{l}, & l ≥ 0 \\ 0, & sonst \end{matrix} , also L(x) = ( \begin{matrix}x_{0} & & 0 \\ ⋮ & ... \\ x_{n−1} & ⋯ & x_{0} \end{matrix} )

und die zugehörige obere (n, n) Dreiecks–Toeplitz–Matrix durch

U(x) := L(x)^{t}.

Die Bezeichnungen U und L stehen natürlich für Upper und Lower.

Satz 5.2.4 Seien x^{j}, y^{j} ∈ C^{n}, j = 1, …, α, α > 0. Dann ist äquivalent:

1. A − MAM^{t} = ∑_{j=1}^{α} x^{j}(y^{j})^{t}

2. A = ∑_{j=1}^{α} L(x^{j})U(y^{j})

Beweis: Wir zeigen zunächst 2 ⇒ 1. Sei A = (a_{i,j}), i = 0, …, n−1, j = 0, …, n − 1. Dann gilt

a_{k,l} = ∑_{j=1}^{α} ∑_{i} L(x^{j})_{k,i}U(y^{j})_{i,l}

= ∑_{j=1}^{α} ∑_{i=0}^{n−1} x_{k−i}^{j}y_{l−i}^{j}

mit der Definition x_{i} = y_{i} = 0 für i < 0. Wir definieren weiter a_{k,l} = 0 für k < 1 oder l < 1. Dann gilt

(A − MAM^{t})_{k,l} = a_{k,l} − a_{k−1,l−1}
= ∑_{j=1}^{α} ∑_{i=0}^{n−1} x_{k−i}^{j}y_{l−i}^{j} − x_{k−1−i}^{j}y_{l−1−i}^{j}
= ∑_{j=1}^{α} x_{k}^{j}y_{l}^{j}
= ∑_{j=1}^{α}(x^{j}(y^{j})^{t})_{k,l}

und A − MAM^{t} = ∑_{j=1}^{α} x^{j}(y^{j})^{t}.

Die umgekehrte Richtung folgt sofort (Übungen).

Satz 5.2.5 Zu jeder (n, n) Matrix A gibt es Vektoren x^{j}, y^{j}, j = 1, …, α_{+}(A), und Vektoren x̃^{j}, ỹ^{j}, j = 1, …, α_{−}(A), so daß

A = ∑_{j=1}^{α_{+}(A)} L(x^{j})U(y^{j}) und A = ∑_{j=1}^{α_{−}(A)} U(ỹ^{j})L(x̃^{j}).

Beweis: Für die Matrix B := A − MAM^{t} vom Rang α_{+}(A) gibt es Vektoren x_{0}, …, x_{k−1} und y_{0}, …, y_{k−1} mit

B = ∑_{j=1}^{α} x^{j}(y^{j})^{t}.

Nach Satz (??) folgt die Behauptung für A − MAM^{t}.

Satz 5.2.6 Seien A, B (n, n)–Matrizen mit festem von n unabhängigem Verschiebungsrang α = α_{+}(A). Dann kann man die LU-Zerlegung von AB mit n log n Operationen berechnen.

Beweis:

1. Die LU-Zerlegung von A kann nach dem Beweis von Satz ?? in O(n) berechnet werden. (Anmerkung: Mit hoher Wahrscheinlichkeit? nachfragen!) Das Bestimmen der l.u. Vektoren kann O(n^{2}) Operationen kosten.

2. Das Produkt von unteren oder oberen Toeplitz–Dreiecksmatrizen ist O(n log n). Beweis der Zwischenbehauptung:

(L(x)L(y))_{kl} = ∑_{i=l}^{k} x_{k−i}y_{i−l}, k ≥ l

= ∑_{j=0}^{k−l} x_{j}y_{k−l−j} =: z_{i}

Die z_{i} können durch schnelle Faltungen berechnet werden in Zeit O(n log n).

3. Sei U eine obere, L eine untere Dreiecks–Toeplitz–Matrix. Dann kann man in O(n) untere bzw. obere Dreiecks–Toeplitz–Matrizen L_{i}, U_{i} berechnen mit

UL = ∑_{i=1}^{3} L_{i}U_{i}

Beweis: Erweitere U und L wie im Beweis zu Satz ?? zu zyklischen Faltungen der Länge 2n. Die Matrizen Ũ und L̃ haben dann die Form

Ũ = ( \begin{matrix}Ũ & L̃_{1}L \\ L̃_{2} & Ũ_{3} \end{matrix} ) , L̃ = ( \begin{matrix}L & Ũ_{1} \\ Ũ_{2} & L̃_{3} \end{matrix} ) , ŨL̃ = ( \begin{matrix}UL + L̃_{1}Ũ_{1} & ∗ \\ ∗ & ∗ \end{matrix} ) .

Das Produkt dieser zyklischen Faltung ist wieder eine zyklische Faltung. Also ist es mit O(n log n) Operationen berechenbar. Außerdem ist die Matrix LU − U_{1}L_{1} Toeplitz, also LU − U_{1}L_{1} = ∑_{U_{i}L_{i}}, und die Zerlegung ist in O(n) berechenbar.

Wir setzen diese Ergebnisse nun zusammen. Gesucht sei das Produkt von A und B. Nach i) gilt

A = ∑_{i=1}^{α} L_{i}U_{i}, B = ∑_{i=1}^{α} L̃_{i}Ũ_{i}.

Damit gilt

AB = ∑_{i,j=1}^{α} L_{i}U_{i}L̃_{j}U_{j}.

Nach Punkt iii) finden wir Matrizen mit

U_{i}L̃_{j} = ∑_{k=1}^{3} L_{k}^{i,j}U_{k}^{i,j}

und

AB = ∑_{i,j,k=1}^{3} L_{i}L_{k}^{i,j}U_{k}^{i,j}Ũ_{j} = ∑_{j=1}^{3α^{2}} L̂_{l}Û_{l}.

Nach einem Satz ist die Multiplikation von Matrizen ungefähr so aufwendig wie die Inversion. Wir erwarten also, daß es einen schnellen Algorithmus auch zur Inversion von Matrizen mit kleinem Verschiebungsrang gibt.

Sei nun

A = ( \begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} )

mit (\frac{n}{2}, \frac{n}{2})-Matrizen A_{i,k}. In Lemma 2.3 zum Strassen– Algorithmus wurde diese Matrix bereits invertiert. Zur Blockinversion sind einige Produkte von Matrizen A_{i,k} und die Inversen der Matrizen A_{1,1} und A_{2,2}−A_{2,1}A_{1,1}^{−1}A_{1,2} zu berechnen. Wenn wir zeigen können, daß alle diese Matrizen kleinen Verschiebungsrang haben, können wir einen schnellen Algorithmus definieren.

Satz 5.2.7 Sei A (n, n)–Matrix mit n = 2m wie oben aufgeteilt. Dann gilt:

• α_{+}(A_{1,1}) ≤ α_{+}(A).

• α_{−}(A_{2,2}) ≤ α_{−}(A).

• α_{+}(A_{2,2}) ≤ α_{+}(A) + 2.

• α_{+}(A_{1,2}) ≤ α_{+}(A) + 1.

• α_{+}(A_{2,1}) ≤ α_{+}(A) + 1.

• α_{+}(A_{2,2} − A_{2,1}A_{1,1}^{−1}A_{1,2}) ≤ α_{+}(A).

Beweis: Sei A = ∑ L_{i}U_{i}. Spalte L_{i} und U_{i} auf wie A in Matrizen

L_{j} = ( \begin{matrix}L_{j}^{1,1} & 0 \\ L_{j}^{2,1} & L_{j}^{2,2} \end{matrix} ) , U_{j} = ( \begin{matrix}U_{j}^{1,1} & U_{j}^{1,2} \\ 0 & U_{j}^{2,2} \end{matrix} ) , L_{j}U_{j} = ( \begin{matrix}L_{j}^{1,1}U_{j}^{1,1} & L_{j}^{1,1}U_{j}^{1,2} \\ L_{j}^{2,1}U_{j}^{1,1} & L_{j}^{2,1}U_{j}^{1,2} + L_{j}^{2,2}U_{j}^{2,2} \end{matrix} )

mit Dreiecks–Toeplitz–Matrizen L_{j}^{1,1}, U_{j}^{1,1}, L_{j}^{2,2} und U_{j}^{2,2} sowie mit Toeplitz–Matrizen L_{j}^{2,1} und U_{j}^{1,2}. Es gilt A = ∑_{j=1}^{α_{+}(A)} L_{j}U_{j}. Aus dieser Darstellung folgt Punkt 1. Aus der entsprechenden UL- Darstellung folgt Punkt 2 und hieraus Punkt 3. Die Toeplitz–Matrizen kann man als Summe von Dreiecks–Toeplitz–Matrizen schreiben. Hieraus folgen 4 und 5. Die Matrix in Punkt 6 ist untere Teilmatrix von A^{−1}, also gilt

α_{+}(A_{2,2} − A_{2,1}A_{1,1}^{−1}A_{1,2}) = α_{−}(C_{2,2}) ≤ α_{−}(A^{−1}) ≤ α_{+}(A).

Satz 5.2.8 Die Inversion einer Matrix mit festem, von n unabhängigem Verschiebungsrang α kann mit O(n(log n)^{2}) Operationen durchgeführt werden.

Beweis: Seien T (n) die benötigten Operationen zur Inversion einer (n, n)–Matrix. Dann gilt T (n) = 2T (n/2) + O(n log n). Nach Satz 1.1 der Vorlesung gilt damit auch T (n) = O(n(log n)^{2}).

Literaturverzeichnis

[1] Baum, U.: Existenz und effiziente Konstruktion schneller Fouriertransformationen auf überauflösbaren Gruppen, Dissertation Bonn 1991.

[2] Beth, T.: Verfahren der schnellen Fourier-Transformation, Teubner Studienbücher, Informatik, 1984, ISBN 3-519-02363-6.

[3] Brigham, Oran E.: FFT Schnelle Fourier-Transformation, R. Oldenbourg Verlag München Wien 1987, 3. verbesserte Aufl., ISBN 3-486-20347-9.

[4] Elliott, Douglas F.and K. Ramamohan Rao: FAST TRANS-FORMS Algorithms, Analysis, Applications, Academic Press, Inc., 1982, ISBN 0-12-237080-5.

[5] Knuth, D.E.: The Art of Computer Programming, Vol. 2, Addison-Wesley 1969.

[6] Van Loan, Charles: Computational Frameworks for the Fast Fourier Transform, SIAM FRONTIERS in Applied Mathematics, Philadelphia 1992, ISBN 0-89871-285-8.

[7] Mehlhorn, K.: Effiziente Algorithmen, Teubner Verlag 1977.

[8] Meinel, C.: Effiziente Algorithmen, Fachbuchverlag Leipzig, 1991.

[9] Müller, W.: Darstellungstheorie von endlichen Gruppen, Teubner Verlag 1980.

[10] Nussbaumer, H.J.: Fast Fourier Transform and Convolution Algorithms, Springer 1982.

[11] Pan, V.Ya.: Methods of Computing Values of Polynomials, Russian Math. Surveys 21, 105-136 (1966).

[12] Quinn, M.J.: Designing Efficient Algorithms for Parallel Computer, McGraw-Hill 1987.

[13] Fässler, A. and E. Stiefel.: Group Theoretical Methods and Its Applications, Birkhäuser Verlag 1992.

[14] Stiefel, E. und A. Fässler: Gruppentheoretische Methoden und ihre Anwendung, Teubner Studienbücher, Mathematik, Bd. 46, 1979.ISBN 3-519-02348-2.

[15] Winograd, S.: Arithmetic Complexity of Computations, SIAM, Philadelphia 1980.