A Refined Laser Method and Faster Matrix Multiplication | Breakthroughs

The Simons Institute's Breakthroughs series kicked off on June 16 with a talk by Virginia Vassilevska Williams of MIT, who recently developed the fastest method to date for multiplying two matrices, in collaboration with Josh Alman of Columbia. Breakthroughs is a new lecture series highlighting major new developments in theoretical computer science and is geared toward a scientific audience. 

Matrix multiplication is one of the most basic linear algebraic operations outside elementary arithmetic. The study of matrix multiplication algorithms is very well motivated from practice, as the applications are plentiful. Matrix multiplication is also of great mathematical interest. Since Strassen's discovery in 1969 that n-by-n matrices can be multiplied asymptotically much faster than the brute-force O(n³) time algorithm, many fascinating techniques have been developed, incorporating ideas from computer science, combinatorics, and algebraic geometry.

The fastest algorithms over the last three decades have used Strassen's "laser method" and its optimization by Coppersmith and Winograd. The method has remained unchanged; the algorithms have differed in what the method was applied to. In recent work, Williams and Alman improve the method so that applying it to the same objects that the old method was applied to immediately yields faster algorithms. Using this new method, they obtain the theoretically fastest algorithm for matrix multiplication to date, with running time O(n^2.37286).