Strassen's Matrix Multiplication

Introduction

Strassen's Matrix Multiplication is an efficient matrix multiplication algorithm based on the Divide and Conquer technique. It was introduced by Volker Strassen in 1969. The main idea is to divide each matrix into smaller sub-matrices and reduce the number of multiplications required to obtain the final result.

In conventional multiplication of two 2 × 2 matrices, 8 scalar multiplications are required. Strassen's method calculates the same result using only 7 multiplications, at the cost of additional additions and subtractions.

This reduction becomes increasingly useful when the matrices are large because multiplication is generally more computationally expensive than addition or subtraction.

Why Do We Need Strassen's Algorithm?

Consider the multiplication of two large n × n matrices. The conventional method requires O(n³) time. As the value of n increases, the number of multiplication operations increases rapidly.

Strassen's Algorithm reduces the number of recursive multiplications from eight to seven. Its recurrence relation is:

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

Using the Master Theorem:

T(n) = O(n^log₂7) ≈ O(n^2.807)

Therefore, the theoretical multiplication complexity is better than the conventional O(n³) algorithm.

Prerequisites

Basic Idea of Strassen's Algorithm

Suppose we want to multiply two square matrices A and B. For simplicity, first consider 2 × 2 matrices.

Figure 1: Division of matrices into four sub-matrices

For larger matrices, the same process is applied recursively. Each matrix is divided into four approximately equal-sized blocks until the base case is reached.

Conventional Multiplication of Two 2 × 2 Matrices

Let:

A = [ a   b ]
[ c   d ]      and      B = [ e   f ]
[ g   h ]

The conventional multiplication is:

C₁₁ = ae + bg

C₁₂ = af + bh

C₂₁ = ce + dg

C₂₂ = cf + dh

This requires eight multiplications:

ae, bg, af, bh, ce, dg, cf, dh

Strassen's method rearranges these calculations so that only seven multiplications are needed.

Seven Intermediate Products

Strassen's Algorithm calculates seven intermediate products, traditionally called P₁ to P₇.

Construction of the Result Matrix

After calculating the seven products, the four blocks of the result matrix are calculated as follows:

Finally, the four blocks are combined:

Step-by-Step Working

For two 2 × 2 matrices:

A = [ A₁₁   A₁₂ ]
[ A₂₁   A₂₂ ]

B = [ B₁₁   B₁₂ ]
[ B₂₁   B₂₂ ]

The complete process is:

1. Divide matrices A and B into four blocks.
2. Calculate the seven products P₁ to P₇.
3. Calculate C₁₁, C₁₂, C₂₁ and C₂₂.
4. Combine the four result blocks.
5. For larger matrices, recursively repeat the same process.

Solved Example 1: Simple 2 × 2 Matrix

Multiply:

A = [ 1   2 ]
[ 3   4 ]      B = [ 5   6 ]
[ 7   8 ]

Therefore:

A₁₁=1, A₁₂=2, A₂₁=3, A₂₂=4

B₁₁=5, B₁₂=6, B₂₁=7, B₂₂=8

Step 1: Calculate P₁

P₁ = (A₁₁ + A₂₂) × (B₁₁ + B₂₂)

= (1 + 4) × (5 + 8)

= 5 × 13 = 65

Step 2: Calculate P₂

P₂ = (A₂₁ + A₂₂) × B₁₁

= (3 + 4) × 5

= 7 × 5 = 35

Step 3: Calculate P₃

P₃ = A₁₁ × (B₁₂ − B₂₂)

= 1 × (6 − 8)

= 1 × (−2) = −2

Step 4: Calculate P₄

P₄ = A₂₂ × (B₂₁ − B₁₁)

= 4 × (7 − 5)

= 4 × 2 = 8

Step 5: Calculate P₅

P₅ = (A₁₁ + A₁₂) × B₂₂

= (1 + 2) × 8

= 3 × 8 = 24

Step 6: Calculate P₆

P₆ = (A₂₁ − A₁₁) × (B₁₁ + B₁₂)

= (3 − 1) × (5 + 6)

= 2 × 11 = 22

Step 7: Calculate P₇

P₇ = (A₁₂ − A₂₂) × (B₂₁ + B₂₂)

= (2 − 4) × (7 + 8)

= −2 × 15 = −30

Step 8: Calculate C₁₁

C₁₁ = P₁ + P₄ − P₅ + P₇

= 65 + 8 − 24 − 30

= 19

Step 9: Calculate C₁₂

C₁₂ = P₃ + P₅

= −2 + 24 = 22

Step 10: Calculate C₂₁

C₂₁ = P₂ + P₄

= 35 + 8 = 43

Step 11: Calculate C₂₂

C₂₂ = P₁ − P₂ + P₃ + P₆

= 65 − 35 − 2 + 22

= 50

Final Answer

Therefore, AB = [19   22; 43   50]

Solved Example 2: Medium 4 × 4 Matrix

Multiply the following matrices using Strassen's method:

A = [ 1   2   3   4 ]
[ 5   6   7   8 ]
[ 9   10   11   12 ]
[ 13   14   15   16 ]

B = [ 16   15   14   13 ]
[ 12   11   10   9 ]
[ 8   7   6   5 ]
[ 4   3   2   1 ]

For a 4 × 4 matrix, divide each matrix into four 2 × 2 blocks.

For matrix A:

A₁₁ = [ 1   2 ]
[ 5   6 ]

A₁₂ = [ 3   4 ]
[ 7   8 ]

A₂₁ = [ 9   10 ]
[ 13   14 ]

A₂₂ = [ 11   12 ]
[ 15   16 ]

Similarly, divide B:

B₁₁ = [ 16   15 ]
[ 12   11 ]

B₁₂ = [ 14   13 ]
[ 10   9 ]

B₂₁ = [ 8   7 ]
[ 4   3 ]

B₂₂ = [ 6   5 ]
[ 2   1 ]

Now apply the seven Strassen formulas to these 2 × 2 blocks. Each multiplication of two 2 × 2 blocks is itself performed using Strassen's method.

Step 1: Calculate the Seven Block Products

P₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)

A₁₁ + A₂₂ = [ 12   14 ]
[ 20   22 ]

B₁₁ + B₂₂ = [ 22   20 ]
[ 14   12 ]

Therefore:

P₁ = [ 12   14 ] [ 22   20 ]
[ 20   22 ] [ 14   12 ]

= [ 460   408; 748   664 ]

Similarly:

P₂ = (A₂₁ + A₂₂)B₁₁

A₂₁ + A₂₂ = [ 20   22 ]
[ 28   30 ]

P₂ = [ 584   542; 808   753 ]

P₃ = A₁₁(B₁₂ − B₂₂)

B₁₂ − B₂₂ = [ 8   8 ]
[ 8   8 ]

P₃ = [ 24   24; 88   88 ]

P₄ = A₂₂(B₂₁ − B₁₁)

B₂₁ − B₁₁ = [ −8   −8 ]
[ −8   −8 ]

P₄ = [ −184   −184; −248   −248 ]

P₅ = (A₁₁ + A₁₂)B₂₂

A₁₁ + A₁₂ = [ 4   6 ]
[ 12   14 ]

P₅ = [ 36   26; 100   74 ]

P₆ = (A₂₁ − A₁₁)(B₁₁ + B₁₂)

A₂₁ − A₁₁ = [ 8   8 ]
[ 8   8 ]

B₁₁ + B₁₂ = [ 30   28 ]
[ 22   20 ]

P₆ = [ 416   384; 416   384 ]

P₇ = (A₁₂ − A₂₂)(B₂₁ + B₂₂)

A₁₂ − A₂₂ = [ −8   −8 ]
[ −8   −8 ]

B₂₁ + B₂₂ = [ 14   12 ]
[ 6   4 ]

P₇ = [ −160   −128; −160   −128 ]

Step 2: Calculate the Four Result Blocks

C₁₁ = P₁ + P₄ − P₅ + P₇

= [ 80   70; 240   190 ]

C₁₂ = P₃ + P₅

= [ 60   50; 188   162 ]

C₂₁ = P₂ + P₄

= [ 400   358; 560   505 ]

C₂₂ = P₁ − P₂ + P₃ + P₆

= [ 316   274; 444   383 ]

Final Answer

Solved Example 3: Advanced 8 × 8 Concept

For an 8 × 8 matrix, Strassen's Algorithm is applied recursively. The important point is that the algorithm does not directly multiply all 64 × 64 individual elements using the conventional method.

The 8 × 8 matrix is first divided into four 4 × 4 blocks:

The same division is made for matrix B. The seven block products are then formed:

P₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)

P₂ = (A₂₁ + A₂₂)B₁₁

P₃ = A₁₁(B₁₂ − B₂₂)

P₄ = A₂₂(B₂₁ − B₁₁)

P₅ = (A₁₁ + A₁₂)B₂₂

P₆ = (A₂₁ − A₁₁)(B₁₁ + B₁₂)

P₇ = (A₁₂ − A₂₂)(B₂₁ + B₂₂)

Each of these seven 4 × 4 multiplications is again divided into four 2 × 2 blocks. The same seven-product procedure is then applied recursively.

Thus, the recursion can be represented as:

8 × 8 → 4 × 4 → 2 × 2 → 1 × 1

At the 1 × 1 level, ordinary scalar multiplication is performed. The results are then combined while returning from the recursive calls.

This example demonstrates the most important feature of Strassen's Algorithm: the same seven-product method is repeatedly applied to smaller matrices.

How Recursion Works

For an n × n matrix, the algorithm divides the problem into seven subproblems of size n/2 × n/2.

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

The 7T(n/2) term represents the seven recursive multiplications, while O(n²) represents the matrix additions and subtractions.

The recursion stops when the matrix reaches the selected base-case size, commonly 1 × 1 or a small threshold such as 2 × 2, depending on the implementation.

Handling Matrix Sizes That Are Not Powers of 2

The simplest recursive implementation works most naturally when the matrix dimension is a power of 2, such as:

2, 4, 8, 16, 32, 64, ...

If the matrix size is not a power of 2, such as 3 × 3 or 5 × 5, the matrices can be padded with zeros until the required dimension is reached.

For example, a 3 × 3 matrix can be converted into a 4 × 4 matrix by adding a row and column containing zeros:

After multiplication, the extra row and column are discarded and the original 3 × 3 result is retained.

Strassen's Algorithm

Pseudocode

Complexity Analysis

The improvement comes from reducing the number of recursive multiplications from 8 to 7. However, Strassen's method performs more additions and subtractions and requires additional temporary storage.

Advantages of Strassen's Algorithm

• Uses seven recursive multiplications instead of eight.
• Has a theoretical time complexity of approximately O(n^2.807).
• Uses the Divide and Conquer technique.
• Can provide performance benefits for sufficiently large matrices.
• Can be applied recursively to large square matrices.

Limitations of Strassen's Algorithm

• The algorithm is more complicated than conventional matrix multiplication.
• It requires additional matrix additions and subtractions.
• It requires additional temporary storage.
• Recursive overhead makes it less attractive for small matrices.
• Numerical errors can be more noticeable for floating-point computations because of the additional additions and subtractions.
• For practical implementations, a conventional multiplication method is often used below a selected matrix-size threshold.

Applications of Strassen's Algorithm

Conventional Matrix Multiplication vs Strassen's Algorithm

Summary

Strassen's Matrix Multiplication is a Divide and Conquer algorithm that reduces the number of recursive multiplications required for matrix multiplication from eight to seven. The algorithm divides matrices into four blocks, calculates seven carefully designed intermediate products and combines them to obtain the final matrix.

Its recurrence relation is T(n) = 7T(n/2) + O(n²), giving a theoretical time complexity of O(n^log₂7) ≈ O(n^2.807). The method is particularly useful as a theoretical and practical technique for large dense matrix multiplication, although the extra additions, temporary storage and recursive overhead mean that it is not necessarily the best choice for every matrix size.