PublicationsManuscripts

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.