\documentclass[12pt,twoside]{article}
\usepackage{amssymb}
\usepackage[german]{babel}
\usepackage{epic}
\usepackage{latexsym}

\pagestyle{myheadings}
\markboth{}{{\sc S\'eminaire Lotharingien de Combinatoire} {\rm S36b (16pp.)}}
\parindent=0pt
\parskip=1em
\setlength{\textwidth}{14cm}

\newtheorem{theorem}{Satz}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Korollar}
\newtheorem{definition}[theorem]{Definition}

\newcommand{\br}{\underline{R}}
\newcommand{\supp}{{\rm supp}\,}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\FF}{{\mathbb F}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\CC}{{\mathbb C}}
\newcommand{\ds}{\displaystyle}

\begin{document}
%\bibliographystyle{plain}
\phantom{...}
\vspace{.2cm}
\begin{center}
{\Large\bf Algebraische Komplexit\"atstheorie II}
\end{center}
\begin{center}
{\Large\bf Schnelle Matrixmultiplikation\\ und Kombinatorik }
\end{center}
\begin{center}
{\sc Peter B\"urgisser, Universit\"at Z\"urich}
\end{center}


\vspace{1cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Dies ist die Ausarbeitung des zweiten Vortrags unserer Reihe, 
in dem die bilineare Komplexit\"at, ein Teilgebiet der 
algebraischen Komplexit\"atstheorie, n\"aher vorgestellt wurde.
Sie hat ihren Ursprung in Strassens erstaunlicher 
Entdeckung aus dem Jahre 1969, wonach Gausselimination kein optimaler 
Algorithmus zur L\"osung zahlreicher Berechnungsprobleme 
der linearen Algebra ist. 
Dieses Ergebnis wirkte damals \"ausserst stimulierend: 
die Optimalit\"at verschiedenster Berechnungsverfahren,
\"uber die man sich bis anhin kaum systematisch Gedanken
gemacht hatte, war damit in Frage gestellt. 
Tats\"achlich wurden in einer st\"urmischen Entwicklung 
in der ersten H\"alfte der 70er Jahre viele neue, 
\"uberraschend schnelle Algorithmen gefunden. 
Parallel dazu entdeckte man die ersten unteren Schranken und 
Optimalit\"atsbeweise.
Das Problem der Matrixmultiplikation erwies sich jedoch 
als besonders hartn\"ackig: 
es vergingen 9 Jahre bis Strassens Algorithmus durch Pan~\cite{vpan:79} 
erstmals verbessert wurde. 
Mittlerweile hat man ein deutlich tieferes 
Verst\"andnis des Problems gewonnen. Es ist 
das Ziel dieses Vortrags, einige der Resultate zu 
pr\"asentieren, sowie die Ideen und Methoden zu skizzieren,
die zu den neuesten Fortschritten in diesem Gebiet gef\"uhrt haben. 
Wie der Titel erahnen l\"asst, spielten 
kombinatorische Methoden bei den j\"ungsten Fortschritten 
eine erhebliche Rolle.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\markboth{\hfill P.~B\"urgisser  \hfill}%
{\hfill Algebraische Komplexit\"atstheorie II \hfill}


\section{Der Exponent}

Das der Definition folgende Verfahren 
zur Multiplikation zweier $n$-reihiger Matrizen \"uber einem K\"oper $k$ 
ben\"otigt Gr\"ossenordnung $n^3$ arithmetische Operationen.
Bekanntlich ist dies keineswegs optimal: 
Strassen~\cite{stra:69} entdeckte im Jahre 1969, dass Gr\"ossenordnung 
$n^{2.81}$ Operationen ausreichen! Der Entwurf seines Algorithmus 
verwendet Argumente, die bei der Untersuchung der Komplexit\"at 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\"uber 
dem gew\"ohnlichen Vorgehen {\em 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 
\"ubrigens mit darstellungstheoretischen Argumenten 
herleiten~\cite{clau:88}.)
Nebenbei sei auch erw\"ahnt, dass man nicht 
mit weniger als $7$ Multiplikationen auskommen kann. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\hrulefill\ 
$$
\begin{array}{c}
\left(\begin{array}{cc} c_{11}&c_{12}\\ c_{21}&c_{22} \end{array}\right) =
\left(\begin{array}{cc} a_{11}&a_{12}\\ a_{21}&a_{22}\end{array}\right) \cdot
\left(\begin{array}{cc} b_{11}&b_{12}\\ b_{21}&b_{22} \end{array}\right)
\\[6ex]
\begin{array}{cc}
\begin{array}{lll}
p_1 &=& (a_{12}-a_{22})\cdot (b_{21}+b_{22}) \\
p_2 &=& (a_{11}+a_{22})\cdot (b_{11}+b_{22}) \\
p_3 &=& (a_{11}-a_{21})\cdot (b_{11}+b_{12}) \\
p_4 &=& (a_{11}+a_{12})\cdot b_{22} \\
p_5 &=& a_{11} \cdot (b_{12}-b_{22}) \\
p_6 &=& a_{22} \cdot (b_{21}-b_{11}) \\
p_7 &=& (a_{21}+a_{22})\cdot b_{11}
\end{array}
&
\begin{array}{lll}
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{array}
\end{array}\\[4ex]
\end{array}
$$
%
\caption{Strassens Algorithmus f\"ur die Multiplikation zweireihiger Matrizen.}
\hrulefill\ 
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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 
\"uber dem Ring der $2^{N-1}$-reihigen Matrizen aufgefasst werden. 
Das oben beschriebene Verfahren zur zweireihigen Matrixmultiplikation
funktioniert jedoch \"uber einem beliebigen, nicht notwendig kommutativen 
Ring! Also bekommt man ein rekursives Verfahren
mit einem Aufwand $T(n)$, $n=2^N$, das folgender Rekursionsgleichung gen\"ugt
$$
 T(n) \le  7 \cdot T(n/2) + 18 (n/2)^2,
$$
was die Absch\"atzung 
$T(n) \le 7\, n^{\log_2 7} \le 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 {\em Exponenten} $\omega$ der 
Matrixmultiplikation \"uber $k$ als das Infimum aller Exponenten 
$\tau$, sodass sich $n$-reihige Matrizen mit Aufwand $O(n^\tau)$ 
multiplizieren lassen.
(Man kann zeigen, dass der Exponent h\"ochstens von der
Charakteristik des Grundk\"orpers $k$ abh\"angt~\cite{scho:81}.) 

Wir haben gerade gesehen, dass $\omega < 2.81$ ist. Ausserdem sieht 
man leicht, dass $\omega$ mindestens zwei sein muss. Dies ist aber 
auch die einzige untere Schranke f\"ur $\omega$, die man kennt! 

Die beste bekannte obere Schranke f\"ur den Exponenten ist
$\omega < 2.38$. Dieses Ergebnis aus dem Jahre 1987 wurde von 
Coppersmith und Winograd~\cite{cowi:87,cowi:90} erzielt. 
Deren bemerkenswerter Beweis 
basiert auf einer von Strassen~\cite{stra:87} entwickelten Technik, die von 
ihm {\em Lasermethode} genannt wurde. Das Kernst\"uck in 
der Argumentation von Coppersmith und Winograds ist ein nichtkonstruktiver 
Existenzbeweis f\"ur eine kombinatorische Struktur, der mittels der 
probabilistischen Methode gef\"uhrt wird. 
Es ist eines der Ziele dieses Vortrags, 
Ihnen die Hauptideen einer gegl\"atteten und vereinfachten Version
dieses Beweises zu erkl\"aren; f\"ur Details verweisen wir auf 
Kapitel~15 unseres Buchs~\cite{bucs:96}. Wir m\"ochten 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\"urde. 


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\"ur die Multiplikation 
dreireihiger Matrizen ist die multiplikative Komplexit\"at nicht 
genau bekannt! Es ist deshalb naheliegend, sich auf asymptotische 
Aussagen zu beschr\"anken.

Die Subroutine Matrixmultiplikation wird von fast allen Algorithmen
der linearen Algebra benutzt, so z.B.\ f\"ur die Berechnung der 
Determinante, des charakteristischen Polynoms, f\"ur Matrixinversion und 
f\"ur die L\"osung linearer Gleichungssysteme.
Man kann zeigen, dass schnelle Algorithmen f\"ur die Matrixmultiplikation 
schnelle Algorithmen f\"ur 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\"asst~\cite{bast:83}. 
Insgesamt gilt, dass all diese Probleme die gleiche asymptotische 
Berechnungskomplexit\"at wie die Matrixmultiplikation haben.
Deshalb beschreibt der Exponent $\omega$ die asymptotische 
Komplexit\"at vieler Berechnungsprobleme der linearen Algebra. 


\section{Rang von Tensoren} 

Wir entwickeln hier einen formalen Rahmen, 
um die Komplexit\"at der Matrixmultiplikation und allgemeinerer 
bilinearer Abbildungen zu diskutieren. 

Ein {\em (Koordinaten-) Tensor} $t$ \"uber $k$ ist definiert als ein Element 
des Tensorprodukts dreier endlichdimensionaler (Koordinaten-) Vektorr\"aume
$$
  t = (t_{ij\ell})_{i,j,\ell} \in k^{m\times n \times p} \simeq
      k^m\otimes k^n\otimes k^p, 
$$
den man sich am besten als eine dreidimensionale 
$m\times n\times p$-Matrix vorstellt.
Eine {\em Triade} ist ein Tensor der Gestalt 
$$ 
  u\otimes v\otimes w :=(u_i v_j w_\ell)_{i,j,\ell},
$$
wobei $u \in k^m$, $v \in k^n$, $w \in k^p$.
Man definiert nun den {\em Rang $R(t)$} eines Tensors~$t$ als 
die minimiale Anzahl Triaden, sodass sich der Tensor als Summe von 
diesen schreiben l\"asst:
\begin{eqnarray*}
 R(t) := \min \big\{ r\in \NN &\mid& \exists u_\rho \in k^m,\, 
               v_\rho\in k^n, \, w_\rho\in k^p :\\
     & & \mbox{$t = \sum_{\rho=1}^r u_\rho\otimes 
           v_\rho\otimes w_\rho$} \big\} .
\end{eqnarray*}
Im Spezialfall $p=1$, wenn also $t$ eine Matrix ist, 
stimmt diese Gr\"osse mit dem Matrixrang \"uberein. 

Wir stellen nun den Bezug zur Komplexit\"at her.  
Eine bilineare Abbildung
$$
 \varphi : k^m \times k^n \to k^p,\ 
\varphi_\ell(x,y) =\sum_{i,j}t_{i j \ell} x_i y_j
$$
korrespondiert in bijektiver Weise mit ihrem Koordinatentensor 
$t=(t_{i j \ell})$. 
Unter der {\em multiplikativen Komplexit\"at} von $\varphi$ verstehen wir 
die Ostrowski-Komplexit\"at 
$L(\varphi_1(x,y),\ldots,\varphi_p(x,y))$, wobei hier die 
$x_i,y_j$ als Unbestimmte \"uber $k$ interpretiert werden
(vgl.\ den ersten Vortrag).  

Es gilt nun das folgende wichtige Ergebnis.

\begin{theorem}[Strassen~\cite{stra:73-1}]
Die multiplikative Komplexit\"at der bilinearen Abbildung $\varphi$ 
unterscheidet sich vom Rang $R(t)$ ihres Koordinatentensors $t$ 
um h\"och\-stens den Faktor zwei.
\end{theorem}

Aufgrund dieses Resultats kann man sich -- zumindest f\"ur 
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\"ugt! Es zeigte sich, dass die Bestimmung 
des Rangs eines konkreten Tensors  -- im Unterschied zum Matrixrang -- 
ein sehr schwieriges Problem ist.

Es seien $t\in k^m\otimes k^n\otimes k^p$ und 
$t'\in k^{m'}\otimes k^{n'}\otimes k^{p'}$ zwei Tensoren. 
Wir nennen $t$ und $t'$ {\em isomorph}, $t\simeq t'$, falls es 
lineare Isomorphismen 
$\alpha\colon k^m \to k^{m'}$, $\beta\colon k^n \to k^{n'}$, 
$\gamma\colon k^p \to k^{p'}$ gibt, sodass 
$t' = (\alpha\otimes\beta\otimes\gamma)(t)$. 
In naheliegender Weise definieren wir die {\em direkte Summe} 
$t\oplus t' \in k^{m+m'}\otimes k^{n+n'}\otimes k^{p+p'}$ 
von $t$ und $t'$: 
$$
 (t \oplus t')_{ij\ell} := \left\{
 \begin{array}{ll}
 t_{ij\ell} & \mbox{falls $i\le m_1,\, j\le n_1,\, \ell \le p_1$,}\\
 t'_{i-m_1,j-n_1,\ell -p_1} & \mbox{falls $i> m_1,\, j> n_1,\, \ell > p_1$,}\\
 0 & \mbox{sonst.}
 \end{array} \right.
$$

Das {\em Tensorprodukt} 
$t\otimes t'\in k^{m\times m'}\otimes k^{n\times n'}\otimes k^{p\times p'}$
von $t$ und $t'$ wird erkl\"art durch 
$$
  (t\otimes t')_{(i,i')(j,j')(\ell,\ell')} := t_{ij\ell}\, t'_{i'j'\ell'} .
$$

Die Rangfunktion verh\"alt sich bez\"uglich dieser Bildungen angenehm, 
denn sie ist {\em subadditiv} und {\em submultiplikativ} 
\begin{eqnarray*}
 R(t\oplus t') &\le & R(t) + R(t'), \\
 R(t\otimes t') &\le & R(t)\, R(t'),
\end{eqnarray*}
sowie invariant unter Isomorphie.

Wir bezeichnen in der Folge den Tensor der Matrixmultiplikation
$$
 k^{e\times h} \times k^{h\times \ell} \to k^{e\times \ell},\,
 (A,B) \mapsto A B
$$
mit $\langle e,h,\ell \rangle$. Man kann sich leicht \"uberlegen, dass 
$$
 \langle e,h,\ell \rangle = 
   \sum_{i,j,m} u_{ij}\otimes v_{jm}\otimes w_{mi}
  \in  k^{e\times h} \otimes k^{h\times \ell} \otimes k^{\ell\times e} ,
$$
wo $u_{ij}$, $v_{jm}$, bzw.\ $w_{mi}$ die kanonischen Basisvektoren 
von $k^{e\times h}$, $k^{h\times \ell}$, bzw.\ $k^{\ell\times e}$ 
bezeichnen. 
Die Tatsache, dass sich die Multiplikation $h h'$-reihiger 
Matrizen via Blockzerlegung zur\"uckf\"uhren l\"asst auf die  
Multiplikation $h$-reihiger
Matrizen, deren Eintr\"age $ h'$-reihige Matrizen sind, f\"uhrt auf die 
folgende fundamentale Beziehung
$$
\langle e,h,\ell \rangle \otimes \langle e',h',\ell' \rangle \simeq 
\langle ee',\ell\ell', hh' \rangle .
$$
Insbesondere ist das Tensorprodukt von Matrixtensoren wieder ein Matrixtensor. 

Wir k\"onnen nun die fr\"uhere \"Uberlegung, welche $\omega <2.81$ lieferte,
mit unseren formalen Begriffen so beschreiben: 
$R(\langle 2,2,2 \rangle) \le 7$ impliziert
$$
    R(\langle 2^m,2^m,2^m \rangle) = R(\langle 2,2,2 \rangle^{\otimes m})
    \le 7^m \le (2^m)^{\log_2 7},
$$
was $\omega < \log_2 7$ oder $2^\omega \le 7$ liefert.   

Diese \"Uberlegung l\"asst sich verallgemeinern zu
\begin{equation}\label{mini-t}
 R(\langle e,h,\ell \rangle) \le r \Longrightarrow 
 (eh\ell)^{\omega/3} \le r .
\end{equation}
Jeder Algorithmus, um Matrizen von speziellem Format zu multiplizieren, 
f\"uhrt also auf Algorithmen, um Matrizen von beliebigem Format zu 
multiplizieren und damit zu einer oberen Schranke f\"ur den Exponenten.


\section{Grenzrang}

Ein signifikanter Schritt im Unterfangen, obere Schranken f\"ur den Exponenten 
zu gewinnen, ist das Konzept des Grenzrangs, welches durch 
Bini, Capovani, Lotti und Romani~\cite{bclr:79} eingef\"uhrt wurde.
Ausgangspunkt war die Beobachtung, dass es, etwa \"uber $\CC$,  
Tensoren gibt, die sich mit beliebiger Genauigkeit durch Tensoren 
kleineren Rangs approximieren lassen. 

Die algebraische Definition des Grenzrangs lautet so: 

\begin{definition}
Sei $t \in k^{m\times n\times p}$ und $\epsilon$ eine Unbestimmte 
\"uber $k$. Der {\em Grenzrang} $\br(t)$ von $t$ ist die kleinste 
nat\"urliche Zahl $r\in \NN$, f\"ur die ein Tensor 
$t_1 \in k[\epsilon]^{m\times n\times p}$ 
existiert so, dass $R(t+\epsilon t_1)\le r$. 
(Hierbei wird $t+\epsilon t_1$ als ein Tensor \"uber dem rationalen 
Funktionenk\"orper $k(\epsilon)$ interpretiert.)
\end{definition}

Um sich diese Definition zu veranschaulichen, stellt man sich 
$\epsilon$ am besten als ein bez\"uglich $k$ infinitesimales
Element vor. Dann hat 
ein Tensor einen Grenzrang kleiner als $r$ genau dann, wenn eine 
infinitesimale St\"orung dieses Tensors einen Rang kleiner als $r$ hat. 
Wir bemerken noch, dass man den Grenzrang \"uber algebraisch abgeschlossenen 
K\"orpern $k$ auch mit Hilfe der Zariski-Topologie charakterisieren 
kann (vgl.\ etwa \cite[Chap.~20]{bucs:96}). 
Genauso wie der Rang ist auch der Grenzrang 
subadditiv, submultiplikativ und invariant unter Isomorphie.

Das folgende Bild zeigt einen $2\times 2\times 2$-Tensor 
vom Rang drei, dessen Grenzrang zwei ist. 
\begin{figure}[h]
\begin{center}
%\input ex_degen.epic 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
%\begin{picture}(5000,1539)(0,-10)
\begin{picture}(5000,2000)(0,-10)
\drawline(237,1212)(1137,912)(1737,1212)(1737,312)
\drawline(1737,312)(1737,312)
\drawline(1137,12)(12,387)
\drawline(135.329,377.513)(12.000,387.000)(116.355,320.592)
\drawline(237,312)(237,1212)
\drawline(237,1212)(837,1512)(1737,1212)
\dashline{60.000}(237,312)(837,612)(1737,312)
\dashline{60.000}(837,612)(837,1512)
\drawline(1137,1212)(1137,1212)
\drawline(1137,12)(1137,1212)
\drawline(1167.000,1092.000)(1137.000,1212.000)(1107.000,1092.000)
\drawline(1137,12)(1962,387)
\drawline(1865.170,310.033)(1962.000,387.000)(1840.342,364.655)
\put(1012,152){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$1$}}}}}
\put(337,887){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$1$}}}}}
\put(1587,837){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}1}}}}}
\put(850,642){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$\epsilon^2$}}}}}
\put(2700,800){
\begin{tabular}{l}
$t=e_{000}+e_{011}+e_{101} \in k^{2\times 2\times 2}$ \\[0.5ex]
$R(t) =3$,  aber \\[0.5ex] 
$\br(t)\le 2$, weil \\[0.7ex] 
$R(t +\epsilon^2 e_{110})\le 2$
\end{tabular}}
\end{picture}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{center}
\end{figure}


Bini, Capovani, Lotti und Romani~\cite{bclr:79,bini:80-1} 
zeigten nun mit einer direkten Konstruktion
$\br(\langle 3,2,2\rangle \le 10$. Ausserdem bewiesen sie, dass 
die Implikation~(\ref{mini-t}) auch f\"ur den Grenzrang gilt, 
woraus sie die Absch\"atzung $\omega < 2.78$ folgerten. 
Die Idee ist dabei, grob gesprochen, 
aus einem gegebenen ``approximativen Algorithmus'' f\"ur ein spezielles
Matrixformat zun\"achst via Tensorproduktbildung approximative 
Algorithmen f\"ur beliebig grosse Formate zu konstruieren, woraus man 
dann mittels Interpolation exakte Algorithmen 
gewinnt. Der f\"ur die Interpolation zus\"atzlich ben\"otigte Aufwand 
ist asymptotisch vernach\-l\"assigbar. 

Eines der wichtigsten Werkzeuge, um effiziente 
Algorithmen f\"ur die Matrixmultiplikation zu entwickeln, ist die Entdeckung 
von Sch\"onhage, dass sich die 
Implikation~(\ref{mini-t}) auf direkte Summen \"ubertragen l\"asst. 

\begin{theorem}[Asymptotische Summenungleichung, Sch\"onhage~\cite{scho:81}]
$$
\br \Bigl( \bigoplus_{i=1}^s \langle e_i,h_i,\ell_i\rangle \Bigr) \le r 
\Longrightarrow 
\sum_{i=1}^s (e_i h_i \ell_i)^{\omega/3} \le r .
$$
\end{theorem}

W\"are der Grenzrang additiv, so w\"urde sich dies als 
eine unmittelbare Folgerung aus dem Ergebnis von 
Bini, Capovani, Lotti und Romani ergeben. Leider ist dem aber
nicht so, wie Sch\"onhage in derselben Arbeit nachwies.

Die asymptotische Summenungleichung besagt, etwas ungenau, in Worten:
\begin{quotation}\noindent
 {\em Jeder Algorithmus, um simultan mehrere unabh\"angige 
Matrixmultiplikationen von speziellem Format ``approximativ'' 
durchzuf\"uhren, f\"uhrt auf Algorithmen, 
um Matrizen von beliebigem Format zu multiplizieren und damit 
zu einer oberen Schranke f\"ur den Exponenten.}
\end{quotation}

Sch\"onhage gab folgende Anwendung: er zeigte 
$$
 \br (\langle 4,1,4\rangle \oplus \langle 1,9,1\rangle) \le 17,
$$
woraus er mit der asymptotischen Summenungleichung zu der Absch\"atzung
$\omega < 2.55$ gelangte. 


\section{Kombinatorische Degeneration}

Bevor wir Strassens~\cite{stra:87} Strategie der Lasermethode erkl\"aren 
k\"onnen, m\"ussen wir noch weitere Begriffe definieren.

Gegeben sei ein Tensor $t \in U \otimes V \otimes W$ bei dem
die Vektorr\"aume $U,V,W$ die folgenden endlichen direkten Summenzerlegungen
aufweisen:
$$
 D: \hspace{3mm} U=\bigoplus_{i \in I}U_i, \;\;
    V=\bigoplus_{j \in J} V_j , \;\; W =\bigoplus_{\ell \in L} W_\ell 
$$
($I,J,L$ sind endliche  Indexmengen).
Dann bekommt man eine eindeutige Zerlegung 
$$
 t= \sum_{(i,j,\ell) \in I \times J \times L} t(i,j,\ell) 
$$
in die sogenannten {\em $D$-Komponenten} 
$t(i,j,\ell) \in U_i \otimes V_j \otimes W_\ell$
von $t$. Die Teilmenge
$$
 \supp_D t := \{(i,j,\ell) \in I \times J \times L \mid  t(i,j,\ell) \ne
 0\} 
$$
des {\em kombinatorischen W\"urfels} $I \times J \times L$
nennt man den {\em $D$-Tr\"ager} von $t$. 
%
\begin{figure}[h]
\hrulefill\ 
\begin{center}
\begin{tabular}{cc}\\[0.5ex]
%\input decomp_left.epic 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{
\setlength{\unitlength}{0.0015in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(2000,1800)(-1100,-450)
\thicklines
% Boxen
\drawline(0,0)(0,200)
\drawline(250,100)(250,500)
\drawline(500,400)(500,600)
\drawline(0,0)(250,100)
\drawline(0,200)(500,400)
\drawline(250,500)(500,600)
% 
\drawline(0,0)(-200,70)
\drawline(0,200)(-400,340)
\drawline(-200,470)(-600,610)
\drawline(-200,70)(-200,470)
\drawline(-400,340)(-400,740)
\drawline(-600,610)(-600,810)
%
\drawline(-200,270)(50,370)(250,300)
\drawline(-200,470)(300,670)(500,600)
\drawline(-400,740)(100,940)
\drawline(-400,540)(-150,640)(50,570)
%
\drawline(50,370)(50,770)(-350,910)(-600,810)
\drawline(-600,810)(-350,910)
\drawline(-600,810)(-400,740)
\drawline(-150,840)(-150,640)
\drawline(50,570)(250,500)
\drawline(300,870)(50,770)
\drawline(300,870)(100,940)
\drawline(300,870)(300,670)
%%
\thinlines
% Umrandung
\drawline(0,0)(500,200)
\drawline(0,0)(0,600)
\drawline(0,0)(-600,210)
\drawline(500,800)(500,200)
\drawline(500,800)(0,600)
\drawline(500,800)(-100,1010)
\drawline(-600,810)(-600,210)
\drawline(-600,810)(0,600)
\drawline(-600,810)(-100,1010)
%
\drawline(0,0)(650,260)
\drawline(596,250)(650,260)
\drawline(604,230)(650,260)
\put(750,270){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle i}$}}}}}
%
\drawline(0,0)(0,1100)
\drawline(-10,1080)(0,1100)
\drawline(10,1080)(0,1100)
\put(0,1150){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle \ell}$}}}}}
%
\drawline(0,0)(-760,266)
\drawline(-743.5,249)(-760,266)
\drawline(-736.5,269)(-760,266)
\put(-860,286){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle j}$}}}}}
%
\drawline(-600,960)(-400,760)
\drawline(-400,760)(-436,764)
\drawline(-400,760)(-404,796)
\put(-750,1000){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle t(i,j,\ell)}$}}}}}
\end{picture}
}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
& 
%\input decomp_right.epic 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\unitlength}{0.0009in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(2294,1863)(0,-400)
\put(1062,1011){\circle*{150}}
\put(612,1386){\circle*{150}}
\put(237,1236){\circle*{150}}
\put(537,936){\circle*{150}}
\put(837,561){\circle*{150}}
\drawline(12,1536)(12,636)(912,336)
	(912,1236)(12,1536)
\drawline(912,336)(1362,636)(1362,1536)(912,1236)
\drawline(1362,1536)(462,1836)(12,1536)
\put(1387,1736){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle {\mathrm supp}_D t}$}}}}}
\put(12,36){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle I=\{1,2\},\, J=\{1,2,3\},\, L=\{1,2\}}$}}}}}
\end{picture}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{tabular}
\caption{Blockzerlegung eines Tensors}
\end{center}
\hrulefill\ 
\end{figure}
%
Es ist hilfreich, sich unter $D$ eine {\em Blockzerlegung} des Tensors $t$ 
vorzustellen: die $D$-Komponenten beschreiben, was in den einzelnen 
Bl\"ocken steht, 
und der $D$-Tr\"ager gibt die grobe Struktur wieder 
(cf.\ Abb.~2).
Eine Teilmenge $\Delta$ eines kombinatorischen W\"urfels $I \times J \times L$
heisst {\em Diagonale}, wenn die Projektionen 
$\Delta \to I$, $\Delta \to J$, $\Delta \to L$ 
injektiv sind. 
Die Bedeutung der Diagonalen r\"uhrt von folgender Beziehung her:
$$
     \sum_{(i,j,\ell) \in \Delta} t(i,j,\ell) \: \simeq 
     \bigoplus_{(i,j,\ell) \in \Delta} t(i,j,\ell) .
