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
If you have any question or suggestion or you have found any error in this solution, please leave a comment below.