ARC Colloquium: Virginia Williams, University of California, Berkeley

Date:

January 30, 2012 1:00 pm

Location:

Klaus 1116W, Georgia Tech, Atlanta, GA

Abstract:

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.