## Statement

Let and . Let and be two square matrices of order and with coefficients in . The classical algorithm for computing the matrix product uses operations in . The Strassen algorithm provides the lower asymptotic upper bound . As for the Karatsuba algorithm, the trick relies on a smart use of distributivity:
If the matrices et are of the form et where , such that equals .
If the matrices and can be decomposed as

where and are square matrices of order . Them, one computes the following 8 sums.

Next, one computes the following 7 matrix products by recursive calls to the algorithm.

Finally, one computes the following 7 sums:

and one returns:

Marc Moreno Maza
2008-03-18