Strassen 「A11 1 Then A21 ]×[】-[aa] where C11= M1+M4-M5+M7 C12 = M3+M5 C21 = M2+M4 C22= M1-M2+M3+M6. Applied recursively, this yields running time 0(nog27)≈0(n2.8) Fast and stable matrix multiplication-p.6/44
Strassen Then A11 A12 A21 A22 × B11 B12 B21 B22 = C11 C12 C21 C22 , where C11 := M1 + M4 − M5 + M7 C12 := M3 + M5 C21 := M2 + M4 C22 := M1 − M2 + M3 + M6. Applied recursively, this yields running time O(nlog2 7) ≈ O(n2.8). Fast and stable matrix multiplication – p.6/44
Coppersmith and Winograd Don Coppersmith Shmuel Winograd Matrix multiplication via arithmetic progressions.Journal of Symbolic Computation [1990]. Used a thm on dense sets of integers containing no three terms in arithmetic progression(R.Salem D.C.Spencer [1942])to get an algorithm with running time(n2.376). Fast and stable matrix multiplication-p.7/44
Coppersmith and Winograd Don Coppersmith Shmuel Winograd Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation [1990]. Used a thm on dense sets of integers containing no three terms in arithmetic progression (R. Salem & D. C. Spencer [1942]) to get an algorithm with running time ≈ O(n2.376). Fast and stable matrix multiplication – p.7/44
Group-theoretic approach Chris Umans Henry Cohn A group-theoretic approach to matrix multiplication,FOCS Proceedings [2003]. Proposed embedding into group algebra to be combined with recursive partitioning. Fast and stable matrix multiplication-p.8/44
Group-theoretic approach Chris Umans Henry Cohn A group-theoretic approach to matrix multiplication, FOCS Proceedings [2003]. Proposed embedding into group algebra to be combined with recursive partitioning. Fast and stable matrix multiplication – p.8/44
Why group algebras? Multiplying two polynomials has complexity O(n log n)instead of O(n2)by embedding coefficients into CG]where G is a finite cyclic group of order N 2n,via the map p→{p(w):w=exp(2πki/N)}k=0,.,N-1 embed convolve extract into C[G] using FFT from C[G] The same can be done with matrix products, via the map A一∑m,yA(ar,y)x-ly.The group G must have special properties. Fast and stable matrix multiplication-p.9/44
Why group algebras? Multiplying two polynomials has complexity O(n log n) instead of O(n2) by embedding coefficients into C[G] where G is a finite cyclic group of order N ≥ 2n, via the map p 7→ {p(w) : w = exp(2πki/N)}k=0,...,N−1. embed into C[G] → convolve using FFT → extract from C[G] . The same can be done with matrix products, via the map A 7→ Px,y A(x, y)x−1y. The group G must have special properties. Fast and stable matrix multiplication – p.9/44
The algorithm Embed A,B in group algebra Perform FFT Reorganize results into new matrices Multiply new matrices recursively Reorganize results into new matrices ●Perform Inverse FFT Extract C=AB from group algebra Fast and stable matrix multiplication-p.10/44
The algorithm • Embed A, B in group algebra • Perform FFT • Reorganize results into new matrices • Multiply new matrices recursively • Reorganize results into new matrices • Perform Inverse FFT • Extract C = AB from group algebra Fast and stable matrix multiplication – p.10/44