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
.
Then, 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