Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 07:39, 24 June 2012

Revision as of 22:39, 17 August 2012

Line 7:

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?}}.

However, unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware.<ref>{{Citation | last1=Robinson | first1=Sara | title=Toward an Optimal Algorithm for Matrix Multiplication | url=http://www.siam.org/pdf/news/174.pdf | year=2005 | journal=SIAM News | volume=38 | issue=9}}</ref>