Strassens Matrix Multiplication

Language: C++

#include <iostream>
#include <vector>
using namespace std;

// Function to add two matrices
vector<vector<int>> matrixAddition(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int n = A.size();
    vector<vector<int>> result(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result[i][j] = A[i][j] + B[i][j];
        }
    }
    return result;
}

// Function to subtract two matrices
vector<vector<int>> matrixSubtraction(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int n = A.size();
    vector<vector<int>> result(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result[i][j] = A[i][j] - B[i][j];
        }
    }
    return result;
}

// Function to perform standard matrix multiplication for small matrices
vector<vector<int>> standardMatrixMultiplication(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int n = A.size();
    vector<vector<int>> result(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return result;
}

// Function to divide matrix into submatrices
void splitMatrix(const vector<vector<int>>& A, vector<vector<int>>& A11, vector<vector<int>>& A12,
                 vector<vector<int>>& A21, vector<vector<int>>& A22) {
    int n = A.size();
    int mid = n / 2;

    for (int i = 0; i < mid; i++) {
        for (int j = 0; j < mid; j++) {
            A11[i][j] = A[i][j];
            A12[i][j] = A[i][j + mid];
            A21[i][j] = A[i + mid][j];
            A22[i][j] = A[i + mid][j + mid];
        }
    }
}

// Function to join submatrices into a single matrix
void joinMatrix(vector<vector<int>>& C, const vector<vector<int>>& C11, const vector<vector<int>>& C12,
                const vector<vector<int>>& C21, const vector<vector<int>>& C22) {
    int n = C.size();
    int mid = n / 2;

    for (int i = 0; i < mid; i++) {
        for (int j = 0; j < mid; j++) {
            C[i][j] = C11[i][j];
            C[i][j + mid] = C12[i][j];
            C[i + mid][j] = C21[i][j];
            C[i + mid][j + mid] = C22[i][j];
        }
    }
}

// Strassen's Matrix Multiplication
vector<vector<int>> strassensMatrixMultiplication(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int n = A.size();

    if (n <= 2) {
        return standardMatrixMultiplication(A, B);
    }

    int mid = n / 2;

    // Divide matrices into submatrices
    vector<vector<int>> A11(mid, vector<int>(mid));
    vector<vector<int>> A12(mid, vector<int>(mid));
    vector<vector<int>> A21(mid, vector<int>(mid));
    vector<vector<int>> A22(mid, vector<int>(mid));

    vector<vector<int>> B11(mid, vector<int>(mid));
    vector<vector<int>> B12(mid, vector<int>(mid));
    vector<vector<int>> B21(mid, vector<int>(mid));
    vector<vector<int>> B22(mid, vector<int>(mid));

    splitMatrix(A, A11, A12, A21, A22);
    splitMatrix(B, B11, B12, B21, B22);

    // Strassen's Matrix Multiplication calculations
    vector<vector<int>> M1 = strassensMatrixMultiplication(matrixAddition(A11, A22), matrixAddition(B11, B22));
    vector<vector<int>> M2 = strassensMatrixMultiplication(matrixAddition(A21, A22), B11);
    vector<vector<int>> M3 = strassensMatrixMultiplication(A11, matrixSubtraction(B12, B22));
    vector<vector<int>> M4 = strassensMatrixMultiplication(A22, matrixSubtraction(B21, B11));
    vector<vector<int>> M5 = strassensMatrixMultiplication(matrixAddition(A11, A12), B22);
    vector<vector<int>> M6 = strassensMatrixMultiplication(matrixSubtraction(A21, A11), matrixAddition(B11, B12));
    vector<vector<int>> M7 = strassensMatrixMultiplication(matrixSubtraction(A12, A22), matrixAddition(B21, B22));

    vector<vector<int>> C11 = matrixAddition(matrixSubtraction(matrixAddition(M1, M4), M5), M7);
    vector<vector<int>> C12 = matrixAddition(M3, M5);
    vector<vector<int>> C21 = matrixAddition(M2, M4);
    vector<vector<int>> C22 = matrixAddition(matrixAddition(matrixSubtraction(M1, M2), M3), M6);

    // Join submatrices into result matrix
    vector<vector<int>> result(n, vector<int>(n));
    joinMatrix(result, C11, C12, C21, C22);

    return result;
}

// Function to display matrix
void displayMatrix(const vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int n;
    cout << "Enter the size of the square matrices: ";
    cin >> n;

    cout << "Enter elements of matrix A of size " << n << "x" << n << " row-wise:" << endl;
    vector<vector<int>> A(n, vector<int>(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 of size " << n << "x" << n << " row-wise:" << endl;
    vector<vector<int>> B(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> B[i][j];
        }
    }

    cout << "Matrix A:" << endl;
    displayMatrix(A);

    cout << "Matrix B:" << endl;
    displayMatrix(B);

    vector<vector<int>> result = strassensMatrixMultiplication(A, B);

    cout << "Matrix A * B (Strassen's Multiplication):" << endl;
    displayMatrix(result);

    return 0;
}

Output:

Enter the size of the square matrices: 2
Enter elements of matrix A of size 2x2 row-wise:
 1 4 2 5
Enter elements of matrix B of size 2x2 row-wise:
 2 56 4 8
Matrix A:
 1 4
 2 5
Matrix B:
 2 56
 4 8
Matrix A * B (Strassen's Multiplication):
 18 88
 24 152