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
20080318