Computational complexity of matrix multiplication: Difference between revisions

Revision as of 07:18, 10 January 2025

Revision as of 07:21, 10 January 2025

Line 259:

=== Rectangular matrix multiplication ===

Similar techniques also apply to rectangular matrix multiplication. The central object of study is <math>\omega(k)</math>, which is the smallest <math>c</math> such that one can multiply a matrix of size <math>n\times \lceil n^k\rceil</math> with a matrix of size <math>\lceil n^k\rceil \times n</math> with <math>O(n^{c + o(1)})</math> arithmetic operations. A result in algebraic complexity states that multiplying matrices of size <math>n\times \lceil n^k\rceil</math> and <math>\lceil n^k\rceil \times n</math> requires the same number of arithmetic operations as multiplying matrices of size <math>n\times \lceil n^k\rceil</math> and <math>n \times n</math> and of size <math>n \times n</math> and <math>n\times \lceil n^k\rceil</math>, so this encompasses the complexity of rectangular matrix multiplication.<ref name="gall18">{{cite bookconference
| last1 = Gall | first1 = Francois Le
|title last2 = Urrutia | first2 = Florent
| editor-last = Czumaj | editor-first = Artur
| arxiv = 1708.05622
| contribution = Improved Rectangularrectangular Matrixmatrix Multiplicationmultiplication using Powerspowers of the Coppersmith-Winograd Tensortensor
|date=2018-01-01|url=https://epubs.siam.org/ doi/ = 10.1137/1.9781611975031.67
|work=Proceedings of the 2018pages Annual= ACM-SIAM Symposium on Discrete Algorithms (SODA)|pages=1029–1046
|series=Proceedings| publisher = Society for Industrial and Applied Mathematics
|doi title =10.1137/1.9781611975031.67|access Proceedings of the Twenty-date=2021Ninth Annual ACM-05-23|last2=Urrutia|first2=Florent|arxiv=1708.05622|isbn=978-1-61197-503-1SIAM |s2cid=33396059Symposium }}</ref>on ThisDiscrete generalizesAlgorithms, theSODA square2018, matrixNew multiplicationOrleans, exponentLA, sinceUSA, <math>\omega(1)January =7–10, \omega</math>.2018

| year = 2018}}</ref> This generalizes the square matrix multiplication exponent, since <math>\omega(1) = \omega</math>.

Since the output of the matrix multiplication problem is size <math>n^2</math>, we have <math>\omega(k) \geq 2</math> for all values of <math>k</math>. If one can prove for some values of <math>k</math> between 0 and 1 that <math>\omega(k) \leq 2</math>, then such a result shows that <math>\omega(k) = 2</math> for those <math>k</math>. The largest ''k'' such that <math>\omega(k) = 2</math> is known as the ''dual matrix multiplication exponent'', usually denoted ''α''. ''α'' is referred to as the "[[Duality (optimization)|dual]]" because showing that <math>\alpha = 1</math> is equivalent to showing that <math>\omega = 2</math>. Like the matrix multiplication exponent, the dual matrix multiplication exponent sometimes appears in the complexity of algorithms in numerical linear algebra and optimization.<ref>{{Cite journal|last1=Cohen|first1=Michael B.|last2=Lee|first2=Yin Tat|last3=Song|first3=Zhao|date=2021-01-05|title=Solving Linear Programs in the Current Matrix Multiplication Time|url=https://doi.org/10.1145/3424305|journal=Journal of the ACM|volume=68|issue=1|pages=3:1–3:39|doi=10.1145/3424305|issn=0004-5411|arxiv=1810.07896|s2cid=231955576 }}</ref>