User:Fawly/Computational complexity of matrix multiplication: Difference between revisions

Revision as of 18:24, 21 May 2021

Revision as of 18:41, 21 May 2021

Line 1:

In [[theoretical computer science]], an active area of research is determining [[Analysis of algorithms|how efficient]] the operation of [[matrix multiplication]] can be performed. [[Matrix multiplication algorithm]]s are a central subroutine in theoretical and [[numerical algorithm|numerical]] algorithms for [[numerical linear algebra]] and [[optimization]], so finding the right amount of time it should take is of major practical relevance.

Because [[matrix multiplication]] is such a central operation in many [[numerical algorithm]]s, much work has been invested in making '''matrix multiplication algorithms''' efficient. Applications of matrix multiplication in computational problems are found in many fields including [[scientific computing]] and [[pattern recognition]] and in seemingly unrelated problems such as counting the paths through a [[Graph (graph theory)|graph]].<ref name="skiena"/> Many different algorithms have been designed for multiplying matrices on different types of hardware, including [[parallel computing|parallel]] and [[distributed computing|distributed]] systems, where the computational work is spread over multiple processors (perhaps over a network).

Directly applying the mathematical definition of matrix multiplication gives an algorithm that [[Analysis of algorithms|takes time]] on the order of {{math|''n''³}} [[Field (mathematics)|field]] operations to multiply two {{math|''n'' × ''n''}} matrices over that field ({{math|Θ(''n''³)}} in [[big O notation]]). BetterSurprisingly, asymptoticalgorithms boundsexist onthat theprovide timebetter requiredrunning totimes multiplythan matricesthis havestraightforward been"schoolbook knownalgorithm". sinceThe thefirst to be discovered was [[Strassen algorithm|Strassen's algorithm]], devised by [[Volker Strassen]] in the1969 1960s,and butoften itreferred to as "fast matrix multiplication". It is still unknown what the optimal timenumber of field operations is (i.e.,required whatto themultiply [[Computationaltwo complexitysquare theory{{math|complexity''n'' of× the''n''}} problem]] is)matrices. {{As of|2020|12}}, the matrix multiplication algorithm with best asymptotic complexity runs in {{math|O(''n''^2.3728596)}} time, given by Josh Alman and [[Virginia Vassilevska Williams]],<ref name="aw20">{{Citation | last1=Alman | first1=Josh | last2=Williams | first2=Virginia Vassilevska | contribution=A Refined Laser Method and Faster Matrix Multiplication | year = 2020 | arxiv=2010.05846 | title = 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) |url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers}}</ref><ref>{{Cite web|last=Hartnett|first=Kevin|title=Matrix Multiplication Inches Closer to Mythic Goal|url=https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/|access-date=2021-04-01|website=Quanta Magazine|language=en}}</ref> however this algorithm is a [[galactic algorithm]] because of the large constants and cannot be realized practically.

{{Citation

| last1=Alman

Surprisingly, algorithms exist that provide better running times than the straightforward ones. The first to be discovered was [[Strassen algorithm|Strassen's algorithm]], devised by [[Volker Strassen]] in 1969 and often referred to as "fast matrix multiplication". It is based on a way of multiplying two {{math|2 × 2}}-matrices which requires only 7 multiplications (instead of the usual 8), at the expense of several additional addition and subtraction operations. Applying this recursively gives an algorithm with a multiplicative cost of <math>O( n^{\log_{2}7}) \approx O(n^{2.807})</math>. Strassen's algorithm is more complex, and the [[numerical stability]] is reduced compared to the naïve algorithm,<ref>{{Citation | last1=Miller | first1=Webb | title=Computational complexity and numerical stability | citeseerx = 10.1.1.148.9947 | year=1975 | journal=SIAM News | volume=4 | issue=2 | pages=97–107 | doi=10.1137/0204009}}</ref> but it is faster in cases where {{math|''n'' > 100}} or so<ref name="skiena"/> and appears in several libraries, such as [[Basic Linear Algebra Subprograms|BLAS]].<ref>{{cite book |last1=Press |first1=William H. |last2=Flannery |first2=Brian P. |last3=Teukolsky |first3=Saul A. |author3-link=Saul Teukolsky |last4=Vetterling |first4=William T. |title=Numerical Recipes: The Art of Scientific Computing |publisher=[[Cambridge University Press]] |edition=3rd |isbn=978-0-521-88068-8 |year=2007 |page=[https://archive.org/details/numericalrecipes00pres_033/page/n131 108]|title-link=Numerical Recipes }}</ref> It is very useful for large matrices over exact domains such as [[finite field]]s, where numerical stability is not an issue.

| first1=Josh

| last2=Williams

The matrix multiplication [[algorithm]] that results of the definition requires, in the [[worst-case complexity|worst case]], {{tmath|n^3}} multiplications of scalars and {{tmath|(n-1)n^2}} additions for computing 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 require a constant time (in practice, this is the case for [[floating point]] numbers, but not for integers).

| first2=Virginia Vassilevska

| contribution=A Refined Laser Method and Faster Matrix Multiplication

The [[greatest lower bound]] for the exponent of matrix multiplication algorithm is generally called {{tmath|\omega}}. It is trivially true that {{tmath|\omega \ge 2}}, because one must read the {{tmath|n^2}} elements of a matrix in order to multiply it with another matrix. Thus {{tmath|2\le \omega < 2.373}}. It is unknown whether {{tmath|\omega > 2}}. The largest known lower bound for matrix-multiplication complexity is {{math|Ω(''n''² log(''n''))}}, for a restricted kind of [[Arithmetic circuit complexity|arithmetic circuits]], and is due to [[Ran Raz]].<ref>

| year = 2020

{{Cite journal

| lastarxiv=Raz2010.05846

| title = 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)

| first=Ran

|url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers

| date=January 2003

}}</ref><ref>{{Cite web|last=Hartnett|first=Kevin|title=Matrix Multiplication Inches Closer to Mythic Goal|url=https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/|access-date=2021-04-01|website=Quanta Magazine|language=en}}</ref> however this algorithm is a [[galactic algorithm]] because of the large constants and cannot be realized practically.

| title=On the Complexity of Matrix Product

| journal=SIAM Journal on Computing

| volume=32

| issue=5

| pages=1356–1369

| doi=10.1137/s0097539702402147

| issn=0097-5397

}}</ref>

[[Freivalds' algorithm]] is a simple [[Monte Carlo algorithm]] that, given matrices {{mvar|A}}, {{mvar|B}} and {{mvar|C}}, verifies in {{math|Θ(''n''²)}} time if {{math|''AB'' {{=}} ''C''}}.

Line 56 ⟶ 49:

}}</ref>

|-

| 1979 || 2.78780 || Bini, Capovani, Romani<ref>

{{cite journal

| doi=10.1016/0020-0190(79)90113-3

Line 180 ⟶ 173:

}}</ref>

|-

| 2020 || 2.3728596 || Alman, [[Virginia Vassilevska Williams|Williams]]<ref name="Alman2020aw20"/>

{{Citation

| last1=Alman

| first1=Josh

| last2=Williams

| first2=Virginia Vassilevska

| contribution=A Refined Laser Method and Faster Matrix Multiplication

| year = 2020

| arxiv=2010.05846

| title = 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)

|url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers

}}</ref>

|}

Surprisingly, algorithms exist that provide better running times than the straightforward ones. The first to be discovered was [[Strassen algorithm|Strassen's algorithm]], devised by [[Volker Strassen]] in 1969 and often referred to as "fast matrix multiplication". It is based on a way of multiplying two {{math|2 × 2}}-matrices which requires only 7 multiplications (instead of the usual 8), at the expense of several additional addition and subtraction operations. Applying this recursively gives an algorithm with a multiplicative cost of <math>O( n^{\log_{2}7}) \approx O(n^{2.807})</math>. Strassen's algorithm is more complex, and the [[numerical stability]] is reduced compared to the naïve algorithm,<ref>{{Citation | last1=Miller | first1=Webb | title=Computational complexity and numerical stability | citeseerx = 10.1.1.148.9947 | year=1975 | journal=SIAM News | volume=4 | issue=2 | pages=97–107 | doi=10.1137/0204009}}</ref> but it is faster in cases where {{math|''n'' > 100}} or so<ref name="skiena"/> and appears in several libraries, such as [[Basic Linear Algebra Subprograms|BLAS]].<ref>{{cite book |last1=Press |first1=William H. |last2=Flannery |first2=Brian P. |last3=Teukolsky |first3=Saul A. |author3-link=Saul Teukolsky |last4=Vetterling |first4=William T. |title=Numerical Recipes: The Art of Scientific Computing |publisher=[[Cambridge University Press]] |edition=3rd |isbn=978-0-521-88068-8 |year=2007 |page=[https://archive.org/details/numericalrecipes00pres_033/page/n131 108]|title-link=Numerical Recipes }}</ref> It is very useful for large matrices over exact domains such as [[finite field]]s, where numerical stability is not an issue.

The matrix multiplication [[algorithm]] that results of the definition requires, in the [[worst-case complexity|worst case]], {{tmath|n^3}} multiplications of scalars and {{tmath|(n-1)n^2}} additions for computing 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 require a constant time (in practice, this is the case for [[floating point]] numbers, but not for integers).

The [[greatest lower bound]] for the exponent of matrix multiplication algorithm is generally called {{tmath|\omega}}. It is trivially true that {{tmath|\omega \ge 2}}, because one must read the {{tmath|n^2}} elements of a matrix in order to multiply it with another matrix. Thus {{tmath|2\le \omega < 2.373}}. It is unknown whether {{tmath|\omega > 2}}. The largest known lower bound for matrix-multiplication complexity is {{math|Ω(''n''² log(''n''))}}, for a restricted kind of [[Arithmetic circuit complexity|arithmetic circuits]], and is due to [[Ran Raz]].<ref>

{{Cite journal

| last=Raz

| first=Ran

| date=January 2003

| title=On the Complexity of Matrix Product

| journal=SIAM Journal on Computing

| volume=32

| issue=5

| pages=1356–1369

| doi=10.1137/s0097539702402147

| issn=0097-5397

}}</ref>

It is an open question in [[theoretical computer science]] how well Strassen's algorithm can be improved in terms of [[Time complexity|asymptotic complexity]]. The ''matrix multiplication exponent'', usually denoted <math>\omega</math>, is the smallest real number for which any <math>n\times n</math> matrix over a field can be multiplied together using <math>n^{\omega + o(1)}</math> field operations.