Fast and stable matrix multiplication Olga Holtz Department of Mathematics University of California-Berkeley holtz@math.berkeley.edu joint work James Demmel,loana Dumitriu and Robert Kleinberg Fast and stable matrix mtiplicaion-p.1/44
Fast and stable matrix multiplication Olga Holtz Department of Mathematics University of California-Berkeley holtz@math.berkeley.edu joint work James Demmel, Ioana Dumitriu and Robert Kleinberg Fast and stable matrix multiplication – p.1/44
The quest for speed How fast can one multiply two nxn matrices? .Standard multiplication:O(n3)operations. .Strassen's algorithm:O(2.81)operations. 0.… .Coppersmith and Winograd's algorithm:O(n2.38) operations. 。lsO(m2)achievable? Fast and stable matrix multiplication-p.2/44
The quest for speed How fast can one multiply two n×n matrices? • Standard multiplication: O(n3) operations. • Strassen’s algorithm: O(n2.81) operations. • ... • Coppersmith and Winograd’s algorithm: O(n2.38) operations. • Is O(n2) achievable? Fast and stable matrix multiplication – p.2/44
Why should we care? Complexity of matrix multiplication complexity of 'almost all"matrix problems: solving linear systems, evaluating determinants, 。LU factorization, many more. See P.Burgisser,M.Clausen,M.A.Shokrollahi Algebraic complexity theory. Fast and stable matrix multiplication-p.3/44
Why should we care? Complexity of matrix multiplication = complexity of “almost all” matrix problems: • solving linear systems, • evaluating determinants, • LU factorization, • many more. See P. Bürgisser, M. Clausen, M. A. Shokrollahi Algebraic complexity theory. Fast and stable matrix multiplication – p.3/44
Strassen's algorithm Main idea: Multiplication by recursively partitioning into smaller blocks. To be faster than O(n3), Volker Strassen this needs a method to Gaussian elimination multiply small matrices is not optimal.Numer. (order k)using o() Mathematik [1969]. multiplications. Fast and stable matrix multiplication-p.4/44
Strassen’s algorithm Volker Strassen Gaussian elimination is not optimal. Numer. Mathematik [1969]. Main idea: • Multiplication by recursively partitioning into smaller blocks. • To be faster than O(n3), this needs a method to multiply small matrices (order k) using o(k3) multiplications. Fast and stable matrix multiplication – p.4/44
Strassen [细 A12 7× B11 B12 requires only A22 B21B22 7 multiplications: M1:=(A11+A22)(B11+B22) M2 :=(A21+A22)B11 M3:=A11(B12-B22) M4:=A22(B21-B11) M5:=(A11+A12)B22 M6= (A21-A11)(B11+B12) M7 = （A12-A22)(B21+B22). Fast and stable matrix multiplication-p.5/44
Strassen A11 A12 A21 A22 × B11 B12 B21 B22 requires only 7 multiplications: M1 := (A11 + A22)(B11 + B22) M2 := (A21 + A22)B11 M3 := A11(B12 − B22) M4 := A22(B21 − B11) M5 := (A11 + A12)B22 M6 := (A21 − A11)(B11 + B12) M7 := (A12 − A22)(B21 + B22). Fast and stable matrix multiplication – p.5/44