Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 23:08, 30 April 2021

Revision as of 16:40, 4 May 2021

Line 18:

| pages = 514–523

| title = Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)

| year = 2012| s2cid = 2410545

| year = 2012}}.</ref> It is possible to improve the exponent further; however, the exponent must be at least 2 (because there are <math>n \times n = n^2</math> values in the result which must be computed).

In 2010, Andrew Stothers gave an improvement to the algorithm, <math>\mathcal{O}(n^{2.374}).</math><ref>{{Citation

Line 25 ⟶ 26:

| type=Ph.D thesis | publisher=University of Edinburgh

| url=https://www.era.lib.ed.ac.uk/handle/1842/4734

| year=2010| hdl=1842/4734
}}.</ref><ref>{{Citation

| last1=Davie | first1=A.M. | last2=Stothers | first2=A.J.

| title=Improved bound for complexity of matrix multiplication

Line 31 ⟶ 33:

| volume=143A | issue=2 | pages=351–370 | date=April 2013

| doi=10.1017/S0308210511001648

| s2cid=113401430 | url=https://www.maths.ed.ac.uk/~adavie/a11164.pdf

}}</ref> In 2011, [[Virginia Vassilevska Williams]] combined a mathematical short-cut from Stothers' paper with her own insights and automated optimization on computers, improving the bound to <math>\mathcal{O}(n^{2.3728642}).</math><ref>{{Citation

| last1=Williams | first1=Virginia Vassilevska

Line 55 ⟶ 57:

}}</ref>

[[Henry Cohn]], [[Robert Kleinberg]], [[Balázs Szegedy]] and [[Chris Umans]] have re-derived the Coppersmith–Winograd algorithm using a [[group theory|group-theoretic]] construction. They also showed that either of two different conjectures would imply that the optimal exponent of matrix multiplication is 2, as has long been suspected. However, they were not able to formulate a specific solution leading to a better running-time than Coppersmith–Winograd.<ref>{{Cite book | last1 = Cohn | first1 = H. | last2 = Kleinberg | first2 = R. | last3 = Szegedy | first3 = B. | last4 = Umans | first4 = C. | chapter = Group-theoretic Algorithms for Matrix Multiplication | doi = 10.1109/SFCS.2005.39 | title = 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) | pages = 379 | year = 2005 | isbn = 0-7695-2468-0 | s2cid = 41278294 | url = https://authors.library.caltech.edu/23966/ }}</ref> Several of their conjectures have since been disproven by Blasiak, Cohn, Church, Grochow, Naslund, Sawin, and Umans using the Slice Rank method.<ref>{{Cite book | last1 = Blasiak | first1 = J. | last2 = Cohn | first2 = H. | last3 = Church | first3 = T. | last4 = Grochow | first4 = J. | last5 = Naslund | first5= E. | last6 = Sawin | first6 = W. | last7=Umans | first7= C.| chapter= On cap sets and the group-theoretic approach to matrix multiplication | doi = 10.19086/da.1245 | title = Discrete Analysis | year = 2017 | s2cid = 9687868 | url = http://discreteanalysisjournal.com/article/1245-on-cap-sets-and-the-group-theoretic-approach-to-matrix-multiplication}}</ref>

== See also ==

Line 67 ⟶ 69:

== Further reading ==

*{{cite book |firstfirst1=P. |lastlast1=Bürgisser |first2=M. |last2=Clausen |first3=M. A. |last3=Shokrollahi |title=Algebraic Complexity Theory |series=Grundlehren der mathematischen Wissenschaften |volume=315 |publisher=Springer Verlag |year=1997 |isbn=3-540-60582-7}}

{{Numerical linear algebra}}