pdf icon
Theory of Computing Library
Graduate Surveys 5
Fast Matrix Multiplication
Published: December 24, 2013    (60 pages)
Download article from ToC site:
[PDF (473K)] [PS (2351K)] [Source ZIP]
Keywords: fast matrix multiplication, bilinear complexity, tensor rank
ACM Classification: F.2.2
AMS Classification: 68Q17, 68Q25

Abstract: [Plain Text Version]

We give an overview of the history of fast algorithms for matrix multiplication. Along the way, we look at some other fundamental problems in algebraic complexity like polynomial evaluation.

This exposition is self-contained. To make it accessible to a broad audience, we only assume a minimal mathematical background: basic linear algebra, familiarity with polynomials in several variables over rings, and rudimentary knowledge in combinatorics should be sufficient to read (and understand) this article. This means that we have to treat tensors in a very concrete way (which might annoy people coming from mathematics), occasionally prove basic results from combinatorics, and solve recursive inequalities explicitly (because we want to annoy people with a background in theoretical computer science, too).