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
- Divide and Conquer — general paradigm behind Strassen's.
- Master Theorem — proves $T(n) = 7T(n/2) + O(n^2) = O(n^{\log_2 7})$.