View source for Matrix multiplication algorithm

{{short description|Algorithm to multiply matrices}}
{{unsolved|computer science|What is the fastest algorithm for matrix multiplication?}}
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''<sup>3</sup>}} to multiply two {{math|''n'' × ''n''}} matrices ({{math|Θ(''n''<sup>3</sup>)}} in [[big O notation]]). Better asymptotic bounds on the time required to multiply matrices have been known since the work of Strassen in the 1960s, but it is still unknown what the optimal time is (i.e., what the [[Computational complexity theory|complexity of the problem]] is).

==Iterative algorithm==
The [[Matrix multiplication#General definition of the matrix product|definition of matrix multiplication]] is that if {{math|''C'' {{=}} ''AB''}} for an {{math|''n'' × ''m''}} matrix {{mvar|A}} and an {{math|''m'' × ''p''}} matrix {{mvar|B}}, then {{mvar|C}} is an {{math|''n'' × ''p''}} matrix with entries

:<math>c_{ij} = \sum_{k=1}^m a_{ik} b_{kj}</math>.

From this, a simple algorithm can be constructed which loops over the indices {{mvar|i}} from 1 through {{mvar|n}} and {{mvar|j}} from 1 through {{mvar|p}}, computing the above using a nested loop:

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Input: matrices {{mvar|A}} and {{mvar|B}}
* Let {{mvar|C}} be a new matrix of the appropriate size
* For {{mvar|i}} from 1 to {{mvar|n}}:
** For {{mvar|j}} from 1 to {{mvar|p}}:
*** Let {{math|sum {{=}} 0}}
*** For {{mvar|k}} from 1 to {{mvar|m}}:
**** Set {{math|sum ← sum + ''A<sub>ik</sub>'' × ''B<sub>kj</sub>''}}
*** Set {{math|''C<sub>ij</sub>'' ← sum}}
* Return {{mvar|C}}
{{frame-footer}}
</div>

This algorithm takes [[time complexity|time]] {{math|Θ(''nmp'')}} (in [[asymptotic notation]]).<ref name="skiena"/> A common simplification for the purpose of [[analysis of algorithms|algorithms analysis]] is to assume that the inputs are all square matrices of size {{math|''n'' × ''n''}}, in which case the running time is {{math|Θ(''n''<sup>3</sup>)}}, i.e., cubic.<ref name="clrs">{{Introduction to Algorithms|3|pages=75–79}}</ref>

===Cache behavior===
[[File:Row_and_column_major_order.svg|thumb|upright|Illustration of row- and column-major order]]
The three loops in iterative matrix multiplication can be arbitrarily swapped with each other without an effect on correctness or asymptotic running time. However, the order can have a considerable impact on practical performance due to the [[locality of reference|memory access patterns]] and [[CPU cache|cache]] use of the algorithm;<ref name="skiena">{{cite book |first=Steven |last=Skiena |authorlink=Steven Skiena |title=The Algorithm Design Manual |publisher=Springer |year=2008 |pages=45–46, 401–403 |doi=10.1007/978-1-84800-070-4_4|chapter=Sorting and Searching |isbn=978-1-84800-069-8 }}</ref>
which order is best also depends on whether the matrices are stored in [[row-major order]], column-major order, or a mix of both.

In particular, in the idealized case of a [[CPU cache#Associativity|fully associative cache]] consisting of {{mvar|M}} bytes and {{mvar|b}} bytes per cache line (i.e. {{sfrac|''M''|''b''}} cache lines), the above algorithm is sub-optimal for {{mvar|A}} and {{mvar|B}} stored in row-major order. When {{math|''n'' > {{sfrac|''M''|''b''}}}}, every iteration of the inner loop (a simultaneous sweep through a row of {{mvar|A}} and a column of {{mvar|B}}) incurs a cache miss when accessing an element of {{mvar|B}}. This means that the algorithm incurs {{math|Θ(''n''<sup>3</sup>)}} cache misses in the worst case. {{As of|2010}}, the speed of memories compared to that of processors is such that the cache misses, rather than the actual calculations, dominate the running time for sizable matrices.<ref name="ocw">{{cite web|url=http://aka-ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/|title=6.172 Performance Engineering of Software Systems, Lecture 8|last1=Amarasinghe|first1=Saman|last2=Leiserson|first2=Charles|date=|year=2010|website=MIT OpenCourseWare|publisher=Massachusetts Institute of Technology|url-status=live|archive-url=|archive-date=|accessdate=27 January 2015}}</ref>

The optimal variant of the iterative algorithm for {{mvar|A}} and {{mvar|B}} in row-major layout is a ''[[loop tiling|tiled]]'' version, where the matrix is implicitly divided into square tiles of size {{math|{{radic|''M''}}}} by {{math|{{radic|''M''}}}}:<ref name="ocw"/><ref>{{cite conference |first1=Monica S. |last1=Lam |first2=Edward E. |last2=Rothberg |first3=Michael E. |last3=Wolf |title=The Cache Performance and Optimizations of Blocked Algorithms |conference=Int'l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS) |year=1991}}</ref>

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Input: matrices {{mvar|A}} and {{mvar|B}}
* Let {{mvar|C}} be a new matrix of the appropriate size
* Pick a tile size {{math|''T'' {{=}} Θ({{radic|''M''}})}}
* For {{mvar|I}} from 1 to {{mvar|n}} in steps of {{mvar|T}}:
** For {{mvar|J}} from 1 to {{mvar|p}} in steps of {{mvar|T}}:
*** For {{mvar|K}} from 1 to {{mvar|m}} in steps of {{mvar|T}}:
**** Multiply {{math|''A''<sub>''I'':''I''+''T'', ''K'':''K''+''T''</sub>}} and {{math|''B''<sub>''K'':''K''+''T'', ''J'':''J''+''T''</sub>}} into {{math|''C''<sub>''I'':''I''+''T'', ''J'':''J''+''T''</sub>}}, that is:
**** For {{mvar|i}} from {{mvar|I}} to {{math|min(''I'' + ''T'', ''n'')}}:
***** For {{mvar|j}} from {{mvar|J}} to {{math|min(''J'' + ''T'', ''p'')}}:
****** Let {{math|sum {{=}} 0}}
****** For {{mvar|k}} from {{mvar|K}} to {{math|min(''K'' + ''T'', ''m'')}}:
******* Set {{math|sum ← sum + ''A<sub>ik</sub>'' × ''B<sub>kj</sub>''}}
****** Set {{math|''C<sub>ij</sub>'' ← ''C<sub>ij</sub>'' + sum}}
* Return {{mvar|C}}
{{frame-footer}}
</div>

In the idealized cache model, this algorithm incurs only {{math|Θ({{sfrac|''n''<sup>3</sup>|''b'' {{radic|''M''}}}})}} cache misses; the divisor {{math|''b'' {{radic|''M''}}}} amounts to several orders of magnitude on modern machines, so that the actual calculations dominate the running time, rather than the cache misses.<ref name="ocw"/>

==Divide and conquer algorithm==
An alternative to the iterative algorithm is the [[divide and conquer algorithm]] for matrix multiplication. This relies on the [[block matrix|block partitioning]]

:<math>C = \begin{pmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22} \\
\end{pmatrix},\,
A = \begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22} \\
\end{pmatrix},\,
B = \begin{pmatrix}
B_{11} & B_{12} \\
B_{21} & B_{22} \\
\end{pmatrix}</math>.

which works for all square matrices whose dimensions are powers of two, i.e., the shapes are {{math|2<sup>''n''</sup> × 2<sup>''n''</sup>}} for some {{mvar|n}}. The matrix product is now

:<math>\begin{pmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22} \\
\end{pmatrix} =
\begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22} \\
\end{pmatrix} \begin{pmatrix}
B_{11} & B_{12} \\
B_{21} & B_{22} \\
\end{pmatrix} = \begin{pmatrix}
A_{11} B_{11} + A_{12} B_{21} & A_{11} B_{12} + A_{12} B_{22}\\
A_{21} B_{11} + A_{22} B_{21} & A_{21} B_{12} + A_{22} B_{22}\\
\end{pmatrix}
</math>

which consists of eight multiplications of pairs of submatrices, followed by an addition step. The divide and conquer algorithm computes the smaller multiplications [[recursion|recursively]], using the [[scalar multiplication]] {{math|''c''<sub>11</sub> {{=}} ''a''<sub>11</sub>''b''<sub>11</sub>}} as its base case.

The complexity of this algorithm as a function of {{mvar|n}} is given by the recurrence<ref name="clrs"/>

:<math>T(1) = \Theta(1)</math>;
:<math>T(n) = 8T(n/2) + \Theta(n^2)</math>,

accounting for the eight recursive calls on matrices of size {{math|''n''/2}} and {{math|Θ(''n''<sup>2</sup>)}} to sum the four pairs of resulting matrices element-wise. Application of the [[master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]] shows this recursion to have the solution {{math|Θ(''n''<sup>3</sup>)}}, the same as the iterative algorithm.<ref name="clrs"/>

===Non-square matrices===
A variant of this algorithm that works for matrices of arbitrary shapes and is faster in practice<ref name="ocw"/> splits matrices in two instead of four submatrices, as follows.<ref name="prokop">{{cite thesis |type=Master's |first=Harald |last=Prokop |authorlink=Harald Prokop |title=Cache-Oblivious Algorithms |publisher=MIT |year=1999 |url=http://supertech.csail.mit.edu/papers/Prokop99.pdf}}</ref>
Splitting a matrix now means dividing it into two parts of equal size, or as close to equal sizes as possible in the case of odd dimensions.

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Inputs: matrices {{mvar|A}} of size {{math|''n'' × ''m''}}, {{mvar|B}} of size {{math|''m'' × ''p''}}.
* Base case: if {{math|max(''n'', ''m'', ''p'')}} is below some threshold, use an [[loop unrolling|unrolled]] version of the iterative algorithm.
* Recursive cases:

:* If {{math|max(''n'', ''m'', ''p'') {{=}} ''n''}}, split {{mvar|A}} horizontally:

::<math>C = \begin{pmatrix} A_1 \\ A_2 \end{pmatrix} {B}
          = \begin{pmatrix} A_1 B \\ A_2 B \end{pmatrix}</math>

:* Else, if {{math|max(''n'', ''m'', ''p'') {{=}} ''p''}}, split {{mvar|B}} vertically:

::<math>C = A \begin{pmatrix} B_1 & B_2 \end{pmatrix}
          = \begin{pmatrix} A B_1 & A B_2 \end{pmatrix}  </math>

:* Otherwise, {{math|max(''n'', ''m'', ''p'') {{=}} ''m''}}. Split {{mvar|A}} vertically and {{mvar|B}} horizontally:

::<math>C = \begin{pmatrix} A_1 & A_2 \end{pmatrix} \begin{pmatrix} B_1 \\ B_2 \end{pmatrix}
          = A_1 B_1 + A_2 B_2</math>
{{frame-footer}}
</div>

===Cache behavior===
The cache miss rate of recursive matrix multiplication is the same as that of a [[Loop tiling|tiled]] iterative version, but unlike that algorithm, the recursive algorithm is [[Cache-oblivious matrix multiplication|cache-oblivious]]:<ref name="prokop"/> there is no tuning parameter required to get optimal cache performance, and it behaves well in a [[multiprogramming]] environment where cache sizes are effectively dynamic due to other processes taking up cache space.<ref name="ocw"/>
(The simple iterative algorithm is cache-oblivious as well, but much slower in practice if the matrix layout is not adapted to the algorithm.)

The number of cache misses incurred by this algorithm, on a machine with {{mvar|M}} lines of ideal cache, each of size {{mvar|b}} bytes, is bounded by{{r|prokop}}{{rp|13}}

:<math>\Theta \left(m + n + p + \frac{mn + np + mp}{b} + \frac{mnp}{b\sqrt{M}} \right)</math>

==Sub-cubic algorithms==
[[File:Bound on matrix multiplication omega over time.svg|thumb|400px|right|The lowest {{mvar|ω}} such that matrix multiplication is known to be in {{math|''O''(''n<sup>ω</sup>'')}}, plotted against time.]]

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 | pages=97–107}}</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=108|title-link=Numerical Recipes }}</ref> It is very useful for large matrices over exact domains such as finite fields, where numerical stability is not an issue.

The current {{math|''O''(''n''<sup>''k''</sup>)}} algorithm with the lowest known exponent {{mvar|k}} is a generalization of the [[Coppersmith–Winograd algorithm]] that has an asymptotic complexity of {{math|''O''(''n''<sup>2.3728639</sup>)}}, by François Le Gall.<ref>{{Citation | last1=Le Gall | first1=François | 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 2014)| bibcode=2014arXiv1401.7714L }}. The original algorithm was presented by [[Don Coppersmith]] and [[Shmuel Winograd]] in 1990, has an asymptotic complexity of {{math|''O''(''n''<sup>2.376</sup>)}}. It was improved in 2013 to {{math|''O''(''n''<sup>2.3729</sup>)}} by [[Virginia Vassilevska Williams]], giving a time only slightly worse than Le Gall's improvement: {{cite web |url=http://www.cs.stanford.edu/~virgi/matrixmult-f.pdf |title=Multiplying matrices faster than Coppersmith-Winograd |first=Virginia Vassilevska |last=Williams|authorlink= Virginia Vassilevska Williams}}</ref>  The Le Gall algorithm, and the Coppersmith–Winograd algorithm on which it is based, 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. However, the constant coefficient hidden by the [[Big O notation]] is so large that these algorithms 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
 }}</ref><ref name="robinson">{{Cite journal | last1=Robinson | first1=Sara | title=Toward an Optimal Algorithm for Matrix Multiplication | url=https://archive.siam.org/pdf/news/174.pdf | year=2005 | journal=SIAM News | volume=38 | issue=9}}</ref>

Since any algorithm for multiplying two {{math|''n'' × ''n''}}-matrices has to process all {{math|2''n''<sup>2</sup>}} entries, there is an asymptotic lower bound of {{math|Ω(''n''<sup>2</sup>)}} operations. Raz proved a lower bound of {{math|Ω(''n''<sup>2</sup> log(''n''))}} for bounded coefficient arithmetic circuits over the real or complex numbers.<ref>[[Ran Raz]]. On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002. {{doi|10.1145/509907.509932}}.</ref>

Cohn ''et al.'' 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 show that if families of [[wreath product]]s of [[Abelian group]]s with symmetric groups realise families of subset triples with a simultaneous version of the TPP, then there are matrix multiplication algorithms with essentially quadratic complexity.<ref>Henry Cohn, [[Robert Kleinberg]], [[Balázs Szegedy]], and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. {{arxiv|math.GR/0511460}}. ''Proceedings of the 46th Annual Symposium on Foundations of Computer Science'', 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp.&nbsp;379–388.</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.&nbsp;438–449.</ref> Most researchers believe that this is indeed the case.<ref name="robinson"/> However, 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>

[[Freivalds' algorithm]] is 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''}}.

==Parallel and distributed algorithms==

===Shared-memory parallelism===
The [[#Divide and conquer algorithm|divide and conquer algorithm]] sketched earlier can be [[parallel algorithm|parallelized]] in two ways for [[shared-memory multiprocessor]]s. These are based on the fact that the eight recursive matrix multiplications in

:<math>\begin{pmatrix}
A_{11} B_{11} + A_{12} B_{21} & A_{11} B_{12} + A_{12} B_{22}\\
A_{21} B_{11} + A_{22} B_{21} & A_{21} B_{12} + A_{22} B_{22}\\
\end{pmatrix}
</math>

can be performed independently of each other, as can the four summations (although the algorithm needs to "join" the multiplications before doing the summations). Exploiting the full parallelism of the problem, one obtains an algorithm that can be expressed in [[fork–join model|fork–join style]] [[pseudocode]]:<ref name="cilk"/>

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
'''Procedure''' {{math|multiply(''C'', ''A'', ''B'')}}:

* Base case: if {{math|''n'' {{=}} 1}}, set {{math|''c''<sub>11</sub> ← ''a''<sub>11</sub> × ''b''<sub>11</sub>}} (or multiply a small block matrix).
* Otherwise, allocate space for a new matrix {{mvar|T}} of shape {{math|''n'' × ''n''}}, then:
** Partition {{mvar|A}} into {{math|''A''<sub>11</sub>}}, {{math|''A''<sub>12</sub>}}, {{math|''A''<sub>21</sub>}}, {{math|''A''<sub>22</sub>}}.
** Partition {{mvar|B}} into {{math|''B''<sub>11</sub>}}, {{math|''B''<sub>12</sub>}}, {{math|''B''<sub>21</sub>}}, {{math|''B''<sub>22</sub>}}.
** Partition {{mvar|C}} into {{math|''C''<sub>11</sub>}}, {{math|''C''<sub>12</sub>}}, {{math|''C''<sub>21</sub>}}, {{math|''C''<sub>22</sub>}}.
** Partition {{mvar|T}} into {{math|''T''<sub>11</sub>}}, {{math|''T''<sub>12</sub>}}, {{math|''T''<sub>21</sub>}}, {{math|''T''<sub>22</sub>}}.
** Parallel execution:
*** ''Fork'' {{math|multiply(''C''<sub>11</sub>, ''A''<sub>11</sub>, ''B''<sub>11</sub>)}}.
*** ''Fork'' {{math|multiply(''C''<sub>12</sub>, ''A''<sub>11</sub>, ''B''<sub>12</sub>)}}.
*** ''Fork'' {{math|multiply(''C''<sub>21</sub>, ''A''<sub>21</sub>, ''B''<sub>11</sub>)}}.
*** ''Fork'' {{math|multiply(''C''<sub>22</sub>, ''A''<sub>21</sub>, ''B''<sub>12</sub>)}}.
*** ''Fork'' {{math|multiply(''T''<sub>11</sub>, ''A''<sub>12</sub>, ''B''<sub>21</sub>)}}.
*** ''Fork'' {{math|multiply(''T''<sub>12</sub>, ''A''<sub>12</sub>, ''B''<sub>22</sub>)}}.
*** ''Fork'' {{math|multiply(''T''<sub>21</sub>, ''A''<sub>22</sub>, ''B''<sub>21</sub>)}}.
*** ''Fork'' {{math|multiply(''T''<sub>22</sub>, ''A''<sub>22</sub>, ''B''<sub>22</sub>)}}.
** ''Join'' (wait for parallel forks to complete).
** {{math|add(''C'', ''T'')}}.
** Deallocate {{mvar|T}}.

'''Procedure''' {{math|add(''C'', ''T'')}} adds {{mvar|T}} into {{mvar|C}}, element-wise:

* Base case: if {{math|''n'' {{=}} 1}}, set {{math|''c''<sub>11</sub> ← ''c''<sub>11</sub> + ''t''<sub>11</sub>}} (or do a short loop, perhaps unrolled).
* Otherwise:
** Partition {{mvar|C}} into {{math|''C''<sub>11</sub>}}, {{math|''C''<sub>12</sub>}}, {{math|''C''<sub>21</sub>}}, {{math|''C''<sub>22</sub>}}.
** Partition {{mvar|T}} into {{math|''T''<sub>11</sub>}}, {{math|''T''<sub>12</sub>}}, {{math|''T''<sub>21</sub>}}, {{math|''T''<sub>22</sub>}}.
** In parallel:
*** ''Fork'' {{math|add(''C''<sub>11</sub>, ''T''<sub>11</sub>)}}.
*** ''Fork'' {{math|add(''C''<sub>12</sub>, ''T''<sub>12</sub>)}}.
*** ''Fork'' {{math|add(''C''<sub>21</sub>, ''T''<sub>21</sub>)}}.
*** ''Fork'' {{math|add(''C''<sub>22</sub>, ''T''<sub>22</sub>)}}.
** ''Join''.
{{frame-footer}}
</div>

Here, ''fork'' is a keyword that signal a computation may be run in parallel with the rest of the function call, while ''join'' waits for all previously "forked" computations to complete. {{math|partition}} achieves its goal by pointer manipulation only.

This algorithm has a [[critical path length]] of {{math|Θ(log<sup>2</sup> ''n'')}} steps, meaning it takes that much time on an ideal machine with an infinite number of processors; therefore, it has a maximum possible [[speedup]] of {{math|Θ(''n''<sup>3</sup>/log<sup>2</sup> ''n'')}} on any real computer. The algorithm isn't practical due to the communication cost inherent in moving data to and from the temporary matrix {{mvar|T}}, but a more practical variant achieves {{math|Θ(''n''<sup>2</sup>)}} speedup, without using a temporary matrix.<ref name="cilk">{{cite thesis |type=Ph.D. |last=Randall |first=Keith H. |title=Cilk: Efficient Multithreaded Computing |publisher=Massachusetts Institute of Technology |year=1998 |pages=54–57 |url=http://supertech.csail.mit.edu/papers/randall-phdthesis.pdf}}</ref>

[[File:Block matrix multiplication.svg|thumb|Block matrix multiplication. In the 2D algorithm, each processor is responsible for one submatrix of {{mvar|C}}. In the 3D algorithm, every pair of submatrices from {{mvar|A}} and {{mvar|B}} that is multiplied is assigned to one processor.]]

===Communication-avoiding and distributed algorithms===
On modern architectures with hierarchical memory, the cost of loading and storing input matrix elements tends to dominate the cost of arithmetic. On a single machine this is the amount of data transferred between RAM and cache, while on a distributed memory multi-node machine it is the amount transferred between nodes; in either case it is called the ''communication bandwidth''. The naïve algorithm using three nested loops uses {{math|Ω(''n''<sup>3</sup>)}} communication bandwidth.

[[Cannon's algorithm]], also known as the ''2D algorithm'', is a [[Communication-Avoiding Algorithms|communication-avoiding algorithm]] that partitions each input matrix into a block matrix whose elements are submatrices of size {{math|{{sqrt|''M''/3}}}} by {{math|{{sqrt|''M''/3}}}}, where {{math|''M''}} is the size of fast memory.<ref>Lynn Elliot Cannon, ''[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=905686 A cellular computer to implement the Kalman Filter Algorithm]'', Technical report, Ph.D. Thesis, Montana State University, 14 July 1969.</ref> The naïve algorithm is then used over the block matrices, computing products of submatrices entirely in fast memory. This reduces communication bandwidth to {{math|''O''(''n''<sup>3</sup>/{{sqrt|''M''}})}}, which is asymptotically optimal (for algorithms performing {{math|Ω(''n''<sup>3</sup>)}} computation).<ref>{{cite journal|last=Hong|first=J. W.|first2=H. T. |last2=Kung|title=I/O complexity: The red-blue pebble game|journal=STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing|year=1981|pages=326–333|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a104739.pdf}}</ref><ref name=irony>{{cite journal|last=Irony|first=Dror|first2=Sivan |last2=Toledo |first3=Alexander |last3=Tiskin |title=Communication lower bounds for distributed-memory matrix multiplication|journal=J. Parallel Distrib. Comput.|date=September 2004|volume=64|issue=9|pages=1017–1026|doi=10.1016/j.jpdc.2004.03.021|citeseerx=10.1.1.20.7034}}</ref>

In a distributed setting with {{mvar|p}} processors arranged in a {{math|{{sqrt|''p''}}}} by {{math|{{sqrt|''p''}}}} 2D mesh, one submatrix of the result can be assigned to each processor, and the product can be computed with each processor transmitting {{math|''O''(''n''<sup>2</sup>/{{sqrt|''p''}})}} words, which is asymptotically optimal assuming that each node stores the minimum {{math|''O''(''n''<sup>2</sup>/''p'')}} elements.<ref name=irony/> This can be improved by the ''3D algorithm,'' which arranges the processors in a 3D cube mesh, assigning every product of two input submatrices to a single processor. The result submatrices are then generated by performing a reduction over each row.<ref name="Agarwal">{{cite journal|last=Agarwal|first=R.C.|first2=S. M. |last2=Balle |first3=F. G. |last3=Gustavson |first4=M. |last4=Joshi |first5=P. |last5=Palkar |title=A three-dimensional approach to parallel matrix multiplication|journal=IBM J. Res. Dev.|date=September 1995|volume=39|issue=5|pages=575–582|doi=10.1147/rd.395.0575|citeseerx=10.1.1.44.3404}}</ref> This algorithm transmits {{math|''O''(''n''<sup>2</sup>/''p''<sup>2/3</sup>)}} words per processor, which is asymptotically optimal.<ref name=irony/> However, this requires replicating each input matrix element {{math|''p''<sup>1/3</sup>}} times, and so requires a factor of {{math|''p''<sup>1/3</sup>}} more memory than is needed to store the inputs. This algorithm can be combined with Strassen to further reduce runtime.<ref name="Agarwal"/> "2.5D" algorithms provide a continuous tradeoff between memory usage and communication bandwidth.<ref>{{cite journal|last=Solomonik|first=Edgar|first2=James |last2=Demmel|title=Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms|journal=Proceedings of the 17th International Conference on Parallel Processing|year=2011|volume=Part II|pages=90–109}}</ref> On modern distributed computing environments such as [[MapReduce]], specialized multiplication algorithms have been developed.<ref>{{cite journal|last1=Bosagh Zadeh|first1=Reza|last2=Carlsson|first2=Gunnar|title=Dimension Independent Matrix Square Using MapReduce|url=http://stanford.edu/~rezab/papers/dimsum.pdf|accessdate=12 July 2014}}</ref>

===Algorithms for meshes===
There are a variety of algorithms for multiplication on [[Mesh networking|meshes]]. For multiplication of two ''n''×''n'' on a standard two-dimensional mesh using the 2D [[Cannon's algorithm]], one can complete the multiplication in 3''n''-2 steps although this is reduced to half this number for repeated computations.<ref>Bae, S.E., T.-W. Shinn, T. Takaoka (2014) [https://www.sciencedirect.com/science/article/pii/S1877050914003858/pdf?md5=4d641ad288db14733fb2f82ee445c258&pid=1-s2.0-S1877050914003858-main.pdf&_valck=1 A faster parallel algorithm for matrix multiplication on a mesh array]. Procedia Computer Science 29: 2230-2240</ref> The standard array is inefficient because the data from the two matrices does not arrive simultaneously and it must  be padded with zeroes.

The result is even faster on a two-layered cross-wired mesh, where only 2''n''-1 steps are needed.<ref>Kak, S. (1988) [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.8527&rep=rep1&type=pdf A two-layered mesh array for matrix multiplication]. Parallel Computing 6: 383-385</ref> The performance improves further for repeated computations leading to 100% efficiency.<ref>Kak, S. (2014) Efficiency of matrix multiplication on the cross-wired mesh array. https://arxiv.org/abs/1411.3273</ref> The cross-wired mesh array may be seen as a special case of a non-planar (i.e. multilayered) processing structure.<ref>Kak, S. (1988) [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.4753&rep=rep1&type=pdf Multilayered array computing]. Information Sciences 45: 347-365</ref>
[[File:Matrix multiplication on a cross-wire two-dimensional array.png|thumb|240px|Matrix multiplication completed in 2n-1 steps for two n×n matrices on a cross-wired  mesh.]]

==See also==
* [[Computational complexity of mathematical operations]]
* [[CYK algorithm#Valiant's algorithm|CYK algorithm, §Valiant's algorithm]]
* [[Matrix chain multiplication]]
* [[Sparse matrix-vector multiplication]]

==References==
{{reflist|30em}}

==Further reading==
* {{Cite journal| doi = 10.1016/j.parco.2008.10.002| title = A class of parallel tiled linear algebra algorithms for multicore architectures| journal = Parallel Computing| volume = 35| pages = 38–53| year = 2009| last1 = Buttari | first1 = Alfredo| last2 = Langou | first2 = Julien| last3 = Kurzak | first3 = Jakub| last4 = Dongarra | first4 = Jack |authorlink4=Jack Dongarra| arxiv = 0709.1272}}
* {{Cite journal | doi = 10.1145/1356052.1356053| title = Anatomy of high-performance matrix multiplication| journal = ACM Transactions on Mathematical Software| volume = 34| issue = 3| pages =1–25| year = 2008| last1 = Goto | first1 = Kazushige| last2 = van de Geijn | first2 = Robert A.| citeseerx = 10.1.1.140.3583}}
* {{Cite journal | doi = 10.1145/2764454 | title = BLIS: A Framework for Rapidly Instantiating BLAS Functionality| journal = ACM Transactions on Mathematical Software| volume = 41| issue = 3| pages =1–33| year = 2015| last1 = Van Zee  | first1 = Field G.| last2 = van de Geijn | first2 = Robert A.}}
* [https://github.com/flame/how-to-optimize-gemm How To Optimize GEMM]

{{Numerical linear algebra}}

[[Category:Matrix multiplication algorithms| ]]