Divide-and-Conquer for Matrix Multiplication: From Naive to Strassen's Algorithm

The Matrix Multiplication Problem

Given two n × n matrices A and B, the goal is to compute their product C = A × B, where each entry is defined as:

C[i][j] = Σ (for k = 1 to n) A[i][k] × B[k][j]

This operation appears throughout computer science and applied mathematics, from computer graphics transformations to solving systems of linear equations to the neural network computations underlying modern machine learning.

The Naive Algorithm

The straightforward approach directly implements the mathematical definition using three nested loops.

SQUARE-MATRIX-MULTIPLY(A, B, n):
  let C be a new n × n matrix
  for i = 1 to n:
      for j = 1 to n:
          C[i][j] = 0
          for k = 1 to n:
              C[i][j] = C[i][j] + A[i][k] · B[k][j]
  return C

Each entry of the output matrix requires n multiplications and additions, and there are n² entries to compute, giving a total running time of Θ(n³). For decades, this cubic running time was assumed to be essentially unavoidable for matrix multiplication.

A First Attempt: Naive Divide-and-Conquer

Applying the divide-and-conquer paradigm, an n × n matrix can be partitioned into four n/2 × n/2 submatrices, and matrix multiplication can be expressed recursively in terms of these submatrices.

Partition A and B into quadrants:
A = [A11  A12]      B = [B11  B12]
    [A21  A22]          [B21  B22]

The product C = A × B is then:
C11 = A11·B11 + A12·B21
C12 = A11·B12 + A12·B22
C21 = A21·B11 + A22·B21
C22 = A21·B12 + A22·B22

This requires 8 recursive multiplications of n/2 × n/2 submatrices, plus 4 additions of n/2 × n/2 matrices, each taking Θ(n²) time. The resulting recurrence is:

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

Solving this recurrence, using the master method covered in the next article of this series, gives T(n) = Θ(n³) — exactly the same asymptotic running time as the naive triple-loop algorithm. Simply reformulating the problem recursively provided no improvement.

Strassen's Breakthrough Insight

In 1969, Volker Strassen discovered a way to compute the product of two 2×2 matrices using only 7 multiplications instead of 8, at the cost of additional matrix additions and subtractions. Since multiplications are the more expensive operation asymptotically when applied recursively, this small reduction has an outsized effect on the overall running time.

Strassen's algorithm first computes 7 intermediate products using specific combinations of submatrix sums and differences:

P1 = A11 · (B12 - B22)
P2 = (A11 + A12) · B22
P3 = (A21 + A22) · B11
P4 = A22 · (B21 - B11)
P5 = (A11 + A22) · (B11 + B22)
P6 = (A12 - A22) · (B21 + B22)
P7 = (A11 - A21) · (B11 + B12)

The four output quadrants are then reconstructed purely from these 7 products, using only addition and subtraction:

C11 = P5 + P4 - P2 + P6
C12 = P1 + P2
C21 = P3 + P4
C22 = P5 + P1 - P3 - P7

Verifying these formulas algebraically confirms they produce exactly the same result as the standard matrix multiplication formulas, but using one fewer multiplication at each level of recursion.

Analyzing Strassen's Running Time

Since each level of recursion now requires only 7 recursive multiplications of half-sized submatrices, plus a constant number of Θ(n²) additions and subtractions, the recurrence becomes:

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

Solving this recurrence using the master method yields T(n) = Θ(n^log₂7) ≈ Θ(n^2.807), a genuine asymptotic improvement over the naive Θ(n³) algorithm. While the improvement from exponent 3 to approximately 2.807 might seem modest, it becomes significant for very large matrices, and it proved something profoundly important: cubic time is not fundamentally required for matrix multiplication, opening the door to decades of further research into even faster algorithms.

Practical Considerations

Despite its better asymptotic complexity, Strassen's algorithm is rarely used in practice for typical matrix sizes, for several practical reasons. The algorithm has a larger constant factor hidden inside the asymptotic notation, meaning it only outperforms the naive algorithm once matrices become quite large. It is also less numerically stable than the naive approach, since the additional additions and subtractions can amplify floating-point rounding errors. Real-world numerical libraries typically use a hybrid approach: applying Strassen's algorithm recursively down to some threshold size, then switching to the naive algorithm for the base case, to get the asymptotic benefit while minimizing overhead and numerical instability.

Why This Result Matters Beyond Matrix Multiplication

Strassen's algorithm is historically significant well beyond its immediate practical application. It was one of the first results to demonstrate that a problem's naive algorithm, however intuitive, is not necessarily asymptotically optimal, inspiring an entire subfield of research into fast matrix multiplication that continues to this day, with the current best-known algorithms achieving exponents even lower than Strassen's original bound, though with constant factors so large they remain purely of theoretical interest.