Strassen's Matrix Multiplication

1. Why do we need Strassen's algorithm?

Suppose we want to multiply two $n \times n$ matrices:

C = A \times B

In the ordinary method, every element of C is obtained by multiplying a row of A with a column of B.

There are n^2 elements in C, and each element requires n multiplications.

Therefore:

n^^{2} \times n = n^^{3}

So ordinary matrix multiplication takes:

Θ(n^3)

This seems natural because matrix multiplication appears to require n^3 scalar multiplications. Strassen's important result was that this is not necessary.

2. First understand the ordinary divide-and-conquer method

Suppose A and B are $4 \times 4$ matrices.

We divide each matrix into four $2 \times 2$ blocks:

A = [A_{11} A_{12}

A21 A_{22}]

and

B = [B_{11} B_{12}

B_{21} B_{22}]

The result is:

C = [C_{11} C_{12}

C_{21} C_{22}]

3. How do we calculate C?

Using ordinary block matrix multiplication:

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}

Now count the multiplications.

For C11


A11 × B11
A12 × B21

→ 2 multiplications.

Similarly:


C12 → 2 multiplications
C21 → 2 multiplications
C22 → 2 multiplications

Therefore:

2 + 2 + 2 + 2 = 8

So the ordinary divide-and-conquer algorithm performs:

8 recursive matrix multiplications

Therefore, the recurrence is:

T(n) = 8T(n/2) + Θ(n²)

The Θ(n²) term comes from the matrix additions required to combine the results.

Using the recurrence, we obtain:

T(n) = Θ(n³)

So ordinary divide-and-conquer does not improve the asymptotic complexity of conventional matrix multiplication.

4. The Big Idea of Strassen

Now comes the clever idea.

Instead of performing 8 multiplications, Strassen finds a way to perform only:

7 multiplications

But to do this, he performs some additional matrix additions and subtractions.

So Strassen makes this trade:

One less multiplication, at the cost of several additions/subtractions.

This is the central idea of Strassen's algorithm.

5. Why is reducing one multiplication useful?

You might ask:

"Why bother reducing 8 multiplications to 7? We are only saving one!"

The important point is that these are recursive multiplications of large matrices.

For an $n \times n$ matrix, the eight multiplications are actually:

8 multiplications of (n /2) \times (n /2) matrices

Strassen reduces this to:

7 multiplications of (n /2) \times (n /2) matrices

Then each of those is again reduced from 8 to 7, and so on.

Therefore the saving occurs at every level of the recursion tree.

That is what gives the asymptotic improvement.

6. A simple algebra analogy

Suppose we want:

$x^^{2} - y^^{2}$

The obvious method is:

$x^^{2} - y^^{2}$

which requires:

$x \times x$
$y \times y$
subtraction

So there are 2 multiplications.

But algebra tells us:

$x^^{2} - y^^{2} = (x + y) (x - y)$

Now we can calculate:

$x + y$ and $x - y$

and then:

$(x + y) (x - y)$

Only one multiplication is needed.

We have replaced:

2 multiplications

with:

1 multiplication + 2 additions/subtractions

This analogy is used to motivate Strassen's strategy.

7. Strassen applies the same idea to matrices

We have:

A = [A_{11} A_{12}

A_{21} A_{22}]

and

B = [B_{11} B_{12}

B_{21} B_{22}]

Instead of directly computing the 8 products, Strassen first creates 10 temporary matrices:

S1,S2,…,S10

using additions and subtractions.

8. The 10 S matrices

Matrix	Calculation
S1	$B_{12} - B_{22}$
S2	$A_{11} + A_{12}$
S3	$A_{21} + A_{22}$
S4	$B_{21} - B_{11}$
S5	$A_{11} + A_{22}$
S6	$B_{11} + B_{22}$
S7	$A_{12} - A_{22}$
S8	$B_{21} + B_{22}$
S9	$A_{11} - A_{21}$
S10	$B_{11} + B_{12}$

