The algorithm

Time complexity

Error bounds

Strassen first presented his algorithm for matrix
multiplication in [15]. It is based on a recursive divide and conquer scheme.
Given *n* by n matrices *A* and *B* we wish to
calculate *C=AB*. To see how this algorithm works we first
divide the matrices as follows:

*P*_{1}* = (A*_{11}*+
A*_{22}*)(B*_{11}*+B*_{22}*) *

* P*_{2}* = (A*_{21}*
+ A*_{22}*) * B*_{11}* *

* P*_{3}* = A*_{11}*
* (B*_{12}* - B*_{22}*) *

* P*_{4}* = A*_{22}*
* (B*_{21}* - B*_{11}*) *

* P*_{5}* = (A*_{11}*
+ A*_{12}*) * B*_{22}* *

* P*_{6}* = (A*_{21}*
- A*_{11}*) * (B*_{11}*
+ B*_{12}*) *

* P*_{7}* = (A*_{12}*
- A*_{22}*) * (B*_{21}*
+ B*_{22}*) *

* *

*C*_{11}* = P*_{1}*
+ P*_{4}* - P*_{5}* + P*_{7}

* C*_{12}* = P*_{3}*
+ P*_{5}* *

* C*_{21}* = P*_{2}*
+ P*_{4}* *

* C*_{22}* = P*_{1}*
+ P*_{3}* - P*_{2}* + P*_{6}*
*

The correctness is easily verified by substitution.

Assume that *n=2m* then the blocks are *n*
by *n* and counting the number of multiplications one sees that
the method of Strassen with conventional multiplication at the block
level will use *7m*^{3} multiplications and *7m*^{3}*+11m*^{2}
additions. This should be compared to conventional matrix
multiplication that uses *(2m)*^{3} multiplies
and *(2m)*^{3}*-(2m)*^{2}
additions. Note that if *n=2*^{q} then it is
possible to user Strassen's method recursively on the blocks until the
block size is 1 at which time only scalar operations are required.
Because of lower order terms it is advisable to employ an ordinary
matrix multiplication routine when the dimension of the blocks reaches
some preset cutoff point *n*_{0}* > 7*
[9].
The complexity of this algorithm is *O(n*^{log 7}*)
= O(n*^{2.807}*)*, For the details see [8].

The numerical properties of this algorithm are
analyzed in [5] and more recently in [9]. The algorithm satisfies the
following error bound: