1. One-Liner
Strassen’s algorithm multiplies two n×n matrices using 7 block multiplications (instead of 8) at each recursive level, improving the asymptotic exponent.
2. The Problem It Solves
Classic matrix multiply costs O(n³); Strassen reduces the exponent to roughly log₂(7) ≈ 2.807 for large n—a landmark divide-and-conquer win in theory and large dense linear algebra.
3. The Core Idea
Partition each matrix into four quadrants; form seven cleverly chosen products of sums/differences of blocks, then recombine with additions/subtractions—fewer multiplies, more adds.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Partition | Split A,B into A11…A22, B11…B22. |
| 2. Seven products | Compute M1…M7 from block sums (Strassen formulas). |
| 3. Combine | Build result blocks C11…C22 from M1…M7. |
| 4. Recurse | Multiply sub-blocks until base size (e.g. 64) then naive multiply. |
5. Dry Run Example
For 2×2 blocks, seven products replace eight—demonstrates the trade: more bookkeeping, fewer multiplications.
6. Key Properties
| Property | Value |
|---|---|
| Time | O(n^{log_2 7}) ≈ O(n^{2.807}) |
| Space | Recursion + temporary blocks |
| Practical | Crossover n often large; cache matters |
7. Where It Is Used
| Domain | Use |
|---|---|
| HPC / research | Large dense matmul building blocks |
| Libraries | Mixed with naive/tiled BLAS for speed |
8. Interview Tips
Know 7 vs 8 products, numeric stability trade-offs vs Strassen, and that constants dominate for moderate n.
9. Comparison with Other Algorithms
| Algorithm | Exponent | Notes |
|---|---|---|
| Naive | 3 | Simple |
| Strassen | ≈2.807 | Fewer multiplies |
| Coppersmith–Winograd family | lower (theory) | Huge constants |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n^{log_2 7}) |
| Space | O(n²) + recursion |
Implementation Example (PYTHON)
def mat_add(A, B):
return [[A[i][j] + B[i][j] for j in range(len(A))] for i in range(len(A))]
def mat_sub(A, B):
return [[A[i][j] - B[i][j] for j in range(len(A))] for i in range(len(A))]
def strassen(A, B):
n = len(A)
if n == 1:
return [[A[0][0] * B[0][0]]]
m = n // 2
A11 = [r[:m] for r in A[:m]]
A12 = [r[m:] for r in A[:m]]
A21 = [r[:m] for r in A[m:]]
A22 = [r[m:] for r in A[m:]]
B11 = [r[:m] for r in B[:m]]
B12 = [r[m:] for r in B[:m]]
B21 = [r[:m] for r in B[m:]]
B22 = [r[m:] for r in B[m:]]
M1 = strassen(mat_add(A11, A22), mat_add(B11, B22))
M2 = strassen(mat_add(A21, A22), B11)
M3 = strassen(A11, mat_sub(B12, B22))
M4 = strassen(A22, mat_sub(B21, B11))
M5 = strassen(mat_add(A11, A12), B22)
M6 = strassen(mat_sub(A21, A11), mat_add(B11, B12))
M7 = strassen(mat_sub(A12, A22), mat_add(B21, B22))
C11 = mat_add(mat_sub(mat_add(M1, M4), M5), M7)
C12 = mat_add(M3, M5)
C21 = mat_add(M2, M4)
C22 = mat_sub(mat_add(mat_add(M1, M3), M6), M2)
top = [C11[i] + C12[i] for i in range(m)]
bot = [C21[i] + C22[i] for i in range(m)]
return top + bot