Group Theoretic Algorithms For Fast matrix Multiplication

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Group Theoretic Algorithms For Fast matrix Multiplication
Speaker:Balazs Szedgedy
Affiliation:IAS
Date:Tuesday, March 14
Time/Room:10:30am - 12:30pm/S-101

In 1969 Strassen discovered the surprising fact that it is possible to multiply two 2x2 matrices by using only 7 multiplications. This leads to an algorithm which multiplies two nxn matrices with n^(2.81+o(1)) field operations. Coppersmith and Winograd in 1990 improved the constant 2.81 to 2.376 but the best constant is still unknown. We present group theoretic algorithms for matrix mltiplication and we discuss undelying combinatorial problems. This is a joint work with: H.Cohn, R.Kleinberg and C.Umans