Properties required For unambiguous embedding into C[G]there must be three subgroups H1,I12,HI3 with the triple product property h1h2h3=1,hi∈Hi→h1=h2=h3=1 (can be generalized to other subsets of G). For the resulting algorithm to be faster than O(n3),we must beat the sum of the cubes: |HlH2l3>∑d (d;are the character degrees of G). Fast and stable matrix multiplication-p.11/44
Properties required • For unambiguous embedding into C[G] there must be three subgroups H1, H2, H3 with the triple product property : h1h2h3 = 1, hi ∈ Hi =⇒ h1 = h2 = h3 = 1 (can be generalized to other subsets of G). • For the resulting algorithm to be faster than O(n3), we must beat the sum of the cubes: |H1| |H2| |H3| > Pj d3j (dj are the character degrees of G). Fast and stable matrix multiplication – p.11/44
Wedderburn's theorem Theorem.The group algebra of a finite group G decomposes as the direct product C[G兰①dxdX.Xcde×d of matrix algebras of orders d1,...,d&.These orders are the character degrees of G,or the dimensions of its irreducible representations. Fast and stable matrix multiplication-p.12/44
Wedderburn’s theorem Theorem. The group algebra of a finite group G decomposes as the direct product C[G] ∼= Cd1×d1 × · · · × Cdk×dk of matrix algebras of orders d1, . . ., dk. These orders are the character degrees of G, or the dimensions of its irreducible representations. Fast and stable matrix multiplication – p.12/44
Beating the sum of the cubes Balazs Szegedy Henry Cohn Chris Umans Bobby Kleinberg Group-theoretic algorithms for matrix multiplication, FOCS Proceedings [2005]. Found groups with subsets beating the sum of the cubes and satisfying the triple product property. Press coverage:SIAM News [Nov 2005]by Sara Robinson. Fast and stable matrix multiplication-p.13/44
Beating the sum of the cubes Balázs Szegedy Henry Cohn Chris Umans Bobby Kleinberg Group-theoretic algorithms for matrix multiplication, FOCS Proceedings [2005]. Found groups with subsets beating the sum of the cubes and satisfying the triple product property. Press coverage: SIAM News [Nov 2005] by Sara Robinson. Fast and stable matrix multiplication – p.13/44
Error analysis Jim Demmel loana Dumitriu Olga Holtz Bobby Kleinberg Fast matrix multiplication is stable,ArXiv Math.NA/0603207 [2006]. Main question:Do you get the right answer in the presence of roundoff?To answer,need error analysis for a large class of recursive matrix multiplication algorithms. Fast and stable matrix multiplication-p.14/44
Error analysis Jim Demmel Ioana Dumitriu Olga Holtz Bobby Kleinberg Fast matrix multiplication is stable, ArXiv Math.NA/0603207 [2006]. Main question: Do you get the right answer in the presence of roundoff? To answer, need error analysis for a large class of recursive matrix multiplication algorithms. Fast and stable matrix multiplication – p.14/44
Method Forward error analysis in the spirit of D.Bini and G.Lotti Stability of fast algorithms for matrix multiplication,Numer.Mathematik [1980/81]. What was missing: More general roundoff assumptions .Wider scope: nonstationary algorithms algorithms with pre-and post-processing Fast and stable matrix multiplication-p.15/44
Method Forward error analysis in the spirit of D. Bini and G. Lotti Stability of fast algorithms for matrix multiplication, Numer. Mathematik [1980/81]. What was missing: • More general roundoff assumptions • Wider scope: nonstationary algorithms algorithms with pre- and post- processing Fast and stable matrix multiplication – p.15/44