Project DelphiTensors Workshop

Recursion — the saving is in the exponent

In every product m_r the entries of A stand on the left and the entries of B on the right: the recipe never assumes xy = yx. So the entries can be matrices. Cut two n × n matrices into quarters, multiply the quarters with 7 products instead of 8, and apply the recipe again inside each product.

After k levels, a matrix of side n = 2ᵏ costs 8ᵏ = n³ the schoolbook way and 7ᵏ = n^2.807 with Strassen (log₂ 7 ≈ 2.807):

side n schoolbook Strassen saved
2 8 7 12.5%
8 512 343 33.0%
1,024 1,073,741,824 282,475,249 73.7%

One saved block saves a whole subtree, at every level. That is why the count of blocks is worth a search. It counts multiplications only: additions, memory traffic and rounding error still decide whether a library uses a fast algorithm.