Write pseudocode for Strassen’s algorithm.

Pseudocode for SQUARE-MATRIX-MULTIPLY-STRASSEN(A, B):

n = A.rows
let C be a new n x n matrix
if n == 1
C11 = A11 * B11
else partition A, B, and C as in equations (4.9) in chapter text
let S1, S2, ..., and S10 be 10 new n/2 x n/2 matrices
let P1, P2, ..., and P7 be 7 new n/2 x n/2 matrices
/* calculate the sum matrices */
S1  = B12 - B22
S2  = A11 + A12
S3  = A21 + A22
S4  = B21 - B11
S5  = A11 + A22
S6  = B11 + B22
S7  = A12 - A22
S8  = B21 + B22
S9  = A11 - A21
S10 = B11 + B12
/* calculate the product matrices */
P1  = SQUARE-MATRIX-MULTIPLY-STRASSEN(A11, S1)
P2  = SQUARE-MATRIX-MULTIPLY-STRASSEN(S2, B22)
P3  = SQUARE-MATRIX-MULTIPLY-STRASSEN(S3, B11)
P4  = SQUARE-MATRIX-MULTIPLY-STRASSEN(A22, S4)
P5  = SQUARE-MATRIX-MULTIPLY-STRASSEN(S5, S6)
P6  = SQUARE-MATRIX-MULTIPLY-STRASSEN(S7, S8)
P7  = SQUARE-MATRIX-MULTIPLY-STRASSEN(S9, S10)
/* calculate the final product sub matrices */
C11 = P4 + P5 + P6 - P2
C12 = P1 + P2
C21 = P3 + P4
C22 = P1 + P5 - P3 - P7
return C