Strassen Theory

Problem

Multiply two n x n matrices faster than classical triple-loop O(n^3). Use algebraic decomposition on 2 x 2 block matrices to reduce multiplication count.

Block Decomposition

Partition A and B into 4 submatrices each (quadrants):

Classical approach requires 8 sub-matrix multiplies (Aij * Bij combos). Strassen derives 7 products M1..M7 using sums/differences which still span all necessary combinations.

Recombine into result quadrants:

Pseudocode

1function strassen(A, B):
2  if n == 1: return A*B
3  partition A,B into 4 submatrices
4  compute 7 products P1..P7
5  combine into result matrix C
6  return C

Key Insights

• Algebraic substitution reduces multiplication count from 8 to 7.
• Hybrid strategy: switch to classical below cutoff to reduce overhead.
• Add/sub operations inflate constant factors vs naive for small n.
• Sets foundation for later theoretical improvements.