Algorithm STRASSEN(A,B)
1. n ←number of rows of A
2. if n = 1 then return (a11b11)
3. else
4. Determine Aij and Bij for i, j = 1, 2 (blocks as before)
5. Compute M1, . . . , M7 (as below)
6. Compute C11, C12, C21, C22 (as below)
7. return C11 C12
C21 C22
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
