Los Angeles Combinatorics and Complexity Seminar: Designing Strassen's algorithm for matrix multiplication

Tuesday, November 24, 2020 at 10:15am to 10:45am

This is a past event.
Virtual Event

Joshua Grochow, University of Colorado at Boulder

Abstract: In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear, the key gain was made by showing that $2 \times 2$ matrix multiplication could be performed with only $7$ multiplications instead of $8$. The latter construction was arrived at by a process of elimination and appears to come out of thin air. We give a transparent proof of this algorithm using only a simple unitary $2$-design (coming from an irreducible representation of a finite group) and a few easy lines of calculation. Moreover, using basic facts from the representation theory of finite groups, we use $2$-designs coming from group orbits to generalize our construction to all $n$ (although the resulting algorithms aren't optimal for $n \ge 3$).

The talk will include background on matrix multiplication, and we'll be able to give the full proof. Based on joint work with C. Moore.


Dial-In Information

Zoom Meeting: https://ucla.zoom.us/j/96564290758

Meeting ID: 965 6429 0758
Passcode: Please see your email for the passcode to join via Zoom

Warning: You must be registered under your name to be admitted.

Event Type

Lecture / Talk / Workshop

Add this to your calendar

Recent Activity