Multiplying matrices faster than Coppersmith-Winograd
Speaker: Virginia Vassilevska Williams , UC Berkeley and Stanford U
Date: February 7 2012
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, be@csail.mit.edu
Relevant URL: In 1987 Coppersmith and Winograd presented an algorithm to multiply two n by n matrices using O(n^{2.3755}) arithmetic operations.
This algorithm has remained the theoretically fastest approach for matrix multiplication for 24 years.
We have recently been able to design an algorithm that multiplies n by n matrices and uses at most O(n^{2.3727}) arithmetic operations, thus improving the Coppersmith-Winograd running time.
The improvement is based on a recursive application of the original Coppersmith-Winograd construction, together with a general theorem that reduces the analysis of the algorithm running time to solving a nonlinear constraint program.
The final analysis is then done by numerically solving this program.
To fully optimize the running time we utilize an idea from independent work by Stothers who claimed an O(n^{2.3737}) runtime in his Ph.D. thesis.
The aim of the talk will be to give some intuition and to highlight the main new ideas needed to obtain the improvement.
See other events that are part of Theory Colloquium 2011/2012
See other events happening in February 2012
