Write pseudocode for Strassen’s algorithm.

Up until this point in the text, we’ve been working off the simplifying assumption that our input matrices \(A\) and \(B\) are \(2^i \times 2^i\) for some positive integer \(i\) which means the same is true of all \(S\) and \(P\) matrices (although their size is \(2^{i-1} \times 2^{i-1}\) where \(i\) may be \(0\)). The following pseudocode is written with this assumption in mind, as well as if \(C\) were a \(2 \times 2\) matrix though this may not be the case.

Nevertheless, in steps 24-27 when we are assigning values to \(C\), the fact that \(C\) is of size \(n \times n\) and our various \(P\) and \(S\) matrices are of size \(\frac{n}{2} \times \frac{n}{2}\) means we can pattern the assignments to four quadrants of \(C\) much like we would if \(C\) were in fact a \(2 \times 2\) matrix. The specific mechanics of how this would be expressed by pseudocode for a matrix \(C\) of variable size did not seem relevant to the task at hand and so I decided to skip the additional effort since this exercise is already quite tedious.

STRASSEN-ALGORITHM(A, B)

01 n = A.rows

02 let C be a new n x n matrix

03 if n == 1

04      C₁₁ = A₁₁ · B₁₁

05 else partition A, B, and C as in equations (4.9)

06 let S₁, S₂, S₃, S₄, S₅, S₆, S₇, S₈, S₉, S₁₀, P₁, P₂, P₃, P₄, P₅, P₆ and P₇ be new n/2 x n/2 matrices

07 S₁ = B₁₂ - B₂₂

08 S₂ = A₁₁ + A₁₂

09 S₃ = A₂₁ + A₂₂

10 S₄ = B₂₁ - B₁₁

11 S₅ = A₁₁ + A₂₂

12 S₆ = B₁₁ + B₂₂

13 S₇ = A₁₂ - A₂₂

14 S₈ = B₂₁ + B₂₂

15 S₉ = A₁₁ - A₂₁

16 S₁₀ = B₁₁ + B₁₂

17 P₁ = STRASSEN-ALGORITHM(A₁₁, S₁)

18 P₂ = STRASSEN-ALGORITHM(S₂, B₂₂)

19 P₃ = STRASSEN-ALGORITHM(S₃, B₁₁)

20 P₄ = STRASSEN-ALGORITHM(A₂₂, S₄)

21 P₅ = STRASSEN-ALGORITHM(S₅, S₆)

22 P₆ = STRASSEN-ALGORITHM(S₇, S₈)

23 P₇ = STRASSEN-ALGORITHM(S₉, S₁₀)

24 C₁₁ = P₅ + P₄ - P₂ + P₆

25 C₁₂ = P₁ + P₂

26 C₂₁ = P₃ + P₄

27 C₂₂ = P₅ + P₁ - P₃ - P₇

28 return C