Matrix multiplication algorithm


Because matrix multiplication is such a central operation in many numerical algorithms, 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. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors.
Directly applying the mathematical definition of matrix multiplication gives an algorithm that takes time on the order of to multiply two matrices. 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.

Iterative algorithm

The definition of matrix multiplication is that if for an matrix and an matrix, then is an matrix with entries
From this, a simple algorithm can be constructed which loops over the indices from 1 through and from 1 through, computing the above using a nested loop:

  • Input: matrices and
  • Let be a new matrix of the appropriate size
  • For from 1 to :
  • * For from 1 to :
  • ** Let
  • ** For from 1 to :
  • *** Set
  • ** Set
  • Return

This algorithm takes time . A common simplification for the purpose of algorithms analysis is to assume that the inputs are all square matrices of size, in which case the running time is, i.e., cubic.

Cache behavior

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 memory access patterns and cache use of the algorithm;
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 fully associative cache consisting of bytes and bytes per cache line, the above algorithm is sub-optimal for and stored in row-major order. When, every iteration of the inner loop incurs a cache miss when accessing an element of. This means that the algorithm incurs cache misses in the worst case., 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.
The optimal variant of the iterative algorithm for and in row-major layout is a tiled version, where the matrix is implicitly divided into square tiles of size by :

  • Input: matrices and
  • Let be a new matrix of the appropriate size
  • Pick a tile size
  • For from 1 to in steps of :
  • * For from 1 to in steps of :
  • ** For from 1 to in steps of :
  • *** Multiply and into, that is:
  • *** For from to :
  • **** For from to :
  • ***** Let
  • ***** For from to :
  • ****** Set
  • ***** Set
  • Return

In the idealized cache model, this algorithm incurs only cache misses; the divisor amounts to several orders of magnitude on modern machines, so that the actual calculations dominate the running time, rather than the cache misses.

Divide and conquer algorithm

An alternative to the iterative algorithm is the divide and conquer algorithm for matrix multiplication. This relies on the block partitioning
which works for all square matrices whose dimensions are powers of two, i.e., the shapes are for some. The matrix product is now
which consists of eight multiplications of pairs of submatrices, followed by an addition step. The divide and conquer algorithm computes the smaller multiplications recursively, using the scalar multiplication as its base case.
The complexity of this algorithm as a function of is given by the recurrence
accounting for the eight recursive calls on matrices of size and to sum the four pairs of resulting matrices element-wise. Application of the master theorem for divide-and-conquer recurrences shows this recursion to have the solution, the same as the iterative algorithm.

Non-square matrices

A variant of this algorithm that works for matrices of arbitrary shapes and is faster in practice splits matrices in two instead of four submatrices, as follows.
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.

  • Inputs: matrices of size, of size.
  • Base case: if is below some threshold, use an unrolled version of the iterative algorithm.
  • Recursive cases:

Cache behavior

The cache miss rate of recursive matrix multiplication is the same as that of a tiled iterative version, but unlike that algorithm, the recursive algorithm is cache-oblivious: 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.
The number of cache misses incurred by this algorithm, on a machine with lines of ideal cache, each of size bytes, is bounded by

Sub-cubic algorithms

Algorithms exist that provide better running times than the straightforward ones. The first to be discovered was 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 -matrices which requires only 7 multiplications, at the expense of several additional addition and subtraction operations. Applying this recursively gives an algorithm with a multiplicative cost of. Strassen's algorithm is more complex, and the numerical stability is reduced compared to the naïve algorithm,
but it is faster in cases where or so and appears in several libraries, such as BLAS. It is very useful for large matrices over exact domains such as finite fields, where numerical stability is not an issue.
The current algorithm with the lowest known exponent is a generalization of the Coppersmith–Winograd algorithm that has an asymptotic complexity of, by François Le Gall. 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 -matrices with fewer than 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.
Since any algorithm for multiplying two -matrices has to process all entries, there is an asymptotic lower bound of operations. Raz proved a lower bound of for bounded coefficient arithmetic circuits over the real or complex numbers.
Cohn et al. put methods such as the Strassen and Coppersmith–Winograd algorithms in an entirely different group-theoretic context, by utilising triples of subsets of finite groups which satisfy a disjointness property called the triple product property. They show that if families of wreath products of Abelian groups 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. Most researchers believe that this is indeed the case. 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.
Freivalds' algorithm is a simple Monte Carlo algorithm that, given matrices, and, verifies in time if.

Parallel and distributed algorithms

Shared-memory parallelism

The divide and conquer algorithm sketched earlier can be parallelized in two ways for shared-memory multiprocessors. These are based on the fact that the eight recursive matrix multiplications in
can be performed independently of each other, as can the four summations. Exploiting the full parallelism of the problem, one obtains an algorithm that can be expressed in fork–join style pseudocode:

Procedure :
  • Base case: if, set .
  • Otherwise, allocate space for a new matrix of shape, then:
  • * Partition into,,,.
  • * Partition into,,,.
  • * Partition into,,,.
  • * Partition into,,,.
  • * Parallel execution:
  • ** Fork.
  • ** Fork.
  • ** Fork.
  • ** Fork.
  • ** Fork.
  • ** Fork.
  • ** Fork.
  • ** Fork.
  • * Join.
  • *.
  • * Deallocate.
Procedure adds into, element-wise:
  • Base case: if, set .
  • Otherwise:
  • * Partition into,,,.
  • * Partition into,,,.
  • * In parallel:
  • ** Fork.
  • ** Fork.
  • ** Fork.
  • ** Fork.
  • * Join.

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. achieves its goal by pointer manipulation only.
This algorithm has a critical path length of 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 on any real computer. The algorithm isn't practical due to the communication cost inherent in moving data to and from the temporary matrix, but a more practical variant achieves speedup, without using a temporary matrix.

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 communication bandwidth.
Cannon's algorithm, also known as the 2D algorithm, is a communication-avoiding algorithm that partitions each input matrix into a block matrix whose elements are submatrices of size by, where is the size of fast memory. The naïve algorithm is then used over the block matrices, computing products of submatrices entirely in fast memory. This reduces communication bandwidth to, which is asymptotically optimal.
In a distributed setting with processors arranged in a by 2D mesh, one submatrix of the result can be assigned to each processor, and the product can be computed with each processor transmitting words, which is asymptotically optimal assuming that each node stores the minimum elements. 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. This algorithm transmits words per processor, which is asymptotically optimal. However, this requires replicating each input matrix element times, and so requires a factor of more memory than is needed to store the inputs. This algorithm can be combined with Strassen to further reduce runtime. "2.5D" algorithms provide a continuous tradeoff between memory usage and communication bandwidth. On modern distributed computing environments such as MapReduce, specialized multiplication algorithms have been developed.

Algorithms for meshes

There are a variety of algorithms for multiplication on 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 3n-2 steps although this is reduced to half this number for repeated computations. 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 2n-1 steps are needed. The performance improves further for repeated computations leading to 100% efficiency. The cross-wired mesh array may be seen as a special case of a non-planar processing structure.