Group-theoretic Algorithms for Matrix Multiplication
Event details
| Date | 24.06.2010 |
| Hour | 09:15 |
| Speaker | Prof. Chris Umans. California Institute of Technology |
| Location | |
| Category | Conferences - Seminars |
We present a group-theoretic approach to producing fast algorithms for matrix multiplication. In this framework, one devises algorithms by constructing non-abelian groups with certain properties. The algorithms themselves are natural and make use of the discrete Fourier transform over these groups.
We construct several families of groups that achieve matrix multiplication exponent significantly less than 3 (but not better than the current best bound, 2.376...). This leads to two appealing conjectures, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.
This is joint work with Henry Cohn, Bobby Kleinberg, and Balazs Szegedy.
Prof. Umans' homepage
Practical information
- General public
- Free