Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 02:28, 6 July 2013

Revision as of 13:33, 22 August 2013

Line 4:

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).

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://wwwciteseerx.csist.berkeleypsu.edu/~virgiviewdoc/matrixmultdownload?doi=10.1.1.228.9947&rep=rep1&type=pdf | year=2011}}</ref>

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