Content deleted Content added
←Redirected page to Matrix multiplication#Algorithms for efficient matrix multiplication |
create page Tags: Removed redirect 2017 wikitext editor |
||
Line 1:
In [[theoretical computer science]], an active area of research is determining [[Analysis of algorithms|how quickly]] 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.
Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires {{math|''n''<sup>3</sup>}} [[Field (mathematics)|field]] operations to multiply two {{math|''n'' × ''n''}} matrices over that field ({{math|Θ(''n''<sup>3</sup>)}} in [[big O notation]]). Surprisingly, algorithms exist that provide better running times than this straightforward "schoolbook algorithm". 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".<ref name="strassen69>
{{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–356
| date=Aug 1969
| issue = 4
| s2cid = 121656251
}}</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|2020|12}}, the matrix multiplication algorithm with best [[Time complexity|asymptotic complexity]] runs in {{math|O(''n''<sup>2.3728596</sup>)}} 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 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>{{citation
| last = Iliopoulos
| first = Costas S.
| doi = 10.1137/0218045
| issue = 4
| journal = SIAM Journal on Computing
| mr = 1004789
| quote = The Coppersmith–Winograd algorithm is not practical, due to the very large hidden constant in the upper bound on the number of multiplications required.
| pages = 658–669
| title = Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix
| url = http://www.williamstein.org/home/wstein/www/home/pernet/Papers/Hermite/Iliopoulos88.pdf
| volume = 18
| year = 1989
| citeseerx = 10.1.1.531.9309
| access-date = 2015-01-16
| archive-url = https://web.archive.org/web/20140305182030/http://www.williamstein.org/home/wstein/www/home/pernet/Papers/Hermite/Iliopoulos88.pdf
| archive-date = 2014-03-05
| url-status = dead
}}</ref><ref name="robinson">{{Citation | last=Robinson | first=Sara | title=Toward an Optimal Algorithm for Matrix Multiplication | url=https://archive.siam.org/pdf/news/174.pdf | date=November 2005 | journal=SIAM News | volume=38 | issue=9 | quote=Even if someone manages to prove one of the conjectures—thereby demonstrating that {{math|1=''ω'' = 2}}—the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. [...] the input matrices must be astronomically large for the difference in time to be apparent.}}</ref>
== Simple algorithms ==
If ''A'', ''B'' are {{math|''n'' × ''n''}} matrices over a field, then their product ''AB'' is also an {{math|''n'' × ''n''}} matrix over that field, defined entrywise as
:<math>
(AB)_{ij} = \sum_{k = 1}^n A_{ik} B_{kj}.
</math>
=== Schoolbook algorithm ===
{{For|implementation techniques (in particular parallel and distributed algorithms)|Matrix multiplication algorithm}}
The simplest approach to computing the product of two {{math|''n'' × ''n''}} matrices ''A'' and ''B'' is to compute the arithmetic expressions coming from the definition of matrix multiplication. In pseudocode:
input is A and B, both n by n matrices
initialize C to be an n by n matrix of all zeros
for i from 1 to n:
for j from 1 to n:
for k from 1 to n:
C[i][j] = C[i][j] + A[i][k]*B[k][j]
output C (as A*B)
This [[algorithm]] requires, in the [[worst-case complexity|worst case]], {{tmath|n^3}} multiplications of scalars and {{tmath|n^3 - n}} 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]] where field operations (addition and multiplication) take constant time (in practice, this is the case for [[floating point]] numbers, but not necessarily for integers).
=== Strassen's algorithm ===
{{Main|Strassen algorithm}}
Strassen's algorithm improves on naive matrix multiplication through a [[Divide-and-conquer algorithm|divide-and-conquer]] approach. The key observation is that multiplying two {{math|2 × 2}} matrices can be done with only 7 multiplications, instead of the usual 8 (at the expense of several additional addition and subtraction operations). This means that, treating the input {{math|''n''×''n''}} matrices as block {{math|2 × 2}} matrices, the task of multiplying {{math|''n''×''n''}} matrices can be reduced to 7 subproblems of multiplying {{math|''n/2''×''n/2''}} matrices. Applying this recursively gives an algorithm needing <math>O( n^{\log_{2}7}) \approx O(n^{2.807})</math> field operations.
Unlike algorithms with faster asymptotic complexity, Strassen's algorithm is used in practice. 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">{{cite book |first=Steven |last=Skiena |author-link=Steven Skiena |title=The Algorithm Design Manual |url=https://archive.org/details/algorithmdesignm00skie_772 |url-access=limited |publisher=Springer |year=2008 |pages=[https://archive.org/details/algorithmdesignm00skie_772/page/n56 45]–46, 401–403 |doi=10.1007/978-1-84800-070-4_4|chapter=Sorting and Searching |isbn=978-1-84800-069-8 }}</ref> 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 exponent ==
[[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>.]]
{| class="wikitable floatright"
|+ Timeline of matrix multiplication exponent
! Year !! Bound on omega !! Authors
|-
| 1969 || 2.8074 || [[Volker Strassen|Strassen]]<ref name="strassen69/>
|-
| 1978 || 2.796 || Pan<ref>
{{cite book
| doi=10.1109/SFCS.1978.34
| author=Victor Yakovlevich Pan
| author-link= Victor Pan
| contribution=Strassen's Algorithm is not Optimal: Trilinear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations
| title=Proc. 19th FOCS
| pages=166–176
| date=Oct 1978
| s2cid= 14348408
}}</ref>
|-
| 1979 || 2.780 || Bini, Capovani, Romani<ref>
{{cite journal
| doi=10.1016/0020-0190(79)90113-3
| url=https://www.sciencedirect.com/journal/information-processing-letters/vol/8/issue/5
| author1=Dario Andrea Bini
| author2= Milvio Capovani
| author3= Francesco Romani
| author4= Grazia Lotti
| title=<math>O(n^{2.7799})</math> complexity for <math>n \times n</math> approximate matrix multiplication
| journal=Information Processing Letters
| volume=8
| number=5
| pages=234–235
| date=Jun 1979
}}</ref>
|-
| 1981 || 2.522 || Schönhage<ref>
{{cite journal
| doi=10.1137/0210032
| author=A. Schönhage
| title=Partial and total matrix multiplication
| journal=SIAM Journal on Computing
| volume=10
| number=3
| pages=434–455
| year=1981
}}</ref>
|-
| 1981 || 2.517 || Romani<ref>
{{cite journal
| doi=10.1137/0211020
| author=Francesco Romani
| title=Some properties of disjoint sums of tensors related to matrix multiplication
| journal=SIAM Journal on Computing
| volume=11
| number=2
| pages=263–267
| year=1982
}}</ref><!-- Note: Romani and Coppersmith-Winograd do not cite each other, so these appear to be simultaneous. -->
|-
| 1981 || 2.496 || [[Don Coppersmith|Coppersmith]], [[Shmuel Winograd|Winograd]]<ref>
{{cite book
| doi=10.1109/SFCS.1981.27
| author1=D. Coppersmith
| author2= S. Winograd
| contribution=On the asymptotic complexity of matrix multiplication
| title=Proc. 22nd Annual Symposium on Foundations of Computer Science (FOCS)
| pages=82–90
| year=1981
| s2cid=206558664
}}</ref>
|-
| 1986 || 2.479 || [[Volker Strassen|Strassen]]<ref>
{{cite book
| doi=10.1109/SFCS.1986.52
| author=Volker Strassen
| contribution=The asymptotic spectrum of tensors and the exponent of matrix multiplication
| title=Proc. 27th Ann. Symp. on Foundation of Computer Science (FOCS)
| pages=49–54
| date=Oct 1986
| s2cid=15077423
}}</ref>
|-
| 1990 || 2.3755 || [[Don Coppersmith|Coppersmith]], [[Shmuel Winograd|Winograd]]<ref>
{{cite journal
| url=https://www.sciencedirect.com/science/article/pii/S0747717108800132
| author1=D. Coppersmith
| author2= S. Winograd
| title=Matrix multiplication via arithmetic progressions
| journal=Journal of Symbolic Computation
| volume=9
| number=3
| pages=251–280
| date=Mar 1990
| doi=10.1016/S0747-7171(08)80013-2
}}</ref>
|-
| 2010 || 2.3737 || Stothers<ref>
{{cite thesis
| type=Ph.D. thesis
| url=https://era.ed.ac.uk/handle/1842/4734
| last=Stothers
| first= Andrew James
| title=On the complexity of matrix multiplication
| institution=University of Edinburgh
| year=2010
}}</ref>
|-
| 2013 || 2.3729 || [[Virginia Vassilevska Williams|Williams]]<ref>
{{cite book
| doi=10.1145/2213977.2214056
| author=Virginia Vassilevska Williams
| contribution=Multiplying Matrices Faster than Coppersmith-Winograd
| editor1=Howard J. Karloff
| editor2= Toniann Pitassi
| title=Proc. 44th [[Symposium on Theory of Computing]] (STOC)
| publisher=ACM
| pages=887–898
| year=2012
}}</ref><ref name="Williams.2014">
{{cite report
| last=Williams
| first=Virginia Vassilevska
| author-link=Virginia Vassilevska Williams
| title=Multiplying matrices in <math>O(n^{2.373})</math> time
| institution=Stanford University
| type=Technical Report
| url=http://www.cs.stanford.edu/~virgi/matrixmult-f.pdf
}}</ref>
|-
| 2014 || 2.3728639 || Le Gall<ref name="LeGall2014">
{{Citation
| last1=Le Gall
| first1=François
| pages=296–303
| contribution=Powers of tensors and fast matrix multiplication
| year = 2014
| arxiv=1401.7714
| title = Proceedings of the 39th [[International Symposium on Symbolic and Algebraic Computation]] (ISSAC)
| editor=Katsusuke Nabeshima
| isbn=978-1-4503-2501-1
| bibcode=2014arXiv1401.7714L
}}</ref>
|-
| 2020 || 2.3728596 || Alman, [[Virginia Vassilevska Williams|Williams]]<ref name="aw20"/>
|}
The ''matrix multiplication exponent'', usually denoted {{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. This notation is commonly used in [[algorithm]]s research, algorithms using matrix multiplication as a subroutine have meaningful bounds on running time regardless of the true value of {{math|ω}}.
Using a naive lower bound and schoolbook matrix multiplication for the upper bound, one can straightforwardly conclude that {{math|2 ≤ ω ≤ 3}}. Whether {{math|1=ω = 2}} is a major open question in [[theoretical computer science]], and there is a line of research developing matrix multiplication algorithms to get improved bounds on {{math|ω}}.
The current best bound on {{math|ω}} is {{math|ω < 2.3728596}}, by Josh Alman and [[Virginia Vassilevska Williams]].<ref name="aw20"/> This algorithm, like all other recent algorithms in this line of research, uses the ''laser method'', a generalization of the Coppersmith–Winograd algorithm, which was given by [[Don Coppersmith]] and [[Shmuel Winograd]] in 1990, was the best matrix multiplication algorithm until 2010, and has an asymptotic complexity of {{math|''O''(''n''<sup>2.375477</sup>)}}.<ref name="coppersmith">{{Citation|doi=10.1016/S0747-7171(08)80013-2 |title=Matrix multiplication via arithmetic progressions |url=http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf |year=1990 |last1=Coppersmith |first1=Don |last2=Winograd |first2=Shmuel |journal=Journal of Symbolic Computation |volume=9|issue=3|pages=251}}</ref> The conceptual idea of these algorithms are similar to Strassen's algorithm: a way is devised for multiplying two {{math|''k'' × ''k''}}-matrices with fewer than {{math|''k''<sup>3</sup>}} multiplications, and this technique is applied recursively. The laser method has limitations to its power, and cannot be used to show that {{math|ω < 2.3725}}.<ref>{{Cite journal|last=Ambainis|first=Andris|last2=Filmus|first2=Yuval|last3=Le Gall|first3=François|date=2015-06-14|title=Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method|url=https://doi.org/10.1145/2746539.2746554|journal=Proceedings of the forty-seventh annual ACM symposium on Theory of Computing|series=STOC '15|___location=Portland, Oregon, USA|publisher=Association for Computing Machinery|pages=585–593|doi=10.1145/2746539.2746554|isbn=978-1-4503-3536-2}}</ref>
=== Group theory reformulation of matrix multiplication algorithms ===
[[Henry Cohn]], [[Robert Kleinberg]], [[Balázs Szegedy]] and [[Chris Umans]] put methods such as the Strassen and Coppersmith–Winograd algorithms in an entirely different [[group theory|group-theoretic]] context, by utilising triples of subsets of finite groups which satisfy a disjointness property called the [[Triple product property|triple product property (TPP)]]. They also give conjectures that, if true, would imply that there are matrix multiplication algorithms with essentially quadratic complexity. This implies that the optimal exponent of matrix multiplication is 2, which most researchers believe is indeed the case.<ref name="robinson"/> One such conjecture is that families of [[wreath product]]s of [[Abelian group]]s with symmetric groups realise families of subset triples with a simultaneous version of the TPP.<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><ref>Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. {{arxiv|math.GR/0307321}}. ''Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science'', 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438–449.</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> Further, Alon, Shpilka and [[Chris Umans]] have recently shown that some of these conjectures implying fast matrix multiplication are incompatible with another plausible conjecture, the [[sunflower conjecture]].<ref>[[Noga Alon|Alon]], Shpilka, Umans, [http://eccc.hpi-web.de/report/2011/067/ On Sunflowers and Matrix Multiplication]</ref>
=== Lower bounds for ω ===
There is a trivial lower bound of {{tmath|\omega \ge 2}}. Since any algorithm for multiplying two {{math|''n'' × ''n''}}-matrices has to process all {{math|2''n''<sup>2</sup>}} entries, there is a trivial asymptotic lower bound of {{math|Ω(''n''<sup>2</sup>)}} operations for any matrix multiplication algorithm. Thus {{tmath|2\le \omega < 2.373}}. It is unknown whether {{tmath|\omega > 2}}. The best known lower bound for matrix-multiplication complexity is {{math|Ω(''n''<sup>2</sup> log(''n''))}}, for bounded coefficient [[Arithmetic circuit complexity|arithmetic circuits]] over the real or complex numbers, and is due to [[Ran Raz]].<ref>{{cite journal | last1 = Raz | first1 = Ran | author-link = Ran Raz | year = 2002| title = On the complexity of matrix product | journal = Proceedings of the Thirty-fourth Annual ACM Symposium on Theory of Computing | pages = 144 | doi = 10.1145/509907.509932 | isbn = 1581134959 | s2cid = 9582328 }}</ref>
=== 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">{{Citation|last=Gall|first=Francois Le|title=Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor|date=2018-01-01|url=https://epubs.siam.org/doi/10.1137/1.9781611975031.67|work=Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)|pages=1029–1046|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611975031.67|access-date=2021-05-23|last2=Urrutia|first2=Florent|arxiv=1708.05622}}</ref> This generalizes the square matrix multiplication exponent, since <math>\omega(1) = \omega</math>.
Of interest is proving that, for values of ''k'' between 0 and 1, that <math>\omega(k) \leq 2</math>.
Since the output of the matrix multiplication problem is size <math>n^2</math>, <math>\omega(k) \geq 2</math> always, so these results show that <math>\omega(k) = 2</math> exactly. 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|last=Cohen|first=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}}</ref>
The first bound on ''α'' is by [[Don Coppersmith|Coppersmith]] in 1982, who showed that <math>\alpha > 0.17227</math>.<ref>{{Cite journal|last=Coppersmith|first=D.|date=1982-08-01|title=Rapid Multiplication of Rectangular Matrices|url=https://epubs.siam.org/doi/10.1137/0211037|journal=SIAM Journal on Computing|volume=11|issue=3|pages=467–471|doi=10.1137/0211037|issn=0097-5397}}</ref> The current best bound on ''α'' is <math>\alpha > 0.31389</math>, given by Le Gall and Urrutia.<ref>{{Citation|last=Le Gall|first=Francois|title=Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor|date=2018-01-01|url=https://epubs.siam.org/doi/10.1137/1.9781611975031.67|work=Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)|pages=1029–1046|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611975031.67|access-date=2021-05-23|last2=Urrutia|first2=Florent|arxiv=1708.05622}}</ref> This paper also contains bounds on <math>\omega(k)</math>.
==Related complexities==
{{further|Computational complexity of mathematical operations#Matrix algebra}}
Problems that have the same asymptotic complexity as matrix multiplication include [[determinant]], [[matrix inversion]], [[Gaussian elimination]] (see next section). Problems with complexity that is expressible in terms of <math>\omega</math> include characteristic polynomial, eigenvalues (but not eigenvectors), [[Hermite normal form]], and [[Smith normal form]].{{citation needed|date=March 2018}}
===Matrix inversion, determinant and Gaussian elimination===
In his 1969 paper, where he proved the complexity <math>O(n^{2.807})</math> for matrix computation, Strassen proved also that [[matrix inversion]], [[determinant]] and [[Gaussian elimination]] have, up to a multiplicative constant, the same [[computational complexity]] as matrix multiplication. The proof does not make any assumptions on matrix multiplication that is used, except that its complexity is <math>O(n^\omega)</math> for some <math>\omega \ge 2</math>
The starting point of Strassen's proof is using [[block matrix]] multiplication. Specifically, a matrix of even dimension {{math|2''n''×2''n''}} may be partitioned in four {{math|''n''×''n''}} blocks
:<math>\begin{bmatrix} {A} & {B} \\{C} & {D} \end{bmatrix}.</math>
Under this form, its inverse is
:<math>
\begin{bmatrix} {A} & {B} \\ {C} & {D} \end{bmatrix}^{-1} =
\begin{bmatrix}
{A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1} & -{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}
\\ -({D}-{CA}^{-1}{B})^{-1}{CA}^{-1} & ({D}-{CA}^{-1}{B})^{-1}
\end{bmatrix},
</math>
provided that {{mvar|A}} and <math>{D}-{CA}^{-1}{B}</math> are invertible.
Thus, the inverse of a {{math|2''n''×2''n''}} matrix may be computed with two inversions, six multiplications and four additions or additive inverses of {{math|''n''×''n''}} matrices. It follows that, denoting respectively by {{math|''I''(''n'')}}, {{math|''M''(''n'')}} and {{math|1= ''A''(''n'') = ''n''<sup>2</sup>}} the number of operations needed for inverting, multiplying and adding {{math|''n''×''n''}} matrices, one has
:<math>I(2n) \le 2I(n) + 6M(n)+ 4 A(n).</math>
If <math>n=2^k,</math> one may apply this formula recursively:
:<math>\begin{align}
I(2^k) &\le 2I(2^{k-1}) + 6M(2^{k-1})+ 4 A(2^{k-1})\\
&\le 2^2I(2^{k-2}) + 6(M(2^{k-1})+2M(2^{k-2})) + 4(A(2^{k-1}) + 2A(2^{k-2}))\\
&\ldots
\end{align}</math>
If <math>M(n)\le cn^\omega,</math> and <math>\alpha=2^\omega\ge 4,</math> one gets eventually
:<math>\begin{align}
I(2^k) &\le 2^k I(1) + 6c(\alpha^{k-1}+2\alpha^{k-2} + \cdots +2^{k-1}\alpha^0) + k 2^{k+1}\\
&\le 2^k + 6c\frac{\alpha^k-2^k}{\alpha-2} + k 2^{k+1}\\
&\le d(2^k)^\omega.
\end{align}</math>
for some constant {{mvar|d}}.
For matrices whose dimension is not a power of two, the same complexity is reached by increasing the dimension of the matrix to a power of two, by padding the matrix with rows and columns whose entries are 1 on the diagonal and 0 elsewhere.
This proves the asserted complexity for matrices such that all submatrices that have to be inverted are indeed invertible. This complexity is thus proved for almost all matrices, as a matrix with randomly chosen entries is invertible with probability one.
The same argument applies to [[LU decomposition]], as, if the matrix {{mvar|A}} is invertible, the equality
:<math>\begin{bmatrix} {A} & {B} \\{C} & {D} \end{bmatrix}
= \begin{bmatrix}I & 0\\CA^{-1}&I\end{bmatrix}\,\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}</math>
defines a block LU decomposition that may be applied recursively to <math>A</math> and <math>D-CA^{-1}B,</math> for getting eventually a true LU decomposition of the original matrix.
The argument applies also for the determinant, since it results from the block LU decomposition that
:<math>\det \begin{bmatrix} {A} & {B} \\{C} & {D} \end{bmatrix} =
\det(A)\det(D-CA^{-1}B).</math>
==See also==
* [[Computational complexity of mathematical operations]]
* [[CYK algorithm#Valiant's algorithm|CYK algorithm, §Valiant's algorithm]]
* [[Freivalds' algorithm]], a simple [[Monte Carlo algorithm]] that, given matrices {{mvar|A}}, {{mvar|B}} and {{mvar|C}}, verifies in {{math|Θ(''n''<sup>2</sup>)}} time if {{math|''AB'' {{=}} ''C''}}.
* [[Matrix chain multiplication]]
* [[Matrix multiplication]], for abstract definitions
* [[Matrix multiplication algorithm]], for practical implementation details
* [[Sparse matrix-vector multiplication]]
==References==
{{reflist|30em}}
[[Category:Unsolved problems in computer science]]
| |||