Strassen partitions matrices into 2x2 blocks and computes seven recursive multiplications instead of eight, reducing asymptotic complexity to approximately O(n^2.81).
// Strassen skeleton (square matrices, power-of-two size)
vector<vector<int>> addM(const vector<vector<int>>& A, const vector<vector<int>>& B){
int n=A.size(); vector<vector<int>> C(n, vector<int>(n));
for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];
return C;
}
vector<vector<int>> subM(const vector<vector<int>>& A, const vector<vector<int>>& B){
int n=A.size(); vector<vector<int>> C(n, vector<int>(n));
for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i][j]=A[i][j]-B[i][j];
return C;
}Split A and B into A11/A12/A21/A22 and B11/B12/B21/B22.
Compute P1..P7 and reconstruct C blocks with additions/subtractions.
Better asymptotic time but higher constants and numerical sensitivity in practice.
Quiz coming soon for this algorithm.