Strassen Matrix Multiplication

Multiplies two n×n matrices (split into 2×2 blocks recursively) using 7 block multiplications instead of the naive 8 — the same "trade a multiplication for extra additions" trick as Karatsuba, one level up in dimensionality.

Category

Divide and Conquer

Time complexity

O(n^2.807)

Space complexity

O(n²)

Pseudocode

split A, B into 2×2 quadrant blocks
compute 7 products M1..M7 combining the blocks
combine M1..M7 into the 4 result quadrants
recurse for n>2

Reference implementation

M1 = a*(f-h);      M2 = (a+b)*h
M3 = (c+d)*e;      M4 = d*(g-e)
M5 = (a+d)*(e+h);  M6 = (b-d)*(g+h)
M7 = (a-c)*(e+f)
C11 = M5+M4-M2+M6;  C12 = M1+M2
C21 = M3+M4;        C22 = M1+M5-M3-M7

Open the interactive Strassen Matrix Multiplication visualisation →