Strassen Matrix Multiplication
Seven block products instead of eight.
Decision · step 9 of 10Karatsuba 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.
What you will see
Matrices split into quadrants; seven products combine.
Cost
| Best | O(n^2.807) |
|---|---|
| Average | O(n^2.807) |
| Worst | O(n^2.807) |
| Space | O(n^2) |
Exponent is log2(7).
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input.
Screen readers: Each call frame announces its range and result; each step announces split, recurse or combine.
Reduced motion: Frames appear and disappear with crossfades; ranges highlight without motion.
Before this
Taught by the same lesson
Karatsuba and Strassen covers these too, in the same run.