Strassen Algorithm

1969 divide-and-conquer algorithm that multiplies 2×2 matrices with 7 multiplications, proving sub-cubic matrix multiplication for the first time.

Specifications & Metrics

Published by Volker Strassen in 1969, it multiplies 2×2 matrices with 7 scalar multiplications instead of 8.
Applied recursively it reaches about O(n^2.807) operations and was the first sub-cubic matrix multiplication algorithm.
It is typically used only for large matrices, because its numerical stability is reduced and the crossover point outweighs the gain for small sizes.