Matrix multiplication

Yuval Filmus

An exposition on algorithms for matrix multiplication, in two parts:

  • Part 1:
    • The arithmetic model.
    • Bilinear normal form for matrix multiplication.
    • Tensor notation and tensor rank.
    • Border rank.
    • Schönhage’s $\tau$ theorem (the asymptotic sum inequality).
    • Coppersmith’s $\tilde{O}(n^2)$ algorithm for multiplying rectangular matrices.
  • Part 2:
    • The laser method.
    • The Coppersmith–Winograd algorithms.
    • Capacity: the fundamental combinatorial underpinning of the Coppersmith–Winograd method.

These talks were given in the Toronto Student Seminar on 2/2/2012 and 9/2/2012, though the second one has been significantly updated since.

The talks were given again in the IAS theory seminar, on 25/2/2014 and 4/3/2014. The second part has been significantly updated: the combinatorial construction has been simplified following Davie and Stothers, and the general presentation follows Le Gall’s recent paper.