Coppersmith–Winograd algorithm: Difference between revisions

Content deleted Content added
No edit summary
Added a reference to the journal version of Stothers' work, corrected the exponent obtained by Virginia Williams, and added the current world record by François Le Gall.
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.3736373}).</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><ref>{{Citation | last1=Davie | first1=A.M. | last2=Stothers | first2=A.J. | title=Improved bound for complexity of matrix multiplication|journal=Proceedings of the Royal Society of Edinburgh|volume=143A|pages=351–370|year=2013|doi=10.1017/S0308210511001648}}</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.37273728642}).</math><ref>{{Citation | last1=Williams | first1=Virginia | title=Breaking the Coppersmith-Winograd barrier | url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.228.9947&rep=rep1&type=pdf | year=2011}}</ref> In 2014, François Le Gall simplified the methods of Williams and obtained an improved bound of <math>O(n^{2.3728639}).</math><ref>{{Citation | last1=Le Gall | first1=François | title=Powers of tensors and fast matrix multiplication | url=http://arxiv.org/pdf/1401.7714}}</ref>
 
The Coppersmith–Winograd algorithm is frequently used as a building block in other algorithms to prove theoretical time bounds.