Fast matrix multiplication

Computer Science/Discrete Mathematics Seminar II
Topic:Fast matrix multiplication
Speaker:Yuval Filmus
Affiliation:Member, School of Mathematics
Date:Tuesday, March 4
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2014/0304-YuvalFilmus

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory of fast matrix multiplication, starting with Strassen's algorithm and culminating with the state-of-the-art Coppersmith-Winograd algorithm and its recent improvements. We also describe Coppersmith's \(O(n^2 log^2 n)\) algorithm for multiplying rectangular matrices, used by Ryan Williams in his separation of ACC and NEXP.