Editing Matrix multiplication (section)

==Computational complexity==
{{Main|Computational complexity of matrix multiplication}}
{{For|implementation techniques (in particular parallel and distributed algorithms)|Matrix multiplication algorithm}}
[[File:MatrixMultComplexity svg.svg|thumb|400px|right|Improvement of estimates of exponent {{math|ω}} over time for the computational complexity of matrix multiplication <math>O(n^\omega)</math>]]

The matrix multiplication [[algorithm]] that results from the definition requires, in the [[worst-case complexity|worst case]], {{tmath|n^3}} multiplications and {{tmath|(n-1)n^2}} additions of scalars to compute the product of two square {{math|''n''×''n''}} matrices. Its [[computational complexity]] is therefore {{tmath|O(n^3)}}, in a [[model of computation]] for which the scalar operations take constant time.

Rather surprisingly, this complexity is not optimal, as shown in 1969 by [[Volker Strassen]], who provided an algorithm, now called [[Strassen's algorithm]], with a complexity of <math>O( n^{\log_{2}7}) \approx O(n^{2.8074}).</math><ref>
{{cite journal 
 | doi=10.1007/BF02165411 
 | url=http://www.digizeitschriften.de/dms/img/?PID=GDZPPN001168215 
 | author=Volker Strassen 
 | title=Gaussian elimination is not optimal 
 | journal=Numerische Mathematik 
 | volume=13 
 | pages=354&ndash;356 
 | date=Aug 1969 
 | issue = 4
 | s2cid = 121656251
}}</ref>
Strassen's algorithm can be parallelized to further improve the performance.<ref>{{cite journal | url=https://core.ac.uk/download/pdf/82778592.pdf | author=C.-C. Chou and Y.-F. Deng and G. Li and Y. Wang | title=Parallelizing Strassen's Method for Matrix Multiplication on Distributed-Memory MIMD Architectures | journal=Computers Math. Applic. | volume=30 | number=2 | pages=49&ndash;69 | year=1995 | doi=10.1016/0898-1221(95)00077-C }}</ref>
{{As of|2024|01}}, the best peer-reviewed matrix multiplication algorithm is by [[Virginia Vassilevska Williams]], Yinzhan Xu, Zixuan Xu, and Renfei Zhou and has complexity {{math|''O''(''n''<sup>2.371552</sup>)}}.<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>
It is not known whether matrix multiplication can be performed in {{math|''n''<sup>2 + o(1)</sup>}} time.<ref>that is, in time {{math|''n''<sup>2+f(n)</sup>}}, for some function {{mvar|''f''}} with {{math|''f''(''n'')[[limit of a function|→]]0}} as {{math|''n''→∞}}</ref> This would be optimal, since one must read the {{tmath|n^2}} elements of a matrix in order to multiply it with another matrix.

Since matrix multiplication forms the basis for many algorithms, and many operations on matrices even have the same complexity as matrix multiplication (up to a multiplicative constant), the computational complexity of matrix multiplication appears throughout [[numerical linear algebra]] and [[theoretical computer science]].