Strassen algorithm

In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication. It is faster than the standard matrix muliplication algorithm.

History

Volker Strassen published the Strassen algorithm in 1969 and although his algorithm is only slightly faster than the standard algorithm for matrix mulitplication, he was the first to point out that Gaussian elimination was not optimal. His paper started the search for even faster algorithms (e.g. Coppersmith-Winograd algorithm).

Algorithm

Let A, B be two square matrices over a