Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 23:34, 22 June 2012

Revision as of 06:19, 24 June 2012

Line 4:

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 the Coppersmith and Winograd's original paper</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?}}.