Aim : Strassen’s multiplication
Date : 11/09/2025
Algorithm :
STRASSEN_MULTIPLY(A, B, n)
if n = 1
then
return [[ A[1][1] * B[1][1] ]]
end
if
Partition A into: A11, A12, A21, A22
Partition B into: B11, B12, B21, B22
M1 = STRASSEN_MULTIPLY(A11 + A22, B11 + B22)
M2 = STRASSEN_MULTIPLY(A21 + A22, B11)
M3 = STRASSEN_MULTIPLY(A11, B12 - B22)
M4 = STRASSEN_MULTIPLY(A22, B21 - B11)
M5 = STRASSEN_MULTIPLY(A11 + A12, B22)
M6 = STRASSEN_MULTIPLY(A21 - A11, B11 + B12)
M7 = STRASSEN_MULTIPLY(A12 - A22, B21 + B22)
C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6
return C
Code :
#include <iostream>
#include <cmath>
using namespace std;
int** allocateMatrix(int n)
{
int** M = new int*[n];
for (int i = 0; i < n; i++)
M[i] = new int[n]();
return M;
}
void freeMatrix(int** M, int n)
{
for (int i = 0; i < n; i++)
delete[] M[i];
delete[] M;
}
int** addMatrix(int** A, int** B, int n)
{
int** C = allocateMatrix(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;
}
int** subMatrix(int** A, int** B, int n)
{
int** C = allocateMatrix(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;
}
int** strassen(int** A, int** B, int n)
{
int** C = allocateMatrix(n);
if (n == 1)
{
C[0][0] = A[0][0] * B[0][0];
return C;
}
int k = n / 2;
int** A11 = allocateMatrix(k);
int** A12 = allocateMatrix(k);
int** A21 = allocateMatrix(k);
int** A22 = allocateMatrix(k);
int** B11 = allocateMatrix(k);
int** B12 = allocateMatrix(k);
int** B21 = allocateMatrix(k);
int** B22 = allocateMatrix(k);
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++)
{
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + k];
A21[i][j] = A[i + k][j];
A22[i][j] = A[i + k][j + k];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j + k];
B21[i][j] = B[i + k][j];
B22[i][j] = B[i + k][j + k];
}
}
int** M1 = strassen(addMatrix(A11, A22, k),
addMatrix(B11, B22, k), k);
int** M2 = strassen(addMatrix(A21, A22, k), B11, k);
int** M3 = strassen(A11, subMatrix(B12, B22, k), k);
int** M4 = strassen(A22, subMatrix(B21, B11, k), k);
int** M5 = strassen(addMatrix(A11, A12, k), B22, k);
int** M6 = strassen(subMatrix(A21, A11, k), addMatrix(B11, B12,
k), k);
int** M7 = strassen(subMatrix(A12, A22, k), addMatrix(B21, B22,
k), k);
int** C11 = subMatrix(addMatrix(addMatrix(M1, M4, k), M7, k),
M5, k);
int** C12 = addMatrix(M3, M5, k);
int** C21 = addMatrix(M2, M4, k);
int** C22 = addMatrix(subMatrix(addMatrix(M1, M3, k), M2, k),
M6, k);
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++)
{
C[i][j] = C11[i][j];
C[i][j + k] = C12[i][j];
C[i + k][j] = C21[i][j];
C[i + k][j + k] = C22[i][j];
}
} return C;
}
int nextPowerOf2(int n)
{
int p = 1;
while (p < n) p *= 2;
return p;
}
int** strassenMultiply(int** A, int** B, int n)
{
int m = nextPowerOf2(n);
int** A_padded = allocateMatrix(m);
int** B_padded = allocateMatrix(m);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
A_padded[i][j] = A[i][j];
B_padded[i][j] = B[i][j];
}
int** C_padded = strassen(A_padded, B_padded, m);
int** C = allocateMatrix(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = C_padded[i][j];
return C;
}
int main()
{
int n;
cout << "Enter size of matrix: ";
cin >> n;
int** A = allocateMatrix(n);
int** B = allocateMatrix(n);
cout << "Enter elements of matrix A:\n";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> A[i][j];
cout << "Enter elements of matrix B:\n";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> B[i][j];
int** C = strassenMultiply(A, B, n);
cout << "Resultant Matrix C (A x B):\n";
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << C[i][j] << " ";
cout << endl;
}
return 0;
}
Output:
