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:
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.
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].
The numerical properties of this algorithm are
analyzed in [5] and more recently in [9]. The algorithm satisfies the
following error bound: