Strassen’s Matrix Multiplication

Multiplication of Large Integers and Strassen’s Matrix Multiplication

In this section, we examine two surprising algorithms for seemingly straightfor-ward tasks: multiplying two integers and multiplying two square matrices. Both achieve a better asymptotic efficiency by ingenious application of the divide-and-conquer technique.

Strassen’s Matrix Multiplication

Now that we have seen that the divide-and-conquer approach can reduce the number of one-digit multiplications in multiplying two integers, we should not be surprised that a similar feat can be accomplished for multiplying matrices. Such an algorithm was published by V. Strassen in 1969 [Str69]. The principal insight of the algorithm lies in the discovery that we can find the product C of two 2 × 2 matrices A and B with just seven multiplications as opposed to the eight required by the brute-force algorithm (see Example 3 in Section 2.3). This is accomplished by using the following formulas:

Thus, to multiply two 2 × 2 matrices, Strassen’s algorithm makes seven multipli-cations and 18 additions/subtractions, whereas the brute-force algorithm requires eight multiplications and four additions. These numbers should not lead us to multiplying 2 × 2 matrices by Strassen’s algorithm. Its importance stems from its asymptotic superiority as matrix order n goes to infinity.

Let A and B be two n × n matrices where n is a power of 2. (If n is not a power of 2, matrices can be padded with rows and columns of zeros.) We can divide A, B, and their product C into four n/2 × n/2 submatrices each as follows:

It is not difficult to verify that one can treat these submatrices as numbers to get the correct product. For example, C₀₀ can be computed either as A₀₀ ∗ B₀₀ +

A₀₁ ∗ B₁₀ or as M₁ + M₄ − M₅ + M₇ where M₁, M₄, M₅, and M₇ are found by Strassen’s formulas, with the numbers replaced by the corresponding submatrices.

If the seven products of n/2 × n/2 matrices are computed recursively by the same method, we have Strassen’s algorithm for matrix multiplication.

Let us evaluate the asymptotic efficiency of this algorithm. If M(n) is the number of multiplications made by Strassen’s algorithm in multiplying two n × n matrices (where n is a power of 2), we get the following recurrence relation for it:

which is smaller than n³ required by the brute-force algorithm.

Since this savings in the number of multiplications was achieved at the expense of making extra additions, we must check the number of additions A(n) made by Strassen’s algorithm. To multiply two matrices of order n > 1, the algorithm needs to multiply seven matrices of order n/2 and make 18 additions/subtractions of matrices of size n/2; when n = 1, no additions are made since two numbers are

simply multiplied. These observations yield the following recurrence relation:

A(n) = 7A(n/2) + 18(n/2)²                for n > 1,   A(1) = 0.

Though one can obtain a closed-form solution to this recurrence (see Problem 8 in this section’s exercises), here we simply establish the solution’s order of growth. According to the Master Theorem, A(n) ∈ (n^{log 2 7}). In other words, the number of additions has the same order of growth as the number of multiplications. This puts Strassen’s algorithm in (n^{log2 7}), which is a better efficiency class than (n³) of the brute-force method.

Since the time of Strassen’s discovery, several other algorithms for multiplying two n × n matrices of real numbers in O(n^α) time with progressively smaller constants α have been invented. The fastest algorithm so far is that of Coopersmith and Winograd [Coo87] with its efficiency in O(n^2.376). The decreasing values of the exponents have been obtained at the expense of the increasing complexity of these algorithms. Because of large multiplicative constants, none of them is of practical value. However, they are interesting from a theoretical point of view. On one hand, they get closer and closer to the best theoretical lower bound known for matrix multiplication, which is n² multiplications, though the gap between this bound and the best available algorithm remains unresolved. On the other hand, matrix multiplication is known to be computationally equivalent to some other important problems, such as solving systems of linear equations (discussed in the next chapter).

Exercises 5.4

         What are the smallest and largest numbers of digits the product of two decimal n-digit integers can have?

         Compute 2101 ∗ 1130 by applying the divide-and-conquer algorithm outlined in the text.

         a.  Prove the equality a^{logb c} = c^{logb a}, which was used in Section 5.4.

         Why is n^{log2 3} better than 3^{log2 n} as a closed-form formula for M(n)?

                 a. Why did we not include multiplications by 10ⁿ in the multiplication count M(n) of the large-integer multiplication algorithm?

         In addition to assuming that n is a power of 2, we made, for the sake of simplicity, another, more subtle, assumption in setting up the recurrences for M(n) and A(n), which is not always true (it does not change the final answers, however). What is this assumption?

         How many one-digit additions are made by the pen-and-pencil algorithm in multiplying two n-digit integers? You may disregard potential carries.

Verify the formulas underlying Strassen’s algorithm for multiplying 2 × 2 matrices.

7. Apply Strassen’s algorithm to compute

 exiting the recursion when n = 2, i.e., computing the products of 2 × 2 matrices by the brute-force algorithm.

        Solve the recurrence for the number of additions required by Strassen’s algo-rithm. Assume that n is a power of 2.

        V. Pan [Pan78] has discovered a divide-and-conquer matrix multiplication algorithm that is based on multiplying two 70 × 70 matrices using 143,640 multiplications. Find the asymptotic efficiency of Pan’s algorithm (you may ignore additions) and compare it with that of Strassen’s algorithm.

            Practical implementations of Strassen’s algorithm usually switch to the brute-force method after matrix sizes become smaller than some crossover point. Run an experiment to determine such a crossover point on your computer system.