Strassen's Matrix Multiplication

Reduce 8 naive block multiplications to 7 strategically combined products — cutting complexity to O(n^(log2 7)) ~ O(n^2.807) by trading multiplies for additions.

Time Complexity

O(n^(log2 7))

≈ O(n^2.807) via 7 products

Space Complexity

O(n²)

Temporary sum/diff buffers

Core Pattern

Algebraic D&C

Rewrite to cut multiplies

Key Mechanics

Block Partition

Split A and B into 4 n/2 submatrices each (A11..A22, B11..B22).

Seven Products

M1..M7 formed from strategic sums/differences (e.g. M1=(A11+A22)(B11+B22)).

Recombination

C blocks reconstructed using linear combos of M1..M7.

When to Use

Large dense matrices (n above hybrid cutoff).
Educational showcase of algebraic speedups.
Foundation layer for advanced algorithms.
CPU-bound multiply dominated workloads.

Trade-offs

More additions increases constant factors.
Higher memory traffic (temp buffers).
Numerical stability slightly worse (add/sub churn).
Cross-over point varies (cache architecture).

Recurrence & Complexity

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

Master Theorem => O(n^(log2 7)) ~ O(n^2.807).

Naive is 8 sub-multiplies + recombination; Strassen removes one multiply at cost of extra additions.

Deep Theory Interactive Simulation

Closest Pair of Points Fast Fourier Transform (FFT)