The Strassen algorithm

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:

It is assumed that each block is square. This can be achieved by padding the matrices. Strassen showed how C can be computed using only 7 block multiplications and 18 block adds:

P1 = (A11+ A22)(B11+B22)
P2 = (A21 + A22) * B11
P3 = A11 * (B12 - B22)
P4 = A22 * (B21 - B11)
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)

C11 = P1 + P4 - P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 + P3 - P2 + P6

The correctness is easily verified by substitution.

Top of page.

Time Complexity

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 7m3 multiplications and 7m3+11m2 additions. This should be compared to conventional matrix multiplication that uses (2m)3 multiplies and (2m)3-(2m)2 additions. Note that if n=2q 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 n0 > 7 [9]. The complexity of this algorithm is O(nlog 7) = O(n2.807), For the details see [8].

Top of page.

Numerical Properties

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

where n0 < n+1 is the cutoff point of 4 where an ordinary matrix algorithm should be applied. This should be compared with standard multiplication

The error bound is somewhat weaker, but may still be regarded as acceptable unless small, componentwise relative errors are required.