AlgoScope

Strassen Matrix Multiplication

Seven block products instead of eight.

Divide and conquer, algorithm, expert
C11 is 19 and C12 is 22.formulavalueM1M2M3M4M5M6M7C row 1C row 2(a11 + a22)(b11 + b22)65(a21 + a22) b1135a11 (b12 - b22)-2a22 (b21 - b11)8(a11 + a12) b2224(a21 - a11)(b11 + b12)22(a12 - a22)(b21 + b22)-30M1 + M4 - M5 + M7, M3 + M519, 22
C11 is 19 and C12 is 22.formulavalueM1M2M3M4M5M6M7C row 1C row 2(a11 + a22)(b11 + b22)65(a21 + a22) b1135a11 (b12 - b22)-2a22 (b21 - b11)8(a11 + a12) b2224(a21 - a11)(b11 + b12)22(a12 - a22)(b21 + b22)-30M1 + M4 - M5 + M7, M3 + M519, 22

Karatsuba and Strassen: Strassen: seven products for a 2 x 2

Decision, step 9 of 10

Assemble the first row of C. C11 = M1 + M4 - M5 + M7 = 65 + 8 - 24 + -30 = 19, and C12 = M3 + M5 = -2 + 24 = 22. Check C11 the direct way: 1 x 5 + 2 x 7 = 19.

How karatsuba and strassen works

Cost

Best
O(n^2.807)
Average
O(n^2.807)
Worst
O(n^2.807)
Space
O(n^2)

Exponent is log2(7).

Taught by the same lesson

Karatsuba and Strassen covers these too, in the same run.