Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 06:19, 24 June 2012

Revision as of 07:14, 24 June 2012

Line 2:

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>In theD. Coppersmith and S. Winograd's. original paper<[http:/ref>/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>

The Coppersmith–Winograd algorithm is frequently used as a building block in other algorithms to prove theoretical time bounds {{notable examples?}}.