Fast matrix multiplication

Fast matrix multiplication - Yuval Filmus

Yuval Filmus
Institute for Advanced Study; Member, School of Mathematics
February 25, 2014
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.