$$

Wir definieren nun den Begriff der kombinatorischen Degeneration 
f\"ur Teilmengen eines kombinatorischen W\"urfels.

\begin{definition}
Sei $\Phi\subseteq I\times J\times L$. 
Eine Teilmenge $\Psi$ von $\Phi$ 
heisst {\em (kombinatorische) Degeneration} von $\Phi$, 
 $\Psi \unlhd \Phi$, falls Funktionen
 $a\colon I\to\ZZ$, $b\colon J\to \ZZ$, $c\colon L\to \ZZ$
 existieren mit der Eigenschaft, dass
 \begin{eqnarray*}
 \forall (i,j,\ell) \in \Psi &\colon& a(i)+b(j)+c(\ell) =0 \\
 \forall (i,j,\ell) \in \Phi\setminus \Psi &\colon& 
      a(i)+b(j)+c(\ell) > 0.
 \end{eqnarray*}
\end{definition}
%
\begin{figure}[h]
\hrulefill\ 
\caption{Zwei zweidimensionale Beispiele f\"ur kombinatorische Degenerationen}
\begin{center}
\begin{tabular}{cc}\\[0.5ex]
%\input degen_left.epic 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(2146,2286)(0,-10)
\thinlines
\drawline(1725,1752)(1725,1752)
\drawline(225,1752)(1725,1752)(1725,252)
\drawline(525,1752)(525,1452)
\drawline(825,1752)(825,1152)
\drawline(1425,1752)(1425,552)
\drawline(1125,1752)(1125,852)
\drawline(675,1752)(675,1302)
\drawline(375,1752)(375,1602)
\drawline(975,1752)(975,1002)
\drawline(1575,1752)(1575,402)
\drawline(1275,1752)(1275,702)
\thicklines
\drawline(225,1752)(1725,252)
\thinlines
\drawline(675,627)(900,927)
\drawline(852.000,813.000)(900.000,927.000)(804.000,849.000)
\drawline(225,252)(225,2052)
\drawline(255.000,1932.000)(225.000,2052.000)(195.000,1932.000)
\drawline(225,252)(2025,252)
\drawline(1905.000,222.000)(2025.000,252.000)(1905.000,282.000)
\put(225,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle 0}$}}}}}
\put(1725,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle n}$}}}}}
\put(0,1752){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle n}$}}}}}
\put(2100,177){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle i}$}}}}}
\put(150,2127){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle j}$}}}}}
\put(1135,1302){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$\Phi$}}}}}
\put(750,552){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$\Psi$}}}}}
\end{picture}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
& 
%\input degen_right.epic 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(2146,2286)(0,-10)
\drawline(1275.000,252.000)(1274.063,327.457)(1267.578,402.640)
	(1255.581,477.143)(1238.137,550.561)(1215.340,622.498)
	(1187.314,692.563)(1154.210,760.377)(1116.209,825.573)
	(1073.515,887.797)(1026.360,946.712)(975.000,1002.000)
	(919.712,1053.360)(860.797,1100.515)(798.573,1143.209)
	(733.377,1181.210)(665.563,1214.314)(595.498,1242.340)
	(523.561,1265.137)(450.143,1282.581)(375.640,1294.578)
	(300.457,1301.063)(225.000,1302.000)
