Chapter 4: Matrix Multiplication and Strassen

Source files used: Matrix Multiplication (Recitation 1, Sections 2 and 3.2); textbook Chapter 4 (chap4, Sections 4.1 and 4.2) as support. No worked examples are included.

1. Big Picture

Strassen’s algorithm is the recitation’s showcase for divide and conquer: a constant saving per level (7 multiplications instead of 8) changes the exponent of the running time.

The Convex Hull guide asked: how do you make the merge step cheap? This guide asks: how do you make the recursion tree less bushy?

$$\boxed{\text{Trade one recursive multiplication for extra additions: }8T(n/2)\to7T(n/2).}$$

New ideas:

• standard multiplication is $\Theta(n^3)$,
• naive block divide and conquer is still $\Theta(n^3)$,
• Strassen’s seven products $M_1,\dots,M_7$,
• $T(n)=7T(n/2)+\Theta(n^2)=\Theta(n^{\lg7})\approx\Theta(n^{2.807})$.

---

2. Core Ideas

2.1 Standard Multiplication

Entry $(i,j)$ of $C=AB$ is row $i$ of $A$ times column $j$ of $B$. For square $n\times n$ matrices this takes $\Theta(n^3)$: $n^2$ entries, each a sum of $n$ products.

---

2.2 Size Is the Dimension $n$

Running time is measured in terms of the dimension $n$, not the number of entries $n^2$. Splitting into four blocks halves $n$, so subproblems are $T(n/2)$, not $T(n/4)$.

This is a common exam trap when writing the recurrence.

---

2.3 Addition Is Cheap, Multiplication Is Expensive

Adding two $n\times n$ matrices costs $\Theta(n^2)$; multiplying costs much more. So saving a multiplication at the cost of a constant number of extra additions pays off.

Textbook analogy: $x^2-y^2=(x+y)(x-y)$ uses one multiplication instead of two, at the cost of an extra addition. For scalars this gains nothing; for large matrices it does.

---

2.4 Padding to a Power of 2

The recitation makes $A$ and $B$ each $2^k\times2^k$ by filling the extra rows and columns with 0. This is allowed because:

• each dimension grows by less than a factor of 2,
• even with $\Theta(n^3)$ multiplication, that costs less than a factor of 8, a constant.

Strip the extra zero rows and columns from $C$ at the end. Powers of 2 are needed (not just even sizes) because the recursion halves the dimension at every level.

---

2.5 Strassen Is Not the Fastest Known

Strassen was a powerful early application of divide and conquer and was the fastest method when discovered. Later work by Coppersmith, Winograd, Stothers, and Vassilevska Williams gives faster methods.

---

3. Main Governing Equations and Formulas

3.1 Entry Formula

$$c_{ij}=\sum_{k=1}^{n}a_{ik}b_{kj}$$

Three nested loops, $\Theta(n^3)$.

---

3.2 Block Partition

$$A=\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix},\quad B=\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix},\quad C=\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}$$

Each block has dimension $n/2$.

---

3.3 Block Product: 8 Multiplications

$$C_{11}=A_{11}B_{11}+A_{12}B_{21}$$ $$C_{12}=A_{11}B_{12}+A_{12}B_{22}$$ $$C_{21}=A_{21}B_{11}+A_{22}B_{21}$$ $$C_{22}=A_{21}B_{12}+A_{22}B_{22}$$

Recurrence (textbook, partitioning by index calculation in $\Theta(1)$):

$$T(n)=8T(n/2)+\Theta(1)=\Theta(n^3)$$

No improvement over three loops. Eight children per node makes a very bushy recursion tree.

---

3.4 Strassen’s Seven Products (Recitation Form)

$$M_1=(A_{11}+A_{22})(B_{11}+B_{22})$$ $$M_2=(A_{21}+A_{22})B_{11}$$ $$M_3=A_{11}(B_{12}-B_{22})$$ $$M_4=A_{22}(B_{21}-B_{11})$$ $$M_5=(A_{11}+A_{12})B_{22}$$ $$M_6=(A_{21}-A_{11})(B_{11}+B_{12})$$ $$M_7=(A_{12}-A_{22})(B_{21}+B_{22})$$

Each $M_i$ is computed recursively with Strassen.

---

3.5 Recombining into $C$

$$C_{11}=M_1+M_4-M_5+M_7$$ $$C_{12}=M_3+M_5$$ $$C_{21}=M_2+M_4$$ $$C_{22}=M_1-M_2+M_3+M_6$$

Correctness follows from expanding the products. Memory aid: $C_{12}$ and $C_{21}$ are each a sum of two products; $C_{11}$ and $C_{22}$ each use $M_1$ plus three others.

The textbook writes the same algorithm with ten sums $S_1,\dots,S_{10}$ and products $P_1,\dots,P_7$. The count is identical; use the recitation’s $M_1,\dots,M_7$ form.

---

3.6 Operation Count per Level

$$7\text{ multiplications}+18\text{ additions/subtractions}$$

(10 additions inside the $M_i$, 8 in the recombination.)

For small matrices this is worse than 8 multiplications: splitting a 2-element matrix into 1-element blocks is over triple the work. In practice, switch to the standard method below some size.

---

3.7 Strassen Recurrence

$$T(n)=7T(n/2)+18\,\Theta(n^2)=7T(n/2)+\Theta(n^2)$$

Watershed $n^{\log_2 7}$ is polynomially larger than $n^2$, so case 1:

$$T(n)=\Theta(n^{\log_2 7})\approx\Theta(n^{2.8074})$$

The textbook writes this as $O(n^{2.81})$.

---

3.8 Beating Strassen with a Different Split

For a D&C method with $a$ subproblems of dimension $n/b$ and $\Theta(n^2)$ combine work, the time is $\Theta(n^{\log_b a})$ whenever $\log_b a>2$. It beats Strassen if and only if

$$\log_b a<\lg 7$$

Example (textbook Exercise 4.5-2): splitting into $n/4$ blocks beats Strassen only if $a<4^{\lg 7}=49$, so at most 48 subproblems.

Use for “could this design be faster than Strassen?” questions.

---

4. Problem-Solving Workflow

1. Write the cost of the standard method: $\Theta(n^3)$.
2. If $n$ is not a power of 2, pad with zeros to $2^k$ (constant-factor cost).
3. Partition into four $n/2\times n/2$ blocks.
4. Compute $M_1,\dots,M_7$ recursively (Section 3.4).
5. Combine into $C_{11},C_{12},C_{21},C_{22}$ with additions only (Section 3.5).
6. Strip the padding.
7. Write the recurrence in terms of the dimension: $T(n)=7T(n/2)+\Theta(n^2)$.
8. Solve with case 1 of the master theorem: $\Theta(n^{\lg 7})$.

---

5. Decision Rules / Decision Trees

5.1 Which Recurrence?

Naive block method (8 products)? → $T(n)=8T(n/2)+\Theta(1)=\Theta(n^3)$

Strassen (7 products)? → $T(n)=7T(n/2)+\Theta(n^2)=\Theta(n^{\lg7})$

Subproblem written as $T(n/4)$ because there are 4 blocks? → wrong: size is the dimension, use $T(n/2)$

5.2 Does the Combine Work Matter?

Combine work $\Theta(n^2)$, watershed $n^{\log_b a}$ with $\log_b a>2$? → combine work does not affect the answer (case 1)

Watershed equals $n^2$? → case 2, extra $\lg n$ factor

5.3 Strassen in Practice

Small matrices? → standard method; 18 additions dominate

Large matrices? → Strassen; the saved multiplication dominates

---

6. Important Tables / Correlations Needed

6.1 Methods Compared

Method	Products per level	Recurrence	Time
Three nested loops	(not recursive)	none	$\Theta(n^3)$
Block D&C	8	$8T(n/2)+\Theta(1)$	$\Theta(n^3)$
Strassen	7	$7T(n/2)+\Theta(n^2)$	$\Theta(n^{\lg7})\approx n^{2.807}$

6.2 Strassen Cheat Sheet

Product	Formula	Used in
$M_1$	$(A_{11}+A_{22})(B_{11}+B_{22})$	$C_{11}$, $C_{22}$
$M_2$	$(A_{21}+A_{22})B_{11}$	$C_{21}$, $C_{22}$
$M_3$	$A_{11}(B_{12}-B_{22})$	$C_{12}$, $C_{22}$
$M_4$	$A_{22}(B_{21}-B_{11})$	$C_{11}$, $C_{21}$
$M_5$	$(A_{11}+A_{12})B_{22}$	$C_{11}$, $C_{12}$
$M_6$	$(A_{21}-A_{11})(B_{11}+B_{12})$	$C_{22}$
$M_7$	$(A_{12}-A_{22})(B_{21}+B_{22})$	$C_{11}$

---

7. Key Takeaways

• Standard matrix multiplication is $\Theta(n^3)$.
• Measure size by the dimension $n$: four blocks means $T(n/2)$, not $T(n/4)$.
• Naive block D&C: $8T(n/2)+\Theta(1)=\Theta(n^3)$, no gain.
• Strassen: 7 multiplications and 18 additions per level.
• $T(n)=7T(n/2)+\Theta(n^2)=\Theta(n^{\lg7})\approx\Theta(n^{2.807})$ by case 1.
• Pad to $2^k\times2^k$ with zeros; the cost is a constant factor.
• Memorize $M_1$ to $M_7$ and the four recombination formulas.
• Strassen loses on small matrices because of the extra additions.
• A design beats Strassen exactly when $\log_b a<\lg7$.
• Strassen is not the fastest known method today.