\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}