\put(975,1002){\circle*{150}}
\drawline(1725,1752)(1725,1752)
\drawline(225,1752)(1725,1752)(1725,252)
\thicklines
\drawline(225,1752)(1725,252)
\thinlines
\drawline(1125,1077)(1275,1227)
\drawline(1188.640,1183.066)(1125.000,1077.000)(1231.066,1140.640)
\drawline(225,252)(225,2052)
\drawline(255.000,1932.000)(225.000,2052.000)(195.000,1932.000)
\drawline(225,252)(2025,252)
\drawline(1905.000,222.000)(2025.000,252.000)(1905.000,282.000)
\put(225,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle 0}$}}}}}
\put(1725,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle n}$}}}}}
\put(0,1752){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle n}$}}}}}
\put(2100,177){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle i}$}}}}}
\put(150,2127){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle j}$}}}}}
\put(1200,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}${\scriptstyle n/\sqrt{2}}$}}}}}
\put(1425,627){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$\Phi$}}}}}
\put(1350,1227){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$\Psi$}}}}}
\end{picture}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\\
$\begin{array}{c} \\[0.5ex]
\Psi \unlhd \Phi \\[1ex]
\underbrace{i}_{a(i)} + \underbrace{(j-n)}_{b(j)} \ge 0 \mbox{ auf $\Phi$} \\[1ex]
\mbox{Gleichheit auf $\Psi$} 
\end{array}$ &
$\begin{array}{c} \\[1ex]
\Psi \unlhd \Phi \\[1ex]
\underbrace{i^{2}}_{a(i)} + \underbrace{(j^{2}-n^{2}/2)}_{b(j)} \ge 0 
\mbox{ auf $\Phi$} \\[1ex]
\mbox{Gleichheit auf $\Psi$} 
\end{array}$ 
\end{tabular}
\end{center}
\hrulefill\ 
\end{figure}

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.

\begin{proposition}\label{pro:degen}
Es sei $t$ ein Tensor mit Blockzerlegung $D$ und 
$\Psi \unlhd \supp_D t$. Dann gilt 
$\br \big(\sum_{(i,j,\ell)\in\Psi} t(i,j,\ell)\big) \le \br(t)$.
\end{proposition}
%
Zum Beweis erw\"ahnen wir nur, dass $\sum_{\Psi} t(i,j,\ell)$ 
aufgrund der Voraussetzung $ \Psi\unlhd \supp_D t$ 
als eine torische Degeneration von $t$ interpretiert werden kann, 
woraus die Behauptung leicht folgt.


Wir haben nun die n\"otigen Hilfsmittel zusammengestellt, um die
{\em Strategie} der sogenannten Lasermethode zu erl\"autern. 
Angenommen, wir haben einen Tensor $t$ mit Blockzerlegung $D$
mit folgenden Eigenschaften: 
\begin{enumerate}
\item alle $D$-Komponenten sind Matrixtensoren,
\item eine ``grosse'' Diagonale $\Delta$ ist Degeneration von $\supp_D t$, 
\item wir kennen eine (gute) obere Schranke $r$ f\"ur den 
 Grenzrang von $t$.
\end{enumerate}
Dann k\"onnen wir aufgrund von Proposition~\ref{pro:degen} schliessen, dass
$$
 \br \Big(\bigoplus_{(i,j,\ell) \in \Delta} t(i,j,\ell) \Big) \le 
  \br(t) \le r.
$$
Jetzt l\"asst sich die asymptotische Summenungleichung anwenden und 
wir erhalten eine Absch\"atzung f\"ur den Exponenten. 

\section{Absch\"atzung des Exponenten}

Das Hauptergebnis dieses Abschnittes ist rein kombinatorischer Natur 
und liefert eine quantitative Aussage \"uber die Gr\"osse von Diagonalen, 
die sich aus gewissen Teilmengen von 
kombina\-torischen W\"urfeln herausdegenerieren lassen. 
Damit l\"asst sich die zweite Bedingung der im letzten Abschnitt 
erl\"auterten Strategie erf\"ullen. 

F\"ur ein positive nat\"urliche Zahl $b$ setzen wir 
$I_b :=\{-b,-b+1,\ldots,b\}\subseteq \ZZ$ und 
$T_b :=\{(x,y,z) \in I_b^3 \mid x+y+z=0\}\subseteq \ZZ^3$.

\begin{definition}
$\Phi\subseteq I\times J\times L$ heisst {\em $b$-straff}, falls
es ein $r\ge1$ und injektive Abbildungen
$\alpha\colon I \to \ZZ^r$, $\beta\colon J \to \ZZ^r$,
$\gamma\colon L \to \ZZ^r$ gibt so, dass
$$
 (\alpha,\beta,\gamma)(\Phi)\subseteq (T_b)^r .
$$
\end{definition}

Eine Teilmenge $\Phi\subseteq I\times J\times L$ ist also 
$b$-straff, wenn sie sich unter Erhaltung  der Produktstruktur 
injektiv in ein Produkt von $T_b$'s einbetten l\"asst.

Der n\"achste Satz beinhaltet die Kernaussage der Methode, die wir 
hier beschreiben. Sein Beweis geht auf 
Coppersmith und Winograd~\cite{cowi:87,cowi:90} zur\"uck.
Die vorliegende gegl\"attete und vereinfachte Variante verdanken wir  
Strassen~\cite{stra:88,stra:91,stra:95}. 
Der Beweis ist ein sch\"ones Beispiel f\"ur die 
M\"achtigkeit der probabilistischen Methode in der Kombinatorik. 

\begin{theorem}
Sei $\Phi \subseteq I \times J \times L$ $b$-straff und etwa
$|I|\le |J|\le |L|$. Dann 
existiert eine Diagonale $\Delta$ in $\Phi$ mit 
Kardinalit\"at 
$$
  |\Delta| \ge \frac{1}{K} \min\{|I|,|J|,|L|\},
$$
welche Degeneration von $\Phi$ ist. 
Hierbei ist $K$ das $13.5$-fache des Maximums von 
$$
\frac{|I|}{|\Phi|}\max_{i\in I} |p_I^{-1}(i)|,\  
\frac{|J|}{|\Phi|}\max_{j\in J} |p_J^{-1}(j)|,\
\frac{|L|}{|\Phi|}\max_{\ell\in L} |p_L^{-1}(\ell)|,\ 
\frac{4}{9}(2b+1) \frac{|I|}{|\Phi|} 
$$
und 
$p_I\colon \Phi \to I$, $p_J\colon \Phi \to J$, $p_L\colon \Phi \to L$ 
bezeichnet die Projektionen, welche als surjektiv vorausgesetzt werden.
\end{theorem}

Wir skizzieren hier den Beweis nur in sehr groben Z\"ugen und verweisen 
f\"ur Details auf \cite[Chap.~15]{bucs:96}. 

Wir w\"ahlen eine Primzahl $M$, 
bezeichnen den endlichen K\"orper $\ZZ/M\ZZ$ mit $\FF_M$ und setzen
$$
\Psi_M:=\{(x,y,z)\in \FF_M^{\, 3} \mid x+y+z=0\}.
$$
Ausserdem sei $\varphi\colon \FF_M^{\, r}\to\FF_M$ eine 
lineare Abbildung. Wir betrachten nun das Diagramm
$$
\begin{array}{ccccccc}
I\times J\times L & \stackrel{(\alpha,\beta,\gamma)}{\hookrightarrow}&
\ZZ^r \times\ZZ^r \times \ZZ^r & \rightarrow & 
\FF_M^{\, r} \times\FF_M^{\, r}\times \FF_M^{\, r} & 
 \stackrel{(\varphi,\varphi,\varphi)}{\rightarrow}&
\FF_M^{\, 3}\\
\uparrow&&\uparrow&&\uparrow&&\uparrow\\
\Phi& \rightarrow& (T_b)^r&\rightarrow&(\Psi_M)^r&\rightarrow&\Psi_M
\end{array}
$$
Die Komposition der unteren drei Abbildungen heisse $F_\varphi$. 
Wenn wir $M$ gen\"u\-gend gross w\"ahlen, ist die Komposition von 
$(\alpha,\beta,\gamma)$ mit der Restklassenabbildung
$\ZZ^r \times\ZZ^r \times \ZZ^r \to \FF_M^{\, r} \times\FF_M^{\, r} 
\times \FF_M^{\, r}$ injektiv. 

Mit einer direkten Konstruktion kann man leicht eine Diagonale
$D\unlhd \Psi_M$ gewinnen mit $|D|\ge M/2$. 
Durch Zur\"uckziehen sieht man, dass 
$F_\varphi^{-1}(D)$ Degeneration von $\Phi$ ist. 
Wir schreiben $F_\varphi^{-1}(D)$ als Vereinigung seiner Fasern
$$
F_\varphi^{-1}(D)= F_\varphi^{-1}(d_1) \cup F_\varphi^{-1}(d_2)\cup \ldots
$$
und degenerieren mit einem weiteren direkten Verfahren jede Faser 
$F_\varphi^{-1}(d_i)$ zu 
einer Diagonale $\Delta_\varphi^i$: 
$\Delta_\varphi^i \unlhd F_\varphi^{-1}(d_i)$. 
Weil $D$ diagonal ist, m\"ussen die Fasern $F_\varphi^{-1}(d_i)$ in 
W\"urfeln mit paarweise disjunkten Kanten liegen. Daraus erh\"alt man, dass 
$\Delta_\varphi := \Delta_\varphi^1 \cup \Delta_\varphi^2 \cup\ldots$
auch diagonal und ausserdem eine Degeneration von $\Phi$ ist. 

Nun kommt der Clou! Wir w\"ahlen die lineare Abbildung 
$\varphi\colon \FF_M^{\, r}\to\FF_M$ {\em zuf\"allig}, womit
die Kardinalit\"at $|\Delta_\varphi|$ eine 
Zufallsvariable wird, deren Erwartungswert abgesch\"atzt werden kann.
(Strenggenommen arbeitet man mit einer kleinen Modifikation von 
$\alpha,\beta,\gamma$, um stochastische Unabh\"angigkeit zu garantieren.) 
Man w\"ahlt dann die Primzahl $M$ so, dass 
$$
 E(|\Delta_\varphi|) \ge \frac{1}{K} \min\{|I|,|J|,|L|\} .
$$
Daraus folgt, dass es mindestens ein $\varphi$ gibt, f\"ur das
$|\Delta_\varphi|$ die gew\"unschte Gr\"osse hat.


Nun k\"onnen wir diesen Satz mit unserer Strategie kombinieren. 
Wir w\"ahlen einen Tensor $t$ mit einer Blockzerlegung $D$ so, dass
alle $D$-Komponenten Matrixtensoren sind und mit der 
Eigenschaft, dass der $D$-Tr\"ager straff ist.
Dann erhalten wir aus der asymptotischen Summenungleichung eine
Absch\"atzung f\"ur den Exponenten. 
Wir k\"onnen diese noch verbessern, indem wir das Verfahren 
auf eine hohe Tensorpotenz $t^{\otimes N}$ mit der zugeh\"origen 
Blockzerlegung anwenden. Auf diese Art kann man folgendes 
zeigen: 


\begin{corollary}[Coppersmith and Winograd~\cite{cowi:87}]
$\omega < 2.38$. 
\end{corollary}


Obwohl seit 1987 keine besseren Absch\"atzungen f\"ur den 
Exponenten gefunden wurden, ist hier das letzte Wort sicherlich 
noch nicht gesprochen. 

Die vergebliche Suche nach nichttrivialen unteren Schranken f\"ur 
den Exponenten, sowie die massiven Verbesserungen bei den oberen
Schranken lassen die Vermutung zu, dass der Exponent $\omega$ 
{\em zwei} sein k\"onnte. 
Diese Vermutung wird gest\"utzt durch das folgende Resultat 
von Coppersmith~\cite{copp:82}
$$
  R(\langle h,h,\lfloor h^{0.17} \rfloor \rangle) = O(h^2 \log^2 h).
$$
Demnach lassen sich eine quadratische $h$-reihige und eine 
rechteckige $h\times h^{0.17}$-Matrix mit einem Aufwand
multiplizieren, der beinahe linear in der Inputgr\"osse $h^2$ ist. 

Ich m\"ochte den Vortrag mit der Frage schliessen, ob tats\"achlich 
$\omega =2$ ist. Dies ist sicher eine der zentralen offenen
Probleme der algebraischen Komplexit\"atstheorie.


%\bibliography{/usr/home/buerg/complex/public/bib/lit-bank}
%\bibliography{/home/assisun/buerg/complex/public/bib/lit-bank}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{10}

\bibitem{bast:83}
W.~Baur and V.~Strassen.
\newblock The complexity of partial derivatives.
\newblock {\em Theoret.\ Comp.\ Sc.}, 22:317--330, 1983.

\bibitem{bini:80-1}
D.~Bini.
\newblock Relation between exact and approximate bilinear algorithms.\
  {A}pplications.
\newblock {\em Calcolo}, 17:87--97, 1980.

\bibitem{bclr:79}
D.~Bini, M.~Capovani, G.~Lotti, and F.~Romani.
\newblock ${O}(n^{2.7799})$ complexity for matrix multiplication.
\newblock {\em Inf.~Proc.\ Letters}, 8:234--235, 1979.

\bibitem{bucs:96}
P.~B\"urgisser, M.~Clausen, and M.A.~Shokrollahi.
\newblock {\em Algebraic Complexity Theory}, {\em {G}rundlehren
  der mathematischen {W}issenschaften}, Bd.~315.
\newblock Springer Verlag, 1996.

\bibitem{clau:88}
M.~Clausen. 
\newblock Beitr\"age zum {E}ntwurf schneller
		{S}pek\-tral\-trans\-for\-ma\-ti\-o\-nen.
\newblock Habi\-li\-ta\-tions\-schrift, Universit\"at Karlsruhe, 1988. 

\bibitem{copp:82}
D.~Coppersmith.
\newblock Rapid multiplication of rectangular matrices.
\newblock {\em {SIAM} J.\ Comp.}, 11:467--471, 1982.

\bibitem{cowi:87}
D.~Coppersmith and S.~Winograd.
\newblock Matrix multiplications via arithmetic progression.
\newblock In {\em Proc.\ 19th ACM STOC}, pages 1--6, 1987.

\bibitem{cowi:90}
D.~Coppersmith and S.~Winograd.
\newblock Matrix multiplication via arithmetic progressions.
\newblock {\em J.\ Symb.\ Comp.}, 9:251--280, 1990.

\bibitem{vpan:79}
V.Ya. Pan.
\newblock Field extension and trilinear aggregating, uniting and cancelling for
  the acceleration of matrix multiplication.
\newblock In {\em Proc.~of the 20th Ann.~{IEEE} Symp.~on Foundations of Comp.
  Sc.}, pages 28--38, 1979.

\bibitem{scho:81}
A.~Sch\"onhage.
\newblock Partial and total matrix multiplication.
\newblock {\em {SIAM} J.\ Comp.}, 10:434--455, 1981.

\bibitem{stra:69}
V.~Strassen.
\newblock {Gaussian} elimination is not optimal.
\newblock {\em Num.~Math.}, 13:354--356, 1969.

\bibitem{stra:73-1}
V.~Strassen.
\newblock {Vermeidung} von {Divisionen}.
\newblock {\em Crelles J.\ Reine Angew.~Math.}, 264:184--202, 1973.

\bibitem{stra:87}
V.~Strassen.
\newblock Relative bilinear complexity and matrix multiplication.
\newblock {\em Crelles J.\ Reine Angew.~Math.}, 375/376:406--443, 1987.

\bibitem{stra:88}
V.~Strassen.
\newblock The asymptotic spectrum of tensors.
\newblock {\em Crelles J.\ Reine Angew.~Math.}, 384:102--152, 1988.

\bibitem{stra:91}
V.~Strassen.
\newblock Degeneration and complexity of bilinear maps: some asymptotic
  spectra.
\newblock {\em Crelles J.\ Reine Angew.~Math.}, 413:127--180, 1991.

\bibitem{stra:95}
V.~Strassen.
\newblock Private Mitteilung, 1995.

\end{thebibliography}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}