9. Now calculate only 7 products

Using these S matrices, Strassen computes:

P_{1} = A_{11} S_{1}

P_{2} = S_{2} B_{22}

P_{3} = S_{3} B_{11}

P_{4} = A_{22} S_{4}

P_{5} = S_{5} S_{6}

P_{6} = S_{7} S_{8}

P_{7} = S_{9} S_{10}

Therefore:

7 matrix multiplications

instead of 8.

These as the seven recursive products.

10. How do these 7 products give the answer?

The four blocks of C are obtained as follows:

C11

C11=P5+P4−P2+P6

C12

C12=P1+P2

C21

C21=P3+P4

C22

C22=P5+P1−P3−P7

These are the combinations given in CLRS.

11. Let's verify one of them

Students usually understand Strassen much better if we verify one equation instead of memorizing all four.

Take:

C_{12} = P_{1} + P_{2}

We know:

P_{1} = A_{11} (B_{12} - B_{22})

Therefore:

P_{1} = A_{11} B_{12} - A_{11} B_{22}

And:

P_{2} = (A_{11} + A_{12}) B_{22}

Therefore:

P_{2} = A_{11} B_{22} + A_{12} B_{22}

Now add them:

P_{1} + P_{2}

= A_{11} B_{12} - A_{11} B_{22} + A_{11} B_{22} + A_{12} B_{22}

The two terms cancel:

- A_{11} B_{22} + A_{11} B_{22} = 0

So we get:

P_{1} + P_{2} = A_{11} B_{12} + A_{12} B_{22}

But this is exactly:

C12

Therefore:

C12=P1+P2

This is the clever algebraic trick behind Strassen.

12. A Small Numerical Example

Let us take two 2 × 2 matrices:
A = [ 1 2 ]
[ 3 4 ]
and
B = [ 5 6 ]
[ 7 8 ]
The ordinary answer is:
C₁₁ = 1×5 + 2×7 = 19
C₁₂ = 1×6 + 2×8 = 22
C₂₁ = 3×5 + 4×7 = 43
C₂₂ = 3×6 + 4×8 = 50
Therefore:
C = [ 19 22 ]
[ 43 50 ]
Now let us see how Strassen obtains the same answer.
Since this is already a 2 × 2 matrix, each block A₁₁, A₁₂, etc. is just a single number.
We have:
A₁₁ = 1
A₁₂ = 2
A₂₁ = 3
A₂₂ = 4
and:
B₁₁ = 5
B₁₂ = 6
B₂₁ = 7
B₂₂ = 8

Calculate S₁ through S₁₀

S₁ = B₁₂ − B₂₂ = 6 − 8 = −2
S₂ = A₁₁ + A₁₂ = 1 + 2 = 3
S₃ = A₂₁ + A₂₂ = 3 + 4 = 7
S₄ = B₂₁ − B₁₁ = 7 − 5 = 2
S₅ = A₁₁ + A₂₂ = 1 + 4 = 5
S₆ = B₁₁ + B₂₂ = 5 + 8 = 13
S₇ = A₁₂ − A₂₂ = 2 − 4 = −2
S₈ = B₂₁ + B₂₂ = 7 + 8 = 15
S₉ = A₁₁ − A₂₁ = 1 − 3 = −2
S₁₀ = B₁₁ + B₁₂ = 5 + 6 = 11

Calculate P₁ through P₇

Now perform the seven multiplications.
P₁ = A₁₁ × S₁
= 1 × (−2)
= −2
P₂ = S₂ × B₂₂
= 3 × 8
= 24
P₃ = S₃ × B₁₁
= 7 × 5
= 35
P₄ = A₂₂ × S₄
= 4 × 2
= 8
P₅ = S₅ × S₆
= 5 × 13
= 65
P₆ = S₇ × S₈
= (−2) × 15
= −30
P₇ = S₉ × S₁₀
= (−2) × 11
= −22

Calculate C₁₁

Use:
C₁₁ = P₅ + P₄ − P₂ + P₆
Substitute:
C₁₁ = 65 + 8 − 24 − 30
Therefore:
C₁₁ = 19

Calculate C₁₂

C₁₂ = P₁ + P₂
= −2 + 24
= 22

Calculate C₂₁

C₂₁ = P₃ + P₄
= 35 + 8
= 43

Calculate C₂₂

C₂₂ = P₅ + P₁ − P₃ − P₇
= 65 − 2 − 35 − (−22)
= 50
Therefore:
C = [ 19 22 ]
[ 43 50 ]
which is exactly the same answer obtained by ordinary matrix multiplication.

13.Recurrence for Strassen's Algorithm

Strassen performs seven recursive multiplications.

Therefore:

T(n) = 7T(n/2) + Θ(n²)

The seven recursive calls dominate the computation.

Using the Master Theorem:

a = 7

b = 2

Therefore:

log₂7 ≈ 2.807

Since:

log₂7 > 2

we obtain:

T(n) = Θ(n^log₂7)

or approximately:

T(n) = Θ(n²·⁸⁰⁷)

Thus Strassen improves the exponent from 3 to approximately 2.807.

14. Comparison

Method	Recursive Multiplications	Time Complexity
Conventional	8	Θ(n³)
Divide-and-conquer	8	Θ(n³)
Strassen	7	Θ(n²·⁸⁰⁷)

The important improvement is:

Θ(n³) → Θ(n²·⁸⁰⁷)

15. Why Does One Less Multiplication Matter So Much?

This is an important point to emphasize to students.

At first, reducing:

8 → 7

may appear to be a small improvement.

But these are recursive multiplications.

For example, at the first level:

8 → 7

At the next level, every multiplication is again divided.

So instead of:

8 × 8 = 64

subproblems at the next level, Strassen has:

7 × 7 = 49

subproblems.

At the next level:

8³ = 512

versus:

7³ = 343

And so on.

This repeated reduction at every level is what produces the asymptotic improvement.

16.Advantages of Strassen's Algorithm

1. Better asymptotic complexity

Conventional matrix multiplication:

Θ(n³)

Strassen:

Θ(n²·⁸⁰⁷)

2. Uses divide-and-conquer

The algorithm naturally demonstrates the power of the divide-and-conquer paradigm.

3. Reduces recursive multiplications

The key achievement is:

8 recursive multiplications → 7 recursive multiplications

17. Limitations

Strassen's algorithm is not always the best choice for every matrix size.

It performs many additional additions and subtractions.

For small matrices, the overhead associated with these operations and recursive calls may outweigh the benefit of reducing multiplications.

Therefore, practical implementations often use a hybrid approach:

Use Strassen's method for sufficiently large matrices and switch to conventional multiplication when the matrices become small.

The exact crossover point depends on the implementation and hardware.

18.Summary

Strassen's matrix multiplication is a divide-and-conquer algorithm for multiplying square matrices.

The conventional divide-and-conquer method divides each matrix into four submatrices and requires 8 recursive matrix multiplications.

Strassen discovered a way to calculate the same result using only 7 recursive matrix multiplications, together with additional matrix additions and subtractions.

The conventional method has the recurrence:

T(n) = 8T(n/2) + Θ(n²)

and therefore:

T(n) = Θ(n³)

Strassen's method has the recurrence:

T(n) = 7T(n/2) + Θ(n²)

and therefore:

T(n) = Θ(n^log₂7) ≈ Θ(n²·⁸⁰⁷)

Thus, the fundamental idea behind Strassen's algorithm is:

Trade a small number of additional additions and subtractions for one fewer recursive multiplication. Because the saving occurs at every level of recursion, the overall asymptotic complexity improves from Θ(n³) to Θ(n²·⁸⁰⁷).