Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 17:08, 24 August 2012

Revision as of 18:34, 30 January 2013

Line 1:

In [[linear algebra]], the '''Coppersmith–Winograd algorithm''', named after [[Don Coppersmith]] and [[Shmuel Winograd]], was the asymptotically fastest known [[algorithm]] for square [[matrix multiplication]] until 2010. It can multiply two <math>n \times n</math> matrices in <math>O(n^{2.3737375477})</math> time{{fact|date <ref name=June"coppersmith">Don 2012}}Coppersmith (seeand Shmuel Winograd. [[Bighttp://www.cs.umd.edu/~gasarch/ramsey/matrixmult.pdf OMatrix notation]Multiplication via Arithmetic Progressions]). J. Symbolic

Computation, 9(3):251–280, 1990, doi:10.1016/S0747-7171(08)80013-2.</ref> (see [[Big O notation]]).

This is an improvement over the naïve <math>O(n^3)</math> time algorithm and the <math>O(n^{2.807})</math> time [[Strassen algorithm]]. Algorithms with better asymptotic running time than the Strassen algorithm are rarely used in practice.

It is possible to improve the exponent further; however, the exponent must be at least 2 (because an <math>n \times n</math> matrix has <math>n^2</math> values, and all of them have to be read at least once to calculate the exact result).

It was known that the complexity of this algorithm is <math>O(n^{2.3755}).</math>{{vague|reason=It was earlier stated in this article that this algorithm is O(n^2.3737). What does it even mean that "it was known that..."?|date=June 2012}}<ref>D. Coppersmith and S. Winograd. [http://www.cs.umd.edu/~gasarch/ramsey/matrixmult.pdf Matrix Multiplication via Arithmetic Progressions]. J. Symbolic

Computation, 9(3):251–280, 1990.</ref>

In 2010, Andrew Stothers gave an improvement to the algorithm, <math>O(n^{2.3736}).</math><ref>{{Citation | last1=Stothers | first1=Andrew | title=On the Complexity of Matrix Multiplication | url=http://www.maths.ed.ac.uk/pg/thesis/stothers.pdf | year=2010}}.</ref> In 2011, Virginia Williams combined a mathematical short-cut from Stothers' paper with her own insights and automated optimization on computers, improving the bound to <math>O(n^{2.3727}).</math><ref>{{Citation | last1=Williams | first1=Virginia | title=Breaking the Coppersmith-Winograd barrier | url=http://www.cs.berkeley.edu/~virgi/matrixmult.pdf | year=2011}}</ref>

Line 18 ⟶ 17:

* [[Gauss–Jordan elimination]]

* [[Strassen algorithm]]

== References ==

{{reflist}}

* {{Citation | doi=10.1016/S0747-7171(08)80013-2 | last1=Coppersmith | first1=Don |last2= Winograd | first2=Shmuel | title=Matrix multiplication via arithmetic progressions | url=http://www.cs.umd.edu/~gasarch/ramsey/matrixmult.pdf | year=1990 | journal=Journal of Symbolic Computation| volume=9 | issue=3 | pages=251–280}}.

* {{Citation | last1=Williams | first1=Virginia | title=Breaking the Coppersmith-Winograd barrier | url=http://www.cs.berkeley.edu/~virgi/matrixmult.pdf | year=2011}}.

{{Numerical linear algebra}}