# 4.2 Strassen's algorithm for matrix multiplication

## 4.2-1

Use Strassen's algorithm to compute the matrix product

$$\begin{pmatrix} 1 & 3 \\ 7 & 5 \end{pmatrix} \begin{pmatrix} 6 & 8 \\ 4 & 2 \end{pmatrix} .$$

The first matrices are

$$\begin{array}{ll} S_1 = 6 & S_6 = 8 \\ S_2 = 4 & S_7 = -2 \\ S_3 = 12 & S_8 = 6 \\ S_4 = -2 & S_9 = -6 \\ S_5 = 6 & S_{10} = 14. \end{array}$$

The products are

\begin{aligned} P_1 & = 1 \cdot 6 = 6 \\ P_2 & = 4 \cdot 2 = 8 \\ P_3 & = 6 \cdot 12 = 72 \\ P_4 & = -2 \cdot 5 = -10 \\ P_5 & = 6 \cdot 8 = 48 \\ P_6 & = -2 \cdot 6 = -12 \\ P_7 & = -6 \cdot 14 = -84. \end{aligned}

The four matrices are

\begin{aligned} C_{11} & = 48 + (-10) - 8 + (-12) = 18 \\ C_{12} & = 6 + 8 = 14 \\ C_{21} & = 72 + (-10) = 62 \\ C_{22} & = 48 + 6 - 72 - (-84) = 66. \end{aligned}

The result is

$$\begin{pmatrix} 18 & 14 \\ 62 & 66 \end{pmatrix} .$$

## 4.2-2

Write pseudocode for Strassen's algorithm.

$$A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} , B = \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix} , C = \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix} . \tag{4.9}$$

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 STRASSEN(A, B) n = A.rows let C be a new n × n matrix if n == 1 c[1, 1] = a[1, 1] * b[1, 1] else partition A and B in equations (4.9) let C[1, 1], C[1, 2], C[2, 1], and C[2, 2] be n / 2 × n / 2 matrices create n / 2 × n / 2 matrices S[1], S[2], ..., S[10] and P[1], P[2], ..., P[7] S[1] = B[1, 2] - B[2, 2] S[2] = A[1, 1] + A[1, 2] S[3] = A[1, 2] + A[2, 2] S[4] = B[2, 1] - B[1, 1] S[5] = A[1, 1] + A[2, 2] S[6] = B[1, 1] + B[2, 2] S[7] = A[1, 2] - A[2, 2] S[8] = B[2, 1] + B[2, 2] S[9] = A[1, 1] - A[2, 1] S[10] = B[1, 1] + B[1, 2] P[1] = STRASSEN(A[1, 1], S[1]) P[2] = STRASSEN(S[2], B[2, 2]) P[3] = STRASSEN(S[3], B[1, 1]) P[4] = STRASSEN(A[2, 2], S[4]) P[5] = STRASSEN(S[5], S[6]) P[6] = STRASSEN(S[7], S[8]) P[7] = STRASSEN(S[9], S[10]) C[1, 1] = P[5] + P[4] - P[2] + P[6] C[1, 2] = P[1] + P[2] C[2, 1] = P[3] + P[4] C[2, 2] = P[5] + P[1] - P[3] - P[7] combine C[1, 1], C[1, 2], C[2, 1], and C[2, 2] into C return C 

## 4.2-3

How would you modify Strassen's algorithm to multiply $n \times n$ matrices in which $n$ is not an exact power of $2$? Show that the resulting algorithm runs in time $\Theta(n^{\lg7})$.

We can just extend it to an $n \times n$ matrix and pad it with zeroes. It's obviously $\Theta(n^{\lg7})$.

## 4.2-4

What is the largest $k$ such that if you can multiply $3 \times 3$ matrices using $k$ multiplications (not assuming commutativity of multiplication), then you can multiply $n \times n$ matrices is time $o(n^{\lg 7})$? What would the running time of this algorithm be?

If you can multiply $3 \times 3$ matrices using $k$ multiplications, then you can multiply $n \times n$ matrices by recursively multiplying $n / 3 \times n /3$ matrices, in time $T(n) = kT(n / 3) + \Theta(n^2)$.

Using the master method to solve this recurrence, consider the ratio of $n^{\log_3 k}$ and $n^2$:

• If $\log_3 k = 2$, case 2 applies and $T(n) = \Theta(n^2\lg n)$. In this case, $k = 9$ and $T(n) = o(n^{\lg 7})$.
• If $\log_3 k < 2$, case 3 applies and $T(n) = \Theta(n^2)$. In this case, $k < 9$ and $T(n) = o(n^{\lg 7})$.
• If $\log_3 k > 2$, case 1 applies and $T(n) = \Theta(n^{\log_3 k})$. In this case, $k > 9$. $T(n) = o(n^{\lg 7})$ when $\log_3 k < \lg 7$, i.e., when $k < 3^{\lg 7} \approx 21.85$. The largest such integer $k$ is $21$.

Thus, $k = 21$ and the running time is $\Theta(n^{\log_3 k}) = \Theta(n^{\log_3 21} = O(n^{2.80})$ (since $\log_3 21 \approx 2.77$).

## 4.2-5

V. Pan has discovered a way of multiplying $68 \times 68$ matrices using $132464$ multiplications, a way of multiplying $70 \times 70$ matrices using $143640$ multiplications, and a way of multiplying $72 \times 72$ matrices using $155424$ multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? How does it compare to Strassen's algorithm?

Using what we know from the last exercise, we need to pick the smallest of the following

\begin{aligned} \log_{68} 132464 & \approx 2.795128 \\ \log_{70} 143640 & \approx 2.795122 \\ \log_{72} 155424 & \approx 2.795147. \end{aligned}

The fastest one asymptotically is $70 \times 70$ using $143640$.

## 4.2-6

How quickly can you multiply a $kn \times n$ matrix by an $n \times kn$ matrix, using Strassen's algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.

• $(kn \times n)(n \times kn)$ produces a $kn \times kn$ matrix. This produces $k^2$ multiplications of $n \times n$ matrices.
• $(n \times kn)(kn \times n)$ produces an $n \times n$ matrix. This produces $k$ multiplications and $k - 1$ additions.

## 4.2-7

Show how to multiply the complex numbers $a + bi$ and $c + di$ using only three multiplications of real numbers. The algorithm should take $a$, $b$, $c$ and $d$ as input and produce the real component $ac - bd$ and the imaginary component $ad + bc$ separately.

The three matrices are

\begin{aligned} A & = (a + b)(c + d) = ac + ad + bc + bd \\ B & = ac \\ C & = bd. \end{aligned}

The result is

$$(B - C) + (A - B - C)i.$$