direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

Algebraische Komplexitaetstheorie II - Schnelle Matrixmultiplikation und Kombinatorik
Citation key B-Algebraische-Komplexitaetstheorie-Ii-Schnelle-Matrixmultiplikation-Und-Kombinatorik
Author Peter Bürgisser
Title of Book Seminaire Lotharingien de Combinatoire
Pages 1-16
Year 1996
Number B36b
Abstract 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 to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.