Strassen Algorithm - Matrix Multiplication

This post was migrated from Tistory. You can find the original here.

Standard matrix multiplication

Standard matrix multiplication

// pseudocode
for i from 1 to n:                     // rows of A (1 to n)
    for j from 1 to n:                 // columns of B (1 to n)
        C[i][j] = 0                    // initialize each element of C
        for k from 1 to n:             // columns of A / rows of B (k from 1 to n)
            C[i][j] = C[i][j] + A[i][k] * B[k][j]
        end for
    end for
end for

The naive approach to matrix multiplication uses three nested loops, giving a time complexity of O(n^3).

Strassen matrix multiplication

The Strassen algorithm uses a divide-and-conquer approach to multiply two n x n matrices faster.

Assumption: split each matrix into 4 symmetric blocks.

Matrix partitioning

Standard matrix multiplication

The straightforward approach requires 8 multiplications.

Strassen came up with a formula that reduces this to 7 multiplications.

Strassen matrix multiplication

Since we first split the matrices, A[i][j] and B[i][j] are each n/2 * n/2 matrices.

So each M term is itself made up of n/2 * n/2 matrix multiplications.

If we let T(n) denote the cost of an n * n matrix multiplication,

then T(n/2) is the cost of an n/2 * n/2 matrix multiplication,

Strassen recurrence relation

and we get the recurrence above, where T(n/2) appears 7 times.

Matrix addition/subtraction

Adding or subtracting two n*n matrices requires two nested for-loops over i and j, so it costs O(n^2).

In the Strassen recurrence, this is written as O((n/2)^2) ~= O(n^2).

Expanding the recurrence

Expanding the Strassen recurrence

Let’s expand the recurrence step by step.

T(n/2) = 7T(n/4) + O((n/2)^2)

T(n/4) = 7T(n/8) + O((n/4)^2)

….

Generalizing the Strassen recurrence

Repeating this pattern, a general form emerges.

Let’s work out the first term and the second term separately.

The recursion bottoms out when n/(2^k) = 1, i.e., when k = log2(n), at which point T(1) = O(1).

First term

Substituting k in,

since n = O(n),

we can say 7^k = O(7^k) = O(n^log2(7)).

Second term

Generalizing the second term gives a geometric series with common ratio 7/4.

Geometric series sum formula

The leading coefficient works out to -4/3 (not that it matters much, since we’re after the time complexity).

As with the first term, let’s substitute k = log2(n).

Since Big-O only cares about the dominant term,

n^(log2(7/4) + 2) dominates over the leading n^2 term (when multiplying powers with the same base, the exponents add).

Since log2(7/4) + 2 = log2(7) - log2(4) + log2(4), this simplifies to n^(log2(7)).

So the second term also comes out to O(n^log2(7)).

Final result

Generalizing the Strassen recurrence

Since both terms converge to O(n^log2(7)), the final time complexity is T(n) = O(n^log2(7)).

Since log2(7) = 2.80735…,

we’ve reduced the standard O(n^3) matrix multiplication down to O(n^2.807..).

Pros and cons of Strassen matrix multiplication

Pros	Cons
Improves time complexity to O(n^2.81)	High constant factor hurts performance on small matrices
Well-suited to parallelization (divide-and-conquer)	Can introduce floating-point precision issues
Delivers real performance gains on large matrices	Uses more memory
Inspired many modern fast algorithms	Extra overhead for handling non-square matrices

Afterword

It’s been a while since I dug into a recurrence relation just for the fun of following it through.