The naïve way to multiply square matrices runs in time O(n^3); for many years no one suspected this was less than optimal. But Strassen discovered an algorithm which runs in time O(n^2.81...). This was very surprising, and sparked new interest in matrix multiplication algorithms. Today the best known algorithm runs in time O(n^2.31...) (although with such a large constant factor that it is unclear if it is useful in the Real World), but nothing is known about a lower bound. In fact, it is not known that matrix multiplication cannot be done in O(n^2) (the size of the input).

The detailed algorithm is described in my writeup under matrix multiplication.

Log in or register to write something here or to contact authors.