Strassen's Algorithm

This project explores Strassen's Algorithm, a divide-and-conquer method for matrix multiplication that achieves O(n^2.81) time complexity, improving upon the standard O(n³) algorithm.

I wrote an in-depth paper on this topic for MATH 299 at Haverford College, which includes proofs of correctness, time complexity analysis, and practical benchmarks comparing pure Strassen, hybrid Strassen, and standard multiplication.

Read the Paper (PDF) View on GitHub

How It Works

Standard matrix multiplication computes each entry of the result matrix using dot products, requiring 8 multiplications for 2×2 matrices. Strassen discovered that you can compute the same result with only 7 multiplications (at the cost of more additions).

x₁ = (a₁₁ + a₂₂)(b₁₁ + b₂₂)
x₂ = (a₂₁ + a₂₂)b₁₁
x₃ = a₁₁(b₁₂ - b₂₂)
x₄ = a₂₂(-b₁₁ + b₂₁)
x₅ = (a₁₁ + a₁₂)b₂₂
x₆ = (-a₁₁ + a₂₁)(b₁₁ + b₁₂)
x₇ = (a₁₂ - a₂₂)(b₂₁ + b₂₂)

Key Insight: While this seems like more work for 2×2 matrices (25 operations vs 12), when applied recursively to large matrices, saving one multiplication at each level compounds into significant savings: O(n^log₂7) ≈ O(n^2.81) vs O(n³).

Interactive Performance Demo

See how operation counts scale with matrix size and why hybrid Strassen outperforms both pure methods:

Performance Comparison

Adjust matrix size to see how each algorithm scales

Matrix Size (n):

32 × 32

Hybrid threshold: T = 32

Standard

32,768

multiplications

Additions: 31,744 Total: 64,512

Pure Strassen

16,807

multiplications

Additions: 58,482 Total: 75,289

Hybrid Strassen

multiplications

Additions: -- Total: --

Total Operations Comparison

Standard

64,512

baseline

Pure Strassen

75,289

1.17x slower

Hybrid

Why Hybrid Wins

At this size, hybrid Strassen uses Strassen's recursion at the top levels to reduce multiplications, then switches to standard multiplication at the base case to avoid the overhead of extra additions. This gives the best of both worlds.

Live Timing Benchmark

Run the algorithms in your browser and measure actual execution time

Matrix Size: Trials:

Standard

milliseconds

Avg per trial: --

Pure Strassen

milliseconds

Avg per trial: --

Hybrid Strassen

milliseconds

Avg per trial: --

Execution Time Comparison

Standard

baseline

Pure Strassen

Hybrid

Note: JavaScript is slower than C, so times will be higher than the paper's benchmarks. However, the relative performance differences should be similar. Hybrid Strassen should consistently beat both standard and pure Strassen for larger matrices.

Key Findings from My Research

Pure Strassen is slower in practice for small matrices due to recursion overhead and extra additions.
Hybrid Strassen (switching to standard multiplication below a threshold) achieves 1.4–2.4× speedup over standard multiplication for n ≥ 32.
The optimal threshold on my machine was T = 16–32.
Strassen's algorithm should be viewed as a tool for reducing the cost of large matrix multiplications, not a replacement for standard multiplication.

Actual Benchmarks (from my C implementation)

n	Standard (s)	Pure Strassen (s)	Hybrid Strassen (s)	Hybrid Speedup
32	0.000069	0.000465	0.000050	1.38×
64	0.000556	0.003201	0.000377	1.47×
128	0.004267	0.022708	0.002413	1.77×
256	0.034772	0.160049	0.018326	1.87×
512	0.277440	1.122273	0.135234	2.06×
1000	2.203858	7.839432	0.922053	2.40×

Benchmarks run on my machine with 100 trials per size. See the paper for full methodology.