Content deleted Content added
Bender2k14 (talk | contribs) m changed link to more authoritative source |
le gall is accepted to issac 2014 |
||
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.373}).</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.3728642}).</math><ref>{{Citation | last1=Williams | first1=Virginia | title=Breaking the Coppersmith-Winograd barrier | url=http://theory.stanford.edu/~virgi/matrixmult-f.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 |
The Coppersmith–Winograd algorithm is frequently used as a building block in other algorithms to prove theoretical time bounds.
| |||