Algebraische Komplexitätstheorie II: Schnelle Matrixmultiplikation und Kombinatorik
Séminaire lotharingien de combinatoire, Tome 36 (1996)
Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website
In 1969 Strassen discovered that Gaussian elimination is not an optimal algorithm for solving various problems in computational linear algebra. His result was based on a fast matrix multiplication algorithm needing only O(n\tau) arithmetic operations, where \tau 2.81. The infimum of all possible exponents \tau >= 2 is called the exponent \omega of matrix multiplication. By extending a method by Strassen, Coppersmith and Winograd showed in 1987 that \omega 2.38. Today, one even conjectures that \omega = 2. We survey the main ideas and methods, which have led to such insights about the complexity of matrix multiplication. In particular, we sketch a simplified version of Coppersmith and Winograd's proof which is based on a nonconstructive existence proof for some combinatorial structure.
@article{SLC_1996_36_a1,
author = {Peter B\"urgisser},
title = {Algebraische {Komplexit\"atstheorie} {II:} {Schnelle} {Matrixmultiplikation} und {Kombinatorik}},
journal = {S\'eminaire lotharingien de combinatoire},
publisher = {mathdoc},
volume = {36},
year = {1996},
url = {http://geodesic.mathdoc.fr/item/SLC_1996_36_a1/}
}
Peter Bürgisser. Algebraische Komplexitätstheorie II: Schnelle Matrixmultiplikation und Kombinatorik. Séminaire lotharingien de combinatoire, Tome 36 (1996). http://geodesic.mathdoc.fr/item/SLC_1996_36_a1/