direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

In Proceedings

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(ntau)$ 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 [1] Link to original publication [2] Download Bibtex entry [3]
------ Links: ------

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.
Copyright TU Berlin 2008