Strassen Algorithm

Strassen’s recursive algorithm for multiplying $n\times n$ matrices runs in $\Theta (n^{\log 7})$. Since $\log 7$ lies between 2.80 and 2.81, Strassen’s algorithm runs in $O(n^{2.81})$.

For two by two matrices, Strassen noticed that we can do 7 multiplications instead of 8.

Analysis: 7 recursive calls in size $\frac{n}{2}+\Theta (n^2)$ additions ⇒ $T(n)=\Theta (n^{{\log }_{2}7})$

Apparently, we cannot get better than 7 multiplications.

We have traded off one matrix multiplication for a constant number of matrix additions.

Pseudocode for Strassen’s algorithm?

function Strassen(Matrix A, Matrix B)
    // Check if matrices are of appropriate size
    if (A.rows != A.cols) or (B.rows != B.cols) or (A.rows != B.rows)
        return "Matrices are not square or of compatible sizes"

    // Base case: If the matrices are small enough, use regular matrix multiplication
    if (A.rows == 1)
        return A * B
    
    // Partition matrices A and B into submatrices
    n = A.rows
    mid = n / 2

    A11, A12, A21, A22 = partition(A)
    B11, B12, B21, B22 = partition(B)

    // Recursive steps to calculate the products of submatrices
    P1 = Strassen(A11 + A22, B11 + B22)
    P2 = Strassen(A21 + A22, B11)
    P3 = Strassen(A11, B12 - B22)
    P4 = Strassen(A22, B21 - B11)
    P5 = Strassen(A11 + A12, B22)
    P6 = Strassen(A21 - A11, B11 + B12)
    P7 = Strassen(A12 - A22, B21 + B22)

    // Calculate the submatrices of the result
    C11 = P1 + P4 - P5 + P7
    C12 = P3 + P5
    C21 = P2 + P4
    C22 = P1 - P2 + P3 + P6

    // Combine the submatrices into the resulting matrix
    C = combine(C11, C12, C21, C22)
    
    return