Stassen’s Matrix Multiplication

Let A and B be two n x n matrices. The product matrix C= AB is also an n x n matrix whose i,jth element is formed by taking the elements in the ith row of A and the jth column of Band multiplying them to get for all i and j between 1 and n. To compute C(i,j) using this formula, we need n multiplications.As the matrix C has n^2 elements,the time for the resulting matrix multiplication algorithm,which we refer to as the conventional method is theta(n^3).

The divide-and-conquer strategy suggests another way to compute the product of two n x n matrices. For simplicity we assume that n is a power of 2, that is,that there exists a non negative integer k such that n = 2^k. In case? i is not a power of two, then enough rows and columns of zero scan be added to both A and B so that the resulting dimensions area power of two (see the exercises for more on this subject). Imagine that A and B are each partitioned into four square sub matrices, each sub matrix having dimensions n/2*n/2. Then the product AB can be computed by using the above formula for the product of 2 x 2 matrices: if AB is

If n = 2, then formulas (a) and (b) are computed using a multiplication operation for the elements of A and B. These elements are typically floating point numbers. For n > 2, the elements of C can be computed using matrix multiplication and addition operations applied to matrices of size n/2 * n/2. Since n is a power of 2, these matrix products can be recursively computed by the same algorithm we are using for the n*n case. This algorithm will continue applying itself to smaller-sized sub matrices until n becomes suitably small(n = 2) so that the product is computed directly.

To compute AB using (3.12), we need to perform eight multiplications of n/2*n/2 matrices and four additions of n/2*n/2 matrices. Since two n/2*n/2 matrices can be added in time cn^2 for some constant c,the overall computing time T(n) of the resulting divide-and-conquer algorithm is given by the recurrence

where b and c are constants.

This recurrence can be solved in the same way as earlier recurrences to obtain T(n)= 0(n^3). Hence no improvement over the conventional method has been made. Since matrix multiplications are more expensive than matrix additions (0(n^3) versus 0(n^2)),we can attempt to reformulate the equations for Cij so as to have fewer multiplications and possibly more additions. Volker Strassen has discovered a way to compute the Cij’s of (formula b) using only 7 multiplications and 18 additions or subtractions. His method involves first computing the seven n/2*n/2 matrices P, Q, R, S, T, U, and V as in (formula c).Then the Cij’s are computed using the formulas in (formula d). As can be seen P, Q, R, S, T, U, and V can be computed using 7 matrix multiplications and 10 matrix additions or subtractions. The Cij’s require an additional 8 additions or subtraction.