On Matrix Multiplication Algorithms | Richard M. Karp Distinguished Lecture

Matrix multiplication is a crucial component in many applications, from mathematics and computer science to the sciences, engineering, and even computer games. And fast matrix multiplication is a central goal in algorithms research. In 1969, Strassen introduced the first algorithm for multiplying n by n matrices that outperformed the O(n3) time approach implied by the problem’s definition, achieving a running time of only O(n{2.81}). Over the decades, faster and faster algorithms were discovered. The goal is to find the smallest real value omega such that n by n matrices can be multiplied in n{omega + o(1)} time in the worst case. Because writing down the n by n output requires at least n2 time, we know that omega is at least 2. Whether omega = 2 is possible remains unknown. The current best bound is omega < 2.37134. In this Richard M. Karp Distinguished Lecture in the Complexity and Linear Algebra program, Virginia Vassilevska Williams examines progress on matrix multiplication algorithms over the decades and offers some intuition about where the research area may be headed.