Breakthroughs — A Refined Laser Method and Faster Matrix Multiplication

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(n3) 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, joint with Josh Alman, we 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, we obtain the theoretically fastest algorithm for matrix multiplication to date, with running time O(n2.37286).

This talk will give an overview of the main techniques and will also outline our recent improvement of the laser method.

Breakthroughs is a lecture series highlighting major new developments in theoretical computer science and is geared toward a scientific audience. 

If you require accommodation for communication, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.