Content deleted Content added
Yuval Filmus (talk | contribs) 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. |
Bender2k14 (talk | contribs) m changed link to more authoritative source |
||
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://
The Coppersmith–Winograd algorithm is frequently used as a building block in other algorithms to prove theoretical time bounds.
| |||