Fast matrix multiplication

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.

Date

Affiliation

Institute for Advanced Study; Member, School of Mathematics