Strassen Matrix Multiplication

1Eight half-size products still cost n cubed

The product C = AB of two n \times n matrices has entries C_{ij} = \sum_k A_{ik} B_{kj}. The triple loop does n^3 scalar multiplies. Divide-and-conquer splits each matrix into four n/2 blocks and writes the same product as four block formulae, each a sum of two half-size products: C_{11} = A_{11}B_{11} + A_{12}B_{21}, and three siblings. That is eight recursive multiplies plus O(n^2) block additions.

The recurrence is T(n) = 8T(n/2) + \Theta(n^2). Master theorem (or unrolling) gives T(n) = \Theta(n^3) — the same class as the triple loop. Splitting the matrix is not enough. You have to multiply fewer than eight blocks.

Figure. A split into four n/2 blocks. Each C block is two products, so eight recursive multiplies — still Θ(n³).

Naive block product

1. SplitEach of A, B, C becomes four n/2 blocks.
2. Eight productsEach of the four C blocks is a sum of two products, so eight recursive multiplies.
3. Same exponentT(n)=8T(n/2)+\Theta(n^2)=\Theta(n^3).

2Seven products, not eight

Strassen keeps the same four-block split and computes seven carefully chosen products P_1,\ldots,P_7 instead of the eight block multiplies. Each P_k is one product of two linear combinations of blocks of A and of B. The combinations look arbitrary until you expand them: they are the unique (up to scaling) set that lets every needed A_{ik}B_{kj} appear in the right C block and cancel elsewhere.

You do not derive the seven formulae in an exam. You store them, expand one C block once to see the cancellations, and then treat the list as the algorithm.

The same four-block split as the eight-product figure; what changes is the list of seven products in the table, not a new geometry.

The seven products

1. Sums firstForm A_{11}+A_{22}, A_{21}+A_{22}, A_{11}+A_{12}, A_{21}-A_{11}, A_{12}-A_{22} and the matching B combinations.
2. Seven multipliesP_1 through P_7 — each is one product of two n/2 matrices.
3. No eighthThere is no A_{12}B_{21} as a standalone product. It is recovered from the P_k mix.

Seven products (n = 2 scalars)

def strassen_products(A, B):
    A11, A12, A21, A22 = A[0][0], A[0][1], A[1][0], A[1][1]
    B11, B12, B21, B22 = B[0][0], B[0][1], B[1][0], B[1][1]
    P1 = (A11 + A22) * (B11 + B22)
    P2 = (A21 + A22) * B11
    P3 = A11 * (B12 - B22)
    P4 = A22 * (B21 - B11)
    P5 = (A11 + A12) * B22
    P6 = (A21 - A11) * (B11 + B12)
    P7 = (A12 - A22) * (B21 + B22)
    return P1, P2, P3, P4, P5, P6, P7

3Assemble C from the seven products

Once the seven products exist, each block of C is a sum and difference of a few of them: C_{11} = P_1+P_4-P_5+P_7, C_{12} = P_3+P_5, C_{21} = P_2+P_4, C_{22} = P_1+P_3-P_2+P_6. No further multiply is required. That is why the recurrence counts seven multiplies and \Theta(n^2) additions.

On the running 2-by-2 pair the four assemblies recover 20, 28, 52, 76 — the same C the eight-multiply expansion produced.

Same 2-by-2 block frame; each C block is now a sum of P_k values from the ledger, not a new drawing.

Four assemblies

1. C_{11}P_1 + P_4 - P_5 + P_7.
2. C_{12} and C_{21}P_3+P_5 and P_2+P_4.
3. C_{22}P_1 + P_3 - P_2 + P_6.

Assemble C

def strassen_combine(P1, P2, P3, P4, P5, P6, P7):
    C11 = P1 + P4 - P5 + P7
    C12 = P3 + P5
    C21 = P2 + P4
    C22 = P1 + P3 - P2 + P6
    return [[C11, C12], [C21, C22]]

Coding lab. Strassen on the 2-by-2 pair runs in the app, with checks on your output.

4T(n) = 7 T(n/2) + Θ(n²)

Each Strassen step does seven multiplies of n/2 matrices and a constant number of n/2 additions (18 additions and subtractions of blocks). So T(n) = 7T(n/2) + \Theta(n^2), with T(1) = \Theta(1).

Master theorem: a=7, b=2, f(n)=n^2, and \log_2 7 \approx 2.807 > 2, so f is polynomially smaller than n^{\log_2 7} and T(n) = \Theta(n^{\log_2 7}). The exponent dropped below 3 because the 8 became a 7. That is the whole point of the algorithm.

Figure. Exponents only, not runtimes: 2 for the additions, about 2.81 for Strassen, 3 for the eight-product recurrence. Not to scale as values of n^k.

Apply the Master theorem

1. Read a,b,fa=7 subproblems, size n/2, combine f(n)=\Theta(n^2).
2. Compare exponents\log_b a = \log_2 7 \approx 2.807 > 2.
3. Case 1T(n)=\Theta(n^{\log_2 7}).

5When seven products lose to the triple loop

The \Theta(n^{2.81}) bound is asymptotic. Each level pays 18 block additions, the recursion wants n a power of two (odd n is padded), and the extra additions are less stable in floating point than the ordinary dot product. On the 2-by-2 running example Strassen used seven multiplies and many more additions than the eight-multiply expansion.

Libraries switch to a tuned triple loop (or a later, still-faster, even-more-addition-heavy algorithm) below a crossover n measured in the hundreds. The syllabus outcome is the seven-product idea and the exponent, not a claim that you should hand-code Strassen for a 4-by-4.

No new geometry — the three-row method table is the figure.

Reasons the crossover is large

1. Addition overhead18 block additions per level, each \Theta(n^2).
2. PaddingOdd n grows to the next power of two before the recurrence applies cleanly.
3. StabilityDifferences such as B_{12}-B_{22} cancel leading digits; the ordinary product does not.