AntInLoop

Strassen's Matrix Multiplication Algorithm

Strassen's Algorithm multiplies two n x n matrices in O(n^log2(7)) ≈ O(n^2.807) time—beating naive O(n^3)—by reducing 8 recursive submatrix multiplications to 7 clever linear combinations.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Strassen's Matrix Multiplication Algorithm

Standard $n \times n$ matrix multiplication takes $O(n^3)$ time (8 recursive $n/2 \times n/2$ multiplications: $T(n) = 8T(n/2) + O(n^2) = O(n^3)$). Volker Strassen (1969) discovered how to compute the exact same product using only 7 recursive multiplications ($M_1 \dots M_7$) plus 18 matrix additions/subtractions, yielding:

$T(n) = 7\,T(n / 2) + O(n^2) \implies O(n^{\log_2 7}) \approx O(n^{2.8074})$

At a Glance

| Property | Naive Multiplication | Strassen's Algorithm |

| :--- | :---: | :---: |

| Time Complexity | $O(n^3)$ | $O(n^{\log_2 7}) \approx O(n^{2.807})$ |

| Recursive Subproblems | 8 | 7 |

| Practical Crossover | Faster for $n \le 64$ | Switch to naive multiplication at base size $n \le 64$! |

---

Practice Problems

Hard

1. Strassen's Matrix Multiplication (With Base-Case Cutoff)

Multiply two $n \times n$ matrices (power-of-2 size) using Strassen's 7 products.

Approach: Split $A, B$ into quadrants, compute $M_1 \dots M_7$ recursively, and combine into $C_{11}, C_{12}, C_{21}, C_{22}$. Fall back to direct multiplication for small submatrices!

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <vector>

using Mat = std::vector<std::vector<long long>>;

Mat add(const Mat& A, const Mat& B, int sign = 1) {
    int n = static_cast<int>(A.size());
    Mat C(n, std::vector<long long>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) C[i][j] = A[i][j] + sign * B[i][j];
    return C;
}

Mat strassen(const Mat& A, const Mat& B) {
    int n = static_cast<int>(A.size());
    if (n <= 2) {
        Mat C(n, std::vector<long long>(n, 0));
        for (int i = 0; i < n; ++i)
            for (int k = 0; k < n; ++k)
                for (int j = 0; j < n; ++j) C[i][j] += A[i][k] * B[k][j];
        return C;
    }
    int h = n / 2;
    auto sub = [&](const Mat& M, int r, int c) {
        Mat S(h, std::vector<long long>(h));
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < h; ++j) S[i][j] = M[r + i][c + j];
        return S;
    };
    Mat A11 = sub(A, 0, 0), A12 = sub(A, 0, h), A21 = sub(A, h, 0), A22 = sub(A, h, h);
    Mat B11 = sub(B, 0, 0), B12 = sub(B, 0, h), B21 = sub(B, h, 0), B22 = sub(B, h, h);

    Mat M1 = strassen(add(A11, A22), add(B11, B22));
    Mat M2 = strassen(add(A21, A22), B11);
    Mat M3 = strassen(A11, add(B12, B22, -1));
    Mat M4 = strassen(A22, add(B21, B11, -1));
    Mat M5 = strassen(add(A11, A12), B22);
    Mat M6 = strassen(add(A21, A11, -1), add(B11, B12));
    Mat M7 = strassen(add(A12, A22, -1), add(B21, B22));

    Mat C11 = add(add(M1, M4), add(M7, M5, -1));
    Mat C12 = add(M3, M5);
    Mat C21 = add(M2, M4);
    Mat C22 = add(add(M1, M3), add(M6, M2, -1));

    Mat C(n, std::vector<long long>(n));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < h; ++j) {
            C[i][j] = C11[i][j]; C[i][j + h] = C12[i][j];
            C[i + h][j] = C21[i][j]; C[i + h][j + h] = C22[i][j];
        }
    }
    return C;
}

int main() {
    Mat A = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 1, 2, 3}, {4, 5, 6, 7}};
    Mat B = {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
    Mat C = strassen(A, B);
    std::cout << C[0][3] << " " << C[1][2] << " " << C[3][3] << "\n"; // 4 7 7
    return 0;
}

</details>

---

Related Algorithms