Matrix Multiplication Complexity Over Time

The efficiency of matrix multiplication is measured by the exponent omega in the asymptotic complexity O(n^omega). For centuries, the schoolbook algorithm with omega equal to 3.0 was the only known method. This changed in 1969 when Volker Strassen discovered an algorithm with an exponent of approximately 2.807, proving that matrix multiplication could be performed faster than the naive approach. This breakthrough sparked decades of research into the theoretical limits of linear algebra computation.

The 1970s and 1980s saw rapid progress with contributions from researchers like Pan, Bini, and Schönhage. A major milestone was reached in 1987 when Coppersmith and Winograd introduced an algorithm with an exponent of 2.375, a record that stood for over twenty years. Recent years have seen a flurry of new records starting with Stothers in 2010 and continued by Virginia Vassilevska Williams and others, pushing the exponent down to approximately 2.371. While these "galactic algorithms" provide significant theoretical improvements, they are often not used in practice due to the massive constant factors involved in their implementation.

Sources: Wikipedia.org, arXiv.org (2307.07970), Stanford University, Quanta Magazine.