98d:68110 68Q40 (68Q25)
Bürgisser, Peter (CH-ZRCH)
Algebraische Komplexitätstheorie. II. Schnelle Matrixmultiplikation und Kombinatorik. (German. German summary) [Algebraic complexity theory. II. Fast matrix multiplication and combinatorics]
Sém. Lothar. Combin. 36 (1996), Art. S36b, approx. 16 pp. (electronic).

This concise treatise puts in perspective the main concepts of the theory of bilinear complexity. In particular it explains the notion of "Grenzrang" (rank in the limit) due to D. Bini et al. [Inform. Process. Lett. 8 (1979), no. 5, 234--235; MR 80h:68024] and the "laser method" introduced by V. Strassen [J. Reine Angew. Math. 375/376 (1987), 406--443; MR 88h:11026]. The latter method led to the asymptotically fastest algorithm for matrix multiplication, due to D. Coppersmith and S. Winograd [J. Symbolic Comput. 9 (1990), no. 3, 251--280; MR 91i:68058]. It uses at most $n\sp w$, with $w<2.38$, arithmetical operations for the multiplication of $n\times n$ matrices, for sufficiently large $n$.

\{For Part I see the preceding review [MR 98d:68109].\}

Reviewed by Claus-Peter Schnorr

Back