TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Inhalt des Dokuments

zur Navigation

Leitung

Prof. Dr. Peter Bürgisser

Lupe

Anschrift
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Büro
Raum MA 317 (3. OG)
Institut für Mathematik

Kontakt

Sekretariat
Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771

eMail
peter.buergisser@offmath.tu-berlin.de

Telefon
+49 (0)30 314 - 75902
Faxgerät
+49 (0)30 314 - 25839

Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.

Publikationen

Algebraische Komplexitaetstheorie II - Schnelle Matrixmultiplikation und Kombinatorik
Zitatschlüssel B-Algebraische-Komplexitaetstheorie-Ii-Schnelle-Matrixmultiplikation-Und-Kombinatorik
Autor Peter Bürgisser
Buchtitel Seminaire Lotharingien de Combinatoire
Seiten 1-16
Jahr 1996
Nummer B36b
Zusammenfassung 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 ω of matrix multiplication. By extending a method by Strassen, Coppersmith and Winograd showed in 1987 that $ømega < 2.38$. Today, one even conjectures that $ømega = 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.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe