Project DelphiTensors Workshop

Strassen's seven blocks

Strassen’s seven rank-one blocks (1969) rebuild the 4 × 4 × 4 tensor exactly, so 2 × 2 matrices can be multiplied with seven multiplications:

np.array_equal(np.einsum("ra,rb,rc->abc", U, V, W), matmul_tensor(2)) # True

It is not a steady walk. Add the blocks one at a time and the count of wrong cells goes 8, 12, 12, 12, 10, 8, 4, 0. Over the seven steps 20 different cells hold something; 12 are cancelled back to zero and the 8 left standing are the tensor.

On numbers it is a bad trade: 7 multiplications and 18 additions and subtractions, against the schoolbook 8 and 4 — 25 operations against 12. Run on [[1, 2], [3, 4]] and [[5, 6], [7, 8]], the seven products 65, 35, −2, 8, 24, 22, −30 assemble to 19, 22, 43, 50.