Computational complexity of matrix multiplication: Difference between revisions

Revision as of 07:21, 10 January 2025

Revision as of 18:01, 1 February 2025

Line 18:

}}</ref> The optimal number of field operations needed to multiply two square {{math|''n'' × ''n''}} matrices [[big O notation|up to constant factors]] is still unknown. This is a major open question in [[theoretical computer science]].

{{As of|2024|01}}, the best bound on the [[Time complexity|asymptotic complexity]] of a matrix multiplication algorithm is {{math|O(''n''^2.371339)}}.<ref name="adwxxz24">

{{As of|2024|01}}, the best bound on the [[Time complexity|asymptotic complexity]] of a matrix multiplication algorithm is {{math|O(''n''^2.371552)}}.<ref name="wxxz23">{{cite conference |last1=Vassilevska Williams |first1=Virginia |last2=Xu |first2=Yinzhan |last3=Xu |first3=Zixuan |last4=Zhou |first4=Renfei |title=New Bounds for Matrix Multiplication: from Alpha to Omega |conference=Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=3792–3835 |arxiv=2307.07970 |doi=10.1137/1.9781611977912.134}}</ref><ref>{{cite web |last=Nadis |first=Steve |date=March 7, 2024 |title=New Breakthrough Brings Matrix Multiplication Closer to Ideal |url=https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307 |access-date=2024-03-09}}</ref> However, this and similar improvements to Strassen are not used in practice, because they are [[galactic algorithm]]s: the constant coefficient hidden by the [[big O notation]] is so large that they are only worthwhile for matrices that are too large to handle on present-day computers.<ref>{{cite journal

{{cite arXiv |eprint=2404.16349 |class=cs.DS |first1=Josh |last1=Alman |first2=Ran |last2=Duan |first3=Virginia Vassilevska |last3=Williams |first4=Yinzhan| last4=Xu |first5=Zixuan |last5=Xu |first6=Renfei |last6=Zhou |title=More Asymmetry Yields Faster Matrix Multiplication |year=2024}}</ref> However, this and similar improvements to Strassen are not used in practice, because they are [[galactic algorithm]]s: the constant coefficient hidden by the [[big O notation]] is so large that they are only worthwhile for matrices that are too large to handle on present-day computers.<ref>{{cite journal

| last = Iliopoulos

| first = Costas S.

Line 233 ⟶ 234:

{{cite arXiv |eprint=2210.10173 |class=cs.DS |first1=Ran |last1=Duan |first2=Hongxun |last2=Wu |title=Faster Matrix Multiplication via Asymmetric Hashing |last3=Zhou |first3=Renfei |year=2022}}</ref>

|-

| 2024 || 2.371552 || [[Virginia Vassilevska Williams|Williams]], Xu, Xu, and Zhou<ref name="wxxz23"/>{{cite conference |last1=Vassilevska Williams |first1=Virginia |last2=Xu |first2=Yinzhan |last3=Xu |first3=Zixuan |last4=Zhou |first4=Renfei |title=New Bounds for Matrix Multiplication: from Alpha to Omega |conference=Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=3792–3835 |arxiv=2307.07970 |doi=10.1137/1.9781611977912.134}}

</ref>

|-

| 2024 || 2.371339 || Alman, Duan, [[Virginia Vassilevska Williams|Williams]], Xu, Xu, and Zhou<ref name="adwxxz24"/>

{{cite arXiv |eprint=2404.16349 |class=cs.DS |first1=Josh |last1=Alman |first2=Ran |last2=Duan |first3=Virginia Vassilevska |last3=Williams |first4=Yinzhan| last4=Xu |first5=Zixuan |last5=Xu |first6=Renfei |last6=Zhou |title=More Asymmetry Yields Faster Matrix Multiplication |year=2024}}</ref>

|}