## 2.5 Strassen's Matrix Multiplication Algorithm Recall that [Algorithm 1.4](LiB0008.html#34) (Matrix Multiplication) multiplied two matrices strictly according to the definition of matrix multiplication. We showed that the time complexity of its number of multiplications is given by *T(n)* = *n*3, where *n* is the number of rows and columns in the matrices. We can also analyze the number of additions. As you will show in the exercises, after the algorithm is modified slightly, the time complexity of the number of additions is given by *T(n)* = *n*3− *n*2. Becuase both of these time complexities are in Θ (*n*3), the algorithm can become impractical fairly quickly. In 1969, Strassen published an algorithm whose time complexity is better than cubic in terms of both multiplications and additions/subtractions. The following example illustrates his method. Example 2.4****Suppose we want the product *C* of two 2 x 2 matrices, *A* and *B.* That is,  Strassen determined that if we let  the product *C* is given by  In the exercises, you will show that this is correct. **** To multiply two 2 x 2 matrices, Strassen's method requires seven multiplications and 18 additions/subtractions, whereas the straightforward method requires eight multiplications and four additions/subtractions. We have saved ourselves one multiplication at the expense of doing 14 additional additions or subtractions. This is not very impressive, and indeed it is not in the case of 2 x 2 matrices that Strassen's method is of value. Because the commutativity of multiplications is not used in Strassen's formulas, those formulas pertain to larger matrices that are each divided into four submatrices. First we divide the matrices *A* and *B*, as illustrated in [Figure 2.4](#ch02fig04). Assuming that *n* is a power of 2, the matrix *A*11, for example, is meant to represent the following submatrix of *A*:  [](fig2-4_0.jpg) Figure 2.4: The partitioning into submatrices in Strassen's algorithm. Using Strassen's method, first we compute  where our operations are now matrix addition and multiplication. In the same way, we compute *M*2 through *M*7. Next we compute  and *C*12, *C*21, and *C*22. Finally, the product *C* of *A* and *B* is obtained by combining the four submatrices *Cij.* The following example illustrates these steps. Example 2.5****Suppose that  [Figure 2.5](#ch02fig05) illustrates the partitioning in Strassen's method. The computations proceed as follows:  [](fig2-5_0.jpg) Figure 2.5: The partitioning in Strassen's algorithm with *n* = 4 and values given to the matrices. When the matrices are sufficiently small, we multiply in the standard way. In this example, we do this when *n* = 2. Therefore  After this, *M*2 through *M*7 are computed in the same way, and then the values of *C*11, *C*12, *C*21, and *C*22 are computed. They are combined to yield *C*. **** Next we present an algorithm for Strassen's method when *n* is a power of 2. Algorithm 2.8: Strassen****Problem: Determine the product of two *n* x *n* matrices where *n* is a power of 2. Inputs: an integer *n* that is a power of 2, and two *n* x *n* matrices *A* and *B*. Outputs: the product *C* of *A* and *B*. ``` void strassen (int n n × n_matrix A, n × n_matrix B, n × n_matrix& C) { if (n<=threshold) compute C = A × B using the standard algorithm; else{ partition A into four submatrices A11, A12, A21, A22; partition B into four submatrices B11, B12, B21, B22; compute C = A × B using Strassen's method; // example recursive call; // strassen (n/2, A11 + A22, B11 + B22, M1) } } ``` **** The value of *threshold* is the point at which we feel it is more efficient to use the standard algorithm than it would be to call procedure *Strassen* recursively. In [Section 2.7](LiB0021.html#223) we discuss a method for determining thresholds. ****Analysis of [Algorithm 2.8](#ch02ex19) Every-Case Time Complexity Analysis of Number of Multiplication (Strassen)Basic operation: one elementary multiplication. Input size: *n*, the number of rows and columns in the matrices. For simplicity, we analyze the case in which we keep dividing until we have two 1 × 1 matrices, at which point we simply multiply the numbers in each matrix. The actual threshold value used does not affect the order. When *n* = 1, exactly one multiplication is done. When we have two *n* × *n* matrices with *n* > 1, the algorithm is called exactly seven times with an (*n*/2) × (*n*/2) matrix passed each time, and no multiplications are done at the top level. We have established the recurrence  This recurrence is solved in Example B.2 in [Appendix B](LiB0102.html#1369). The solution is  **** ****Analysis of [Algorithm 2.8](#ch02ex19) Every-Case Time Complexity Analysis of Number of Additions/Subtractions (Strassen)Basic operation: one elementary addition or subtraction. Input size: *n*, the number of rows and columns in the matrices. Again we assume that we keep dividing until we have two 1 × 1 matrices. When *n* = 1, no additions/subtractions are done. When we have two *n* × *n* matrices with *n* > 1, the algorithm is called exactly seven times with an (*n*/2) × (*n*/2) matrix passed in each time, and 18 matrix additions/subtractions are done on (*n*/2) × (*n*/2) matrices. When two (*n*/2) × (*n*/2) matrices are added or subtracted, (*n*/2)2 additions or subtractions are done on the items in the matrices. We have established the recurrence  This recurrence is solved in Example B.20 in [Appendix B](LiB0102.html#1369). The solution is  **** When *n* is not a power of 2, we must modify the previous algorithm. One simple modification is to add sufficient numbers of columns and rows of 0s to the original matrices to make the dimension a power of 2. Alternatively, in the recursive calls we could add just one extra row and one extra column of 0s whenever the number of rows and columns is odd. Strassen (1969) suggested the following, more complex modification. We embed the matrices in larger ones with 2k*m* rows and columns, where *k* = \[lg*n* − 4\] and *m* = \[*n*/2k\] + 1. We use Strassen's method up to a ***threshold*** value of *m* and use the standard algorithm after reaching the threshold. It can be shown that the total number of arithmetic operations (multiplications, additions, and subtractions) is less than 4.7*n*2.81. [Table 2.3](#ch02table03)compares the time complexities of the standard algorithm and Strassen's algorithm for *n* a power of 2. If we ignore for the moment the overhead involved in the recursive calls, Strassen's algorithm is always more efficient in terms of multiplicaitons, and for large values of *n*, Strassen's algorithm is more efficient in terms of additions/subtractions. In [Section 2.7](LiB0021.html#223) we will discuss an analysis technique that accounts for the time taken by the recursive calls. Table 2.3: A comparison of two algorithms that multiply *n* × *n* matrices Standard Algorithm Strassen's Algorithm Multiplications *n*3 *n*2.81 Additions/Subtractions *n*3 – *n*2 6*n*2.81 – 6*n*2 Shmuel Winograd developed a variant of Strassen's algorithm that requires only 15 additions/subtractions. It appears in Brassard and Bratley (1988). For this algorithm, the time complexity of the additions/subtractions is given by  Coppersmith and Winograd (1987) developed a matrix multiplication algorithm whose time comlexity for the number of multiplications is in *O* (*n*2.38). However, the constant is so large that Strassen's algorithm is usually more efficient. It is possible to prove that matrix multiplication requires an algorithm whose time complexity is at least quadratic. Whether matrix multiplications can be done in quadratic time remains an open question; no one has ever created a quadratic-time algorithm for matrix multiplication, and no one has proven that it is not possible to create such an algorithm. One last point is that other matrix operations such as inverting a matrix and finding the determinant of a matrix are directly related to matrix multiplication. Therefore, we can readily create algorithms for these operations that are as efficient as Strassen's algorithm for matrix multiplication.