Matrix Multiplication I

These notes are based on a lecture given at the Toronto Student Seminar on February 2, 2012. The material is taken mostly from the book Algebraic Complexity Theory [ACT] and the lecture notes by Bläser and Bendun [Blä]. Starred sections are the ones I didn’t have time to cover. 1 Problem statement This lecture discusses the problem of multiplying two square matrices. We will be working in the algebraic complexity model. For us, an algorithm for multiplying two n × n matrices will mean a sequence of steps, where step l is a statement of the form • tl ← r for any r ∈ R • tl ← aij or tl ← bij for i, j ∈ {1,..., n} • tl ← tp ◦ tq, where p, q < l and ◦ ∈ {+,−, ·, /} • cij ← tp for p < l We will say that such an algorithm computes the product C = AB if at the end of the program, cik = j aijbjk. The running-time or complexity of the algorithm is the total number of steps, disregarding input and output steps. Our model is non-uniform. As an example, consider Strassen’s algorithm for multiplying two 2×2 matrices, as copied from Wikipedia: 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) c11 = m1 +m4 −m5 +m7 c12 = m3 +m5 c21 = m2 +m4 c22 = m1 −m2 +m3 +m6 1 In our model (using some benign shortcuts), it will look like this: t1 ← a11 + a22 t2 ← b11 + b22 t3 ← a21 + a22 t4 ← b12 − b22 t5 ← b21 − b11 t6 ← a11 + a12 t7 ← a21 − a11 t8 ← b11 + b12 t9 ← a12 − a22 t10 ← b21 + b22 t11 ← t1 · t2 t12 ← t3 · b11 t13 ← a11 · t4 t14 ← a22 · t5 t16 ← t6 · b22 t17 ← t7 · t8 t18 ← t9 · t10 t19 ← t11 + t14 t20 ← t19 − t15 c11 ← t20 + t17 c12 ← t13 + t15 c21 ← t12 + t14 t21 ← t11 − t12 t22 ← t21 + t13 c22 ← t22 + t16 The total complexity of this algorithm is 26 operations. Later we will write such algorithms in a much better way. Strassen’s algorithm can be used to multiply two 2n × 2n matrices. The key is to write the matrices in block form: