Strassen Matrix Multiplication
Seven block products instead of eight.
Karatsuba and Strassen: Strassen: seven products for a 2 x 2
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.
Cost
- Best
- O(n^2.807)
- Average
- O(n^2.807)
- Worst
- O(n^2.807)
- Space
- O(n^2)
Exponent is log2(7).
Before this
Taught by the same lesson
Karatsuba and Strassen covers these too, in the same run.