Theory of Computing Library Graduate Surveys
---------------------------------------------------
Title : Fast Matrix Multiplication
Authors : Markus Blaeser
Number : 5
Pages : 1-60
URL : http://www.theoryofcomputing.org/articles/gs005
Abstract
--------
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).