Strassen’s Algorithm
Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 14(3):3543 356, 1969.
https://link.springer.com/article/10.1007/BF02165411
- divide-and-conquer, but make the recursion tree less “bushy”.
S01 = B12 - B22
S02 = A11 + A12
S03 = A21 + A22
S04 = B21 - B11
S05 = A11 + A22
S06 = B11 + B22
S07 = A12 - A22
S08 = B21 + B22
S09 = A11 - A21
S10 = B11 + B12
P1 = A11 * S01 = A11 * B12 - A11 * B22
P2 = S02 * B22 = A11 * B22 + A12 * B22
P3 = S03 * B11 = A21 * B11 + A22 * B11
P4 = A22 * S04 = A22 * B21 - A22 * B11
P5 = S05 * S06 = A11 * B11 + A11 * B22 + A22 * B11 + A22 * B22
P6 = S07 * S08 = A12 * B21 + A12 * B22 - A22 * B21 - A22 * B22
P7 = S09 * S10 = A11 * B11 + A11 * B12 - A21 * B11 - A21 * B12
C11 = P5 + P4 - P2 + P6
C12 = P1 + P2
C21 = P3 + P4
C22 = P5 + P1 - P3 - P7- Strassen’s method can be helpful for large matrices, but they tend to be sparse, in that case sparse methods work better.