Lecture Series on Fast Matrix Multiplication (Lecture 2)

Speaker: Prof. Amin Shokrollahi , ALGO


I will give a series of lectures that will probably last until the end of the semeser, each one hour, on the main ideas that have led to the currently fastest known matrix multiplication algorithms. I will start with the “classical” approach of bilinear complexity, deformations, and its culmination given by the Laser method of Strassen and its extensions by Coppersmith and Winograd. I will isolate and emphasize the combinatorial constructions that underly these algorithms. In the second part, I will lay out the method by Cohn and Umans using the theory of finite groups and their representations, and will show how that theory can be used to get fast matrix multiplication algorithms. Using the same combinatorics as in the classical approach, we obtain algorithms of the same asymptotic complexity.