Departmental Colloquium
Joseph M. Landsberg
Texas A&M University
On the geometry of matrix multiplication
Abstract: Our story begins with a spectacular failure:
The standard algorithm to multiply two nxn matrices uses $n^3$ multiplications. In 1969, while attempting to show that the standard algorithm was optimal, V. Strassen discovered an explicit algorithm to multiply 2x2 matrices using 7 multiplications rather than $8=2^3$. It is a central question to determine just how efficiently one can multiply nxn matrices, both practically and asymptotically.
In this talk, I will present a history of the problem, both of upper and lower complexity bounds I will discuss how geometry, more precisely algebraic geometry and representation theory,
are used. In particular, I will explain how, had someone asked him 100 years ago, the algebraic geometer Terracini could have
predicted Strassen's algorithm. The talk will conclude with the recent use of representation theory to construct algorithms, more precisely, rank decompositions.
For those who can't wait for the talk, a detailed history and the state of the art appears in Landsberg, J. (2017). Geometry and Complexity Theory (Cambridge Studies in Advanced Mathematics 169).
Tea at 4:15 PM
Friday February 16, 2018 at 3:00 PM in SEO 636