Algebraische Komplexitätstheorie II

Schnelle Matrixmultiplikation und Kombinatorik

Peter Bürgisser, Universität Zürich

Dies ist die Ausarbeitung des zweiten Vortrags unserer Reihe, in dem die bilineare Komplexität, ein Teilgebiet der algebraischen Komplexitätstheorie, näher vorgestellt wurde. Sie hat ihren Ursprung in Strassens erstaunlicher Entdeckung aus dem Jahre 1969, wonach Gausselimination kein optimaler Algorithmus zur Lösung zahlreicher Berechnungsprobleme der linearen Algebra ist. Dieses Ergebnis wirkte damals äusserst stimulierend: die Optimalität verschiedenster Berechnungsverfahren, über die man sich bis anhin kaum systematisch Gedanken gemacht hatte, war damit in Frage gestellt. Tatsächlich wurden in einer stürmischen Entwicklung in der ersten Hälfte der 70er Jahre viele neue, überraschend schnelle Algorithmen gefunden. Parallel dazu entdeckte man die ersten unteren Schranken und Optimalitätsbeweise. Das Problem der Matrixmultiplikation erwies sich jedoch als besonders hartnäckig: es vergingen 9 Jahre bis Strassens Algorithmus durch Pan [9] erstmals verbessert wurde. Mittlerweile hat man ein deutlich tieferes Verständnis des Problems gewonnen. Es ist das Ziel dieses Vortrags, einige der Resultate zu präsentieren, sowie die Ideen und Methoden zu skizzieren, die zu den neuesten Fortschritten in diesem Gebiet geführt haben. Wie der Titel erahnen lässt, spielten kombinatorische Methoden bei den jüngsten Fortschritten eine erhebliche Rolle.

1 Der Exponent

Das der Definition folgende Verfahren zur Multiplikation zweier n-reihiger Matrizen über einem Köper k benötigt Grössenordnung n^{3} arithmetische Ope-

\begin{matrix}( \begin{matrix}c_{11} & c_{12} \\ c_{21} & c_{22} \end{matrix} ) = ( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} ) · ( \begin{matrix}b_{11} & b_{12} \\ b_{21} & b_{22} \end{matrix} ) \\ \begin{aligned}p_{1} & = & (a_{12} − a_{22}) · (b_{21} + b_{22}) \\ p_{2} & = & (a_{11} + a_{22}) · (b_{11} + b_{22}) \\ p_{3} & = & (a_{11} − a_{21}) · (b_{11} + b_{12}) \\ p_{4} & = & (a_{11} + a_{12}) · b_{22} \\ p_{5} & = & a_{11} · (b_{12} − b_{22}) \\ p_{6} & = & a_{22} · (b_{21} − b_{11}) \\ p_{7} & = & (a_{21} + a_{22}) · b_{11} \end{aligned} & \begin{aligned}c_{11} & = & p_{1} + p_{2} − p_{4} + p_{6} \\ c_{12} & = & p_{4} + p_{5} \\ c_{21} & = & p_{6} + p_{7} \\ c_{22} & = & p_{2} − p_{3} + p_{5} − p_{7} \end{aligned} \end{matrix}

Abbildung 1: Strassens Algorithmus für die Multiplikation zweireihiger Matrizen.

rationen. Bekanntlich ist dies keineswegs optimal: Strassen [11] entdeckte im Jahre 1969, dass Grössenordnung n^{2.81} Operationen ausreichen! Der Entwurf seines Algorithmus verwendet Argumente, die bei der Untersuchung der Komplexität der Matrixmultiplikation in abgewandelter Form immer wieder vorkommen. Wir beginnen deshalb mit einer Beschreibung von Strassens Algorithmus.

Im ersten Schritt wird ein Verfahren zur Multiplikation von zweireihigen Matrizen entwickelt, das gegenüber dem gewöhnlichen Vorgehen eine Multiplikation auf Kosten von einigen Additionen oder Subtraktionen einspart. Dies geschieht mittels der Formeln in Abb. 1, die hier etwas vom Himmel fallen. (Man kann diese übrigens mit darstellungstheoretischen Argumenten herleiten [5].) Nebenbei sei auch erwähnt, dass man nicht mit weniger als 7 Multiplikationen auskommen kann.

Diese bescheiden anmutende Einsparung einer Multiplikation entfaltet ihre volle Wirkung erst zusammen mit der Idee der Rekursion. Die Multiplikation von 2^{N}-reihigen Matrizen kann via Blockzerlegung als Multiplikation zweireihiger Matrizen über dem Ring der 2^{N−1}-reihigen Matrizen aufgefasst werden. Das oben beschriebene Verfahren zur zweireihigen Matrixmultiplikation funktioniert jedoch über einem beliebigen, nicht notwendig kommutativen Ring! Also bekommt man ein rekursives Verfahren mit einem Aufwand T (n), n = 2^{N}, das folgender Rekursionsgleichung genügt

T (n) ≤ 7 · T (n/2) + 18(n/2)^{2},

was die Abschätzung T (n) ≤ 7 n^{log_{2} 7} ≤ 7 n^{2.81} impliziert. Bemerkenswert ist die Tatsache, dass die Anzahl Additionen und Subtraktionen durch die Anzahl Multiplikationen dominiert wird: Wenn Strassens Verfahren zur zweireihigen Matrixmultiplikation 100 statt 18 Additionen verwendete, so erhielte man trotzdem T (n) = O(n^{2.81}).

Man definiert nun den sogenannten Exponenten ω der Matrixmultiplikation über k als das Infimum aller Exponenten τ, sodass sich n-reihige Matrizen mit Aufwand O(n^{τ}) multiplizieren lassen. (Man kann zeigen, dass der Exponent höchstens von der Charakteristik des Grundkörpers k abhängt [10].)

Wir haben gerade gesehen, dass ω < 2.81 ist. Ausserdem sieht man leicht, dass ω mindestens zwei sein muss. Dies ist aber auch die einzige untere Schranke für ω, die man kennt!

Die beste bekannte obere Schranke für den Exponenten ist ω < 2.38. Dieses Ergebnis aus dem Jahre 1987 wurde von Coppersmith und Winograd [7, 8] erzielt. Deren bemerkenswerter Beweis basiert auf einer von Strassen [13] entwickelten Technik, die von ihm Lasermethode genannt wurde. Das Kernstück in der Argumentation von Coppersmith und Winograds ist ein nichtkonstruktiver Existenzbeweis für eine kombinatorische Struktur, der mittels der probabilistischen Methode geführt wird. Es ist eines der Ziele dieses Vortrags, Ihnen die Hauptideen einer geglätteten und vereinfachten Version dieses Beweises zu erklären; für Details verweisen wir auf Kapitel 15 unseres Buchs [4]. Wir möchten auch nicht verschweigen, dass Coppersmith und Winograds Algorithmus von rein theoretischem Interesse ist, weil sich der asymptotische Gewinn erst bei astronomischen Matrixformaten bemerkbar machen würde.

Bevor wir weiterfahren, motivieren wir die Definition des Exponenten noch etwas weiter. Eine genaue Bestimmung des Aufwands der Matrixmultiplikation liegt weit ausserhalb der Reichweite der heutigen, bekannten Methoden. Sogar für die Multiplikation dreireihiger Matrizen ist die multiplikative Komplexität nicht genau bekannt! Es ist deshalb naheliegend, sich auf asymptotische Aussagen zu beschränken.

Die Subroutine Matrixmultiplikation wird von fast allen Algorithmen der linearen Algebra benutzt, so z.B. für die Berechnung der Determinante, des charakteristischen Polynoms, für Matrixinversion und für die Lösung linearer Gleichungssysteme. Man kann zeigen, dass schnelle Algorithmen für die Matrixmultiplikation schnelle Algorithmen für alle obigen Probleme liefern. Aber auch die Umkehrung gilt! Zum Beispiel kann man zeigen, dass sich jeder Algorithmus zur Determinantenberechnung in einen nicht viel langsameren zur Multiplikation von Matrizen transformieren lässt [1]. Insgesamt gilt, dass all diese Probleme die gleiche asymptotische Berechnungskomplexität wie die Matrixmultiplikation haben. Deshalb beschreibt der Exponent ω die asymptotische Komplexität vieler Berechnungsprobleme der linearen Algebra.

2 Rang von Tensoren

Wir entwickeln hier einen formalen Rahmen, um die Komplexität der Matrixmultiplikation und allgemeinerer bilinearer Abbildungen zu diskutieren.

Ein (Koordinaten-) Tensor t über k ist definiert als ein Element des Tensorprodukts dreier endlichdimensionaler (Koordinaten-) Vektorräume

t = (t_{ijℓ})_{i,j,ℓ} ∈ k^{m×n×p} ≃ k^{m} ⊗ k^{n} ⊗ k^{p},

den man sich am besten als eine dreidimensionale m × n × p-Matrix vorstellt. Eine Triade ist ein Tensor der Gestalt

u ⊗ v ⊗ w := (u_{i}v_{j}w_{ℓ})_{i,j,ℓ},

wobei u ∈ k^{m}, v ∈ k^{n}, w ∈ k^{p}. Man definiert nun den Rang R(t) eines Tensors t als die minimiale Anzahl Triaden, sodass sich der Tensor als Summe von diesen schreiben lässt:

R(t) := min {r ∈ ℕ | ∃u_{ρ} ∈ k^{m}, v_{ρ} ∈ k^{n}, w_{ρ} ∈ k^{p} :
t = ∑_{ρ=1}^{r} u_{ρ} ⊗ v_{ρ} ⊗ w_{ρ}}.

Im Spezialfall p = 1, wenn also t eine Matrix ist, stimmt diese Grösse mit dem Matrixrang überein.

Wir stellen nun den Bezug zur Komplexität her. Eine bilineare Abbildung

φ : k^{m} × k^{n} → k^{p}, φ_{ℓ}(x, y) = ∑_{i,j} t_{ijℓ}x_{i}y_{j}

korrespondiert in bijektiver Weise mit ihrem Koordinatentensor t = (t_{ijℓ}). Unter der multiplikativen Komplexität von φ verstehen wir die Ostrowski-Komplexität L(φ_{1}(x, y), …, φ_{p}(x, y)), wobei hier die x_{i}, y_{j} als Unbestimmte über k interpretiert werden (vgl. den ersten Vortrag).

Es gilt nun das folgende wichtige Ergebnis.

Satz 1 (Strassen [12]) Die multiplikative Komplexität der bilinearen Abbildung φ unterscheidet sich vom Rang R(t) ihres Koordinatentensors t um höchstens den Faktor zwei.

Aufgrund dieses Resultats kann man sich – zumindest für asymptotische Untersuchungen – auf den Rang konzentrieren. Die Definition des Rangs ist mathematisch so klar und einfach, dass man versucht ist zu denken, dass mit obigem Satz die Hauptarbeit geleistet ist. Der Schein trügt! Es zeigte sich, dass die Bestimmung des Rangs eines konkreten Tensors – im Unterschied zum Matrixrang – ein sehr schwieriges Problem ist.

Es seien t ∈ k^{m} ⊗ k^{n} ⊗ k^{p} und t′ ∈ k^{m′} ⊗ k^{n′} ⊗ k^{p′} zwei Tensoren. Wir nennen t und t′ isomorph, t ≃ t′, falls es lineare Isomorphismen α: k^{m} → k^{m′}, β: k^{n} → k^{n′}, γ: k^{p} → k^{p′} gibt, sodass t′ = (α ⊗ β ⊗ γ)(t). In naheliegender Weise definieren wir die direkte Summe t ⊕ t′ ∈ k^{m+m′} ⊗ k^{n+n′} ⊗ k^{p+p′} von t und t′:

(t ⊕ t′)_{ijℓ} := \{ \begin{matrix}t_{ijℓ} & falls i ≤ m_{1}, j ≤ n_{1}, ℓ ≤ p_{1}, \\ t′_{i−m_{1},j−n_{1},ℓ−p_{1}} & falls i > m_{1}, j > n_{1}, ℓ > p_{1}, \\ 0 & sonst. \end{matrix}

Das Tensorprodukt t ⊗ t′ ∈ k^{m×m′} ⊗ k^{n×n′} ⊗ k^{p×p′} von t und t′ wird erklärt durch

(t ⊗ t′)_{(i,i′)(j,j′)(ℓ,ℓ′)} := t_{ijℓ} t′_{i′j′ℓ′}.

Die Rangfunktion verhält sich bezüglich dieser Bildungen angenehm, denn sie ist subadditiv und submultiplikativ

R(t ⊕ t′) ≤ R(t) + R(t′),
R(t ⊗ t′) ≤ R(t) R(t′),

sowie invariant unter Isomorphie.

Wir bezeichnen in der Folge den Tensor der Matrixmultiplikation

k^{e×h} × k^{h×ℓ} → k^{e×ℓ}, (A, B) ↦ AB

mit ⟨e, h, ℓ⟩. Man kann sich leicht überlegen, dass

⟨e, h, ℓ⟩ = ∑_{i,j,m} u_{ij} ⊗ v_{jm} ⊗ w_{mi} ∈ k^{e×h} ⊗ k^{h×ℓ} ⊗ k^{ℓ×e},

wo u_{ij}, v_{jm}, bzw. w_{mi} die kanonischen Basisvektoren von k^{e×h}, k^{h×ℓ}, bzw. k^{ℓ×e} bezeichnen. Die Tatsache, dass sich die Multiplikation hh′-reihiger Matrizen via Blockzerlegung zurückführen lässt auf die Multiplikation h-reihiger Matrizen, deren Einträge h′-reihige Matrizen sind, führt auf die folgende fundamentale Beziehung

⟨e, h, ℓ⟩ ⊗ ⟨e′, h′, ℓ′⟩ ≃ ⟨ee′, ℓℓ′, hh′⟩.

Insbesondere ist das Tensorprodukt von Matrixtensoren wieder ein Matrixtensor.

Wir können nun die frühere Überlegung, welche ω < 2.81 lieferte, mit unseren formalen Begriffen so beschreiben: R(⟨2, 2, 2⟩) ≤ 7 impliziert

R(⟨2^{m}, 2^{m}, 2^{m}⟩) = R(⟨2, 2, 2⟩^{⊗m}) ≤ 7^{m} ≤ (2^{m})^{log_{2} 7},

was ω < log_{2} 7 oder 2^{ω} ≤ 7 liefert.

Diese Überlegung lässt sich verallgemeinern zu

R(⟨e, h, ℓ⟩) ≤ r ⟹ (ehℓ)^{ω/3} ≤ r.  (1)

Jeder Algorithmus, um Matrizen von speziellem Format zu multiplizieren, führt also auf Algorithmen, um Matrizen von beliebigem Format zu multiplizieren und damit zu einer oberen Schranke für den Exponenten.

3 Grenzrang

Ein signifikanter Schritt im Unterfangen, obere Schranken für den Exponenten zu gewinnen, ist das Konzept des Grenzrangs, welches durch Bini, Capovani, Lotti und Romani [3] eingeführt wurde. Ausgangspunkt war die Beobachtung, dass es, etwa über ℂ, Tensoren gibt, die sich mit beliebiger Genauigkeit durch Tensoren kleineren Rangs approximieren lassen.

Die algebraische Definition des Grenzrangs lautet so:

Definition 2 Sei t ∈ k^{m×n×p} und ϵ eine Unbestimmte über k. Der Grenzrang \underline{R}(t) von t ist die kleinste natürliche Zahl r ∈ ℕ, für die ein Tensor t_{1} ∈ k[ϵ]^{m×n×p} existiert so, dass R(t + ϵt_{1}) ≤ r. (Hierbei wird t + ϵt_{1} als ein Tensor über dem rationalen Funktionenkörper k(ϵ) interpretiert.)

Um sich diese Definition zu veranschaulichen, stellt man sich ϵ am besten als ein bezüglich k infinitesimales Element vor. Dann hat ein Tensor einen Grenzrang kleiner als r genau dann, wenn eine infinitesimale Störung dieses Tensors einen Rang kleiner als r hat. Wir bemerken noch, dass man den Grenzrang über algebraisch abgeschlossenen Körpern k auch mit Hilfe der Zariski-Topologie charakterisieren kann (vgl. etwa [4, Chap. 20]). Genauso wie der Rang ist auch der Grenzrang subadditiv, submultiplikativ und invariant unter Isomorphie.

Das folgende Bild zeigt einen 2×2×2-Tensor vom Rang drei, dessen Grenzrang zwei ist.

1

1 ϵ^{2}

t = e_{000} + e_{011} + e_{101} ∈ k^{2×2×2}
R(t) = 3, aber
\underline{R}(t) ≤ 2, weil
R(t + ϵ^{2}e_{110}) ≤ 2

Bini, Capovani, Lotti und Romani [3, 2] zeigten nun mit einer direkten Konstruktion \underline{R}(⟨3, 2, 2⟩ ≤ 10. Ausserdem bewiesen sie, dass die Implikation (1) auch für den Grenzrang gilt, woraus sie die Abschätzung ω < 2.78 folgerten. Die Idee ist dabei, grob gesprochen, aus einem gegebenen “approximativen Algorithmus” für ein spezielles Matrixformat zunächst via Tensorproduktbildung approximative Algorithmen für beliebig grosse Formate zu konstruieren, woraus man dann mittels Interpolation exakte Algorithmen gewinnt. Der für die Interpolation zusätzlich benötigte Aufwand ist asymptotisch vernachlässigbar.

Eines der wichtigsten Werkzeuge, um effiziente Algorithmen für die Matrixmultiplikation zu entwickeln, ist die Entdeckung von Schönhage, dass sich die Implikation (1) auf direkte Summen übertragen lässt.

Satz 3 (Asymptotische Summenungleichung, Schönhage [10])

\underline{R}(⨁_{i=1}^{s}⟨e_{i}, h_{i}, ℓ_{i}⟩) ≤ r ⟹ ∑_{i=1}^{s}(e_{i}h_{i}ℓ_{i})^{ω/3} ≤ r.

Wäre der Grenzrang additiv, so würde sich dies als eine unmittelbare Folgerung aus dem Ergebnis von Bini, Capovani, Lotti und Romani ergeben. Leider ist dem aber nicht so, wie Schönhage in derselben Arbeit nachwies.

Die asymptotische Summenungleichung besagt, etwas ungenau, in Worten:

Jeder Algorithmus, um simultan mehrere unabhängige Matrixmultiplikationen von speziellem Format “approximativ” durchzuführen, führt auf Algorithmen, um Matrizen von beliebigem Format zu multiplizieren und damit zu einer oberen Schranke für den Exponenten.

Schönhage gab folgende Anwendung: er zeigte

\underline{R}(⟨4, 1, 4⟩ ⊕ ⟨1, 9, 1⟩) ≤ 17,

woraus er mit der asymptotischen Summenungleichung zu der Abschätzung ω < 2.55 gelangte.

4 Kombinatorische Degeneration

Bevor wir Strassens [13] Strategie der Lasermethode erklären können, müssen wir noch weitere Begriffe definieren.

Gegeben sei ein Tensor t ∈ U ⊗ V ⊗ W bei dem die Vektorräume U, V, W die folgenden endlichen direkten Summenzerlegungen aufweisen:

D : U = ⨁_{i∈I} U_{i}, V = ⨁_{j∈J} V_{j}, W = ⨁_{ℓ∈L} W_{ℓ}

(I, J, L sind endliche Indexmengen). Dann bekommt man eine eindeutige Zerlegung

t = ∑_{(i,j,ℓ)∈I×J×L} t(i, j, ℓ)

in die sogenannten D-Komponenten t(i, j, ℓ) ∈ U_{i} ⊗ V_{j} ⊗ W_{ℓ} von t. Die Teilmenge

supp_{D}t := {(i, j, ℓ) ∈ I × J × L | t(i, j, ℓ) ≠ 0}

des kombinatorischen Würfels I × J × L nennt man den D-Träger von t. Es ist hilfreich, sich unter D eine Blockzerlegung des Tensors t vorzustellen: die D-Komponenten beschreiben, was in den einzelnen Blöcken steht, und der D-Träger gibt die grobe Struktur wieder (cf. Abb. 2). Eine Teilmenge Δ eines kombinatorischen Würfels I × J × L heisst Diagonale, wenn die Projektionen Δ → I, Δ → J, Δ → L injektiv sind. Die Bedeutung der Diagonalen rührt von folgender Beziehung her:

∑_{(i,j,ℓ)∈Δ} t(i, j, ℓ) ≃ ⨁_{(i,j,ℓ)∈Δ} t(i, j, ℓ).

Wir definieren nun den Begriff der kombinatorischen Degeneration für Teilmengen eines kombinatorischen Würfels.

Definition 4 Sei Φ ⊆ I × J × L. Eine Teilmenge Ψ von Φ heisst (kombinatorische) Degeneration von Φ, Ψ ⊴ Φ, falls Funktionen a: I → ℤ, b: J → ℤ, c: L → ℤ existieren mit der Eigenschaft, dass

∀(i, j, ℓ) ∈ Ψ : a(i) + b(j) + c(ℓ) = 0
∀(i, j, ℓ) ∈ Φ \ Ψ : a(i) + b(j) + c(ℓ) > 0.

[figure: i; ℓ; j; t(i,j,ℓ); supp_{D}t; I={1,2}, J={1,2,3}, L={1,2}]

Abbildung 2: Blockzerlegung eines Tensors

In Abb. 3 wird dieser Begriff an zwei 2-dimensionalen Beispielen illustriert. Im linken Bild wird ein (kombinatorisches) Quadrat durch eine Diagonale in zwei Dreiecke zerlegt. Diese Diagonale ist eine Degeneration beider Dreiecke. Rechts sieht man, dass der Mittelpunkt dieser Diagonale als deren Degeneration erhalten werden kann.

Der Bezug der kombinatorischen Degeneration zum Grenzrang wird durch die folgende Aussage hergestellt.

Proposition 5 Es sei t ein Tensor mit Blockzerlegung D und Ψ ⊴ supp_{D}t. Dann gilt \underline{R}( ∑_{(i,j,ℓ)∈Ψ} t(i, j, ℓ)) ≤ \underline{R}(t).

Zum Beweis erwähnen wir nur, dass ∑_{Ψ} t(i, j, ℓ) aufgrund der Voraussetzung Ψ ⊴ supp_{D}t als eine torische Degeneration von t interpretiert werden kann, woraus die Behauptung leicht folgt.

Abbildung 3: Zwei zweidimensionale Beispiele für kombinatorische Degenerationen

[figure: 0; n; n; i; j; Φ; Ψ; 0; n; n; i; j; n/\sqrt{2}; Φ; Ψ]
Ψ ⊴ Φ

\underbrace{i}_{a(i)} + \underbrace{(j − n)}_{b(j)} ≥ 0 auf Φ

Gleichheit auf Ψ

Ψ ⊴ Φ

\underbrace{i^{2}}_{a(i)} + \underbrace{(j^{2} − n^{2}/2)}_{b(j)} ≥ 0 auf Φ

Gleichheit auf Ψ

Wir haben nun die nötigen Hilfsmittel zusammengestellt, um die Strategie der sogenannten Lasermethode zu erläutern. Angenommen, wir haben einen Tensor t mit Blockzerlegung D mit folgenden Eigenschaften:

1. alle D-Komponenten sind Matrixtensoren,

2. eine “grosse” Diagonale Δ ist Degeneration von supp_{D}t,

3. wir kennen eine (gute) obere Schranke r für den Grenzrang von t.

Dann können wir aufgrund von Proposition 5 schliessen, dass

\underline{R}( ⨁_{(i,j,ℓ)∈Δ} t(i, j, ℓ)) ≤ \underline{R}(t) ≤ r.

Jetzt lässt sich die asymptotische Summenungleichung anwenden und wir erhalten eine Abschätzung für den Exponenten.

5 Abschätzung des Exponenten

Das Hauptergebnis dieses Abschnittes ist rein kombinatorischer Natur und liefert eine quantitative Aussage über die Grösse von Diagonalen, die sich aus gewissen Teilmengen von kombinatorischen Würfeln herausdegenerieren lassen. Damit lässt sich die zweite Bedingung der im letzten Abschnitt erläuterten Strategie erfüllen.

Für ein positive natürliche Zahl b setzen wir I_{b} := {−b, −b + 1, …, b} ⊆ ℤ und T_{b} := {(x, y, z) ∈ I_{b}^{3} | x + y + z = 0} ⊆ ℤ^{3}.

Definition 6 Φ ⊆ I × J × L heisst b-straff, falls es ein r ≥ 1 und injektive Abbildungen α: I → ℤ^{r}, β: J → ℤ^{r}, γ: L → ℤ^{r} gibt so, dass

(α, β, γ)(Φ) ⊆ (T_{b})^{r}.

Eine Teilmenge Φ ⊆ I × J × L ist also b-straff, wenn sie sich unter Erhaltung der Produktstruktur injektiv in ein Produkt von T_{b}’s einbetten lässt.

Der nächste Satz beinhaltet die Kernaussage der Methode, die wir hier beschreiben. Sein Beweis geht auf Coppersmith und Winograd [7, 8] zurück. Die vorliegende geglättete und vereinfachte Variante verdanken wir Strassen [14, 15, 16]. Der Beweis ist ein schönes Beispiel für die Mächtigkeit der probabilistischen Methode in der Kombinatorik.

Satz 7 Sei Φ ⊆ I × J × L b-straff und etwa |I| ≤ |J| ≤ |L|. Dann existiert eine Diagonale Δ in Φ mit Kardinalität

|Δ| ≥ \frac{1}{K} min\{|I|, |J|, |L|\},

welche Degeneration von Φ ist. Hierbei ist K das 13.5-fache des Maximums von

\frac{|I|}{|Φ|} max_{i∈I} |p_{I}^{−1}(i)|, \frac{|J|}{|Φ|} max_{j∈J} |p_{J}^{−1}(j)|, \frac{|L|}{|Φ|} max_{ℓ∈L} |p_{L}^{−1}(ℓ)|, \frac{4}{9}(2b + 1)\frac{|I|}{|Φ|}

und p_{I}: Φ → I, p_{J}: Φ → J, p_{L}: Φ → L bezeichnet die Projektionen, welche als surjektiv vorausgesetzt werden.

Wir skizzieren hier den Beweis nur in sehr groben Zügen und verweisen für Details auf [4, Chap. 15].

Wir wählen eine Primzahl M, bezeichnen den endlichen Körper ℤ/Mℤ mit 𝔽_{M} und setzen

Ψ_{M} := {(x, y, z) ∈ 𝔽_{M}^{3} | x + y + z = 0}.

Ausserdem sei φ: 𝔽_{M}^{r} → 𝔽_{M} eine lineare Abbildung. Wir betrachten nun das Diagramm

I × J × L ↪^{(α,β,γ)} ℤ^{r} × ℤ^{r} × ℤ^{r} → 𝔽_{M}^{r} × 𝔽_{M}^{r} × 𝔽_{M}^{r} →^{(φ,φ,φ)} 𝔽_{M}^{3}
↑  ↑  ↑  ↑
Φ  →  (T_{b})^{r}  →  (Ψ_{M})^{r}  → Ψ_{M}

Die Komposition der unteren drei Abbildungen heisse F_{φ}. Wenn wir M genügend gross wählen, ist die Komposition von (α, β, γ) mit der Restklassenabbildung ℤ^{r} × ℤ^{r} × ℤ^{r} → 𝔽_{M}^{r} × 𝔽_{M}^{r} × 𝔽_{M}^{r} injektiv.

Mit einer direkten Konstruktion kann man leicht eine Diagonale D ⊴ Ψ_{M} gewinnen mit |D| ≥ M/2. Durch Zurückziehen sieht man, dass F_{φ}^{−1}(D) Degeneration von Φ ist. Wir schreiben F_{φ}^{−1}(D) als Vereinigung seiner Fasern

F_{φ}^{−1}(D) = F_{φ}^{−1}(d_{1}) ∪ F_{φ}^{−1}(d_{2}) ∪ …

und degenerieren mit einem weiteren direkten Verfahren jede Faser F_{φ}^{−1}(d_{i}) zu einer Diagonale Δ_{φ}^{i}: Δ_{φ}^{i} ⊴ F_{φ}^{−1}(d_{i}). Weil D diagonal ist, müssen die Fasern F_{φ}^{−1}(d_{i}) in Würfeln mit paarweise disjunkten Kanten liegen. Daraus erhält man, dass Δ_{φ} := Δ_{φ}^{1}∪Δ_{φ}^{2}∪… auch diagonal und ausserdem eine Degeneration von Φ ist.

Nun kommt der Clou! Wir wählen die lineare Abbildung φ: 𝔽_{M}^{r} → 𝔽_{M} zufällig, womit die Kardinalität |Δ_{φ}| eine Zufallsvariable wird, deren Erwartungswert abgeschätzt werden kann. (Strenggenommen arbeitet man mit einer kleinen Modifikation von α, β, γ, um stochastische Unabhängigkeit zu garantieren.) Man wählt dann die Primzahl M so, dass

E(|Δ_{φ}|) ≥ \frac{1}{K} min\{|I|, |J|, |L|\}.

Daraus folgt, dass es mindestens ein φ gibt, für das |Δ_{φ}| die gewünschte Grösse hat.

Nun können wir diesen Satz mit unserer Strategie kombinieren. Wir wählen einen Tensor t mit einer Blockzerlegung D so, dass alle D-Komponenten Matrixtensoren sind und mit der Eigenschaft, dass der D-Träger straff ist. Dann erhalten wir aus der asymptotischen Summenungleichung eine Abschätzung für den Exponenten. Wir können diese noch verbessern, indem wir das Verfahren auf eine hohe Tensorpotenz t^{⊗N} mit der zugehörigen Blockzerlegung anwenden. Auf diese Art kann man folgendes zeigen:

Korollar 8 (Coppersmith and Winograd [7]) ω < 2.38.

Obwohl seit 1987 keine besseren Abschätzungen für den Exponenten gefunden wurden, ist hier das letzte Wort sicherlich noch nicht gesprochen.

Die vergebliche Suche nach nichttrivialen unteren Schranken für den Exponenten, sowie die massiven Verbesserungen bei den oberen Schranken lassen die Vermutung zu, dass der Exponent ω zwei sein könnte. Diese Vermutung wird gestützt durch das folgende Resultat von Coppersmith [6]

R(⟨h, h, ⌊h^{0.17}⌋⟩) = O(h^{2} log^{2} h).

Demnach lassen sich eine quadratische h-reihige und eine rechteckige h×h^{0.17}- Matrix mit einem Aufwand multiplizieren, der beinahe linear in der Inputgrösse h^{2} ist.

Ich möchte den Vortrag mit der Frage schliessen, ob tatsächlich ω = 2 ist. Dies ist sicher eine der zentralen offenen Probleme der algebraischen Komplexitätstheorie.

Literatur

[1] W. Baur and V. Strassen. The complexity of partial derivatives. Theoret. Comp. Sc., 22:317–330, 1983.

[2] D. Bini. Relation between exact and approximate bilinear algorithms. Applications. Calcolo, 17:87–97, 1980.

[3] D. Bini, M. Capovani, G. Lotti, and F. Romani. O(n^{2.7799}) complexity for matrix multiplication. Inf. Proc. Letters, 8:234–235, 1979.

[4] P. Bürgisser, M. Clausen, and M.A. Shokrollahi. Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften, Bd. 315. Springer Verlag, 1996.

[5] M. Clausen. Beiträge zum Entwurf schneller Spektraltransformationen. Habilitationsschrift, Universität Karlsruhe, 1988.

[6] D. Coppersmith. Rapid multiplication of rectangular matrices. SIAM J. Comp., 11:467–471, 1982.

[7] D. Coppersmith and S. Winograd. Matrix multiplications via arithmetic progression. In Proc. 19th ACM STOC, pages 1–6, 1987.

[8] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comp., 9:251–280, 1990.

[9] V.Ya. Pan. Field extension and trilinear aggregating, uniting and cancelling for the acceleration of matrix multiplication. In Proc. of the 20th Ann. IEEE Symp. on Foundations of Comp. Sc., pages 28–38, 1979.

[10] A. Schönhage. Partial and total matrix multiplication. SIAM J. Comp., 10:434–455, 1981.

[11] V. Strassen. Gaussian elimination is not optimal. Num. Math., 13:354– 356, 1969.

[12] V. Strassen. Vermeidung von Divisionen. Crelles J. Reine Angew. Math., 264:184–202, 1973.

[13] V. Strassen. Relative bilinear complexity and matrix multiplication. Crelles J. Reine Angew. Math., 375/376:406–443, 1987.

[14] V. Strassen. The asymptotic spectrum of tensors. Crelles J. Reine Angew. Math., 384:102–152, 1988.

[15] V. Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. Crelles J. Reine Angew. Math., 413:127–180, 1991.

[16] V. Strassen. Private Mitteilung, 1995.