{"post":"

Matrix Multiplication in C++: Naive vs Strassen's Algorithm

Introduction

Matrix multiplication is a fundamental operation in linear algebra with applications in computer graphics, machine learning, and scientific computing. We'll explore two implementation approaches:

1. Basic (Naive) Matrix Multiplication

2. Strassen's Algorithm (Optimized)

Technique 1: Basic Matrix Multiplication

Algorithm Overview

The naive approach implements the standard mathematical definition of matrix multiplication:

For matrices A (m×n) and B (n×p), their product C (m×p) is calculated as:

C[i][j] = Σ(A[i][k] × B[k][j]) for k from 0 to n-1

Implementation

#include <iostream>\nusing namespace std;\nconst int MAX_SIZE = 5;\n\nvoid multiply(int A[MAX_SIZE][MAX_SIZE], int B[MAX_SIZE][MAX_SIZE], \n             int result[MAX_SIZE][MAX_SIZE], int r1, int c1, int r2, int c2) {\n\n    if (c1 != r2) {\n        cout << \"Matrix multiplication not possible!\\n\";\n        return;\n    }\n\n    for (int i = 0; i < r1; i++) {\n        for (int j = 0; j < c2; j++) {\n            result[i][j] = 0;\n            for (int k = 0; k < c1; k++) {\n                result[i][j] += A[i][k] * B[k][j];\n            }\n        }\n    }\n}\n\nvoid display(int matrix[MAX_SIZE][MAX_SIZE], int rows, int cols) {\n    for (int i = 0; i < rows; i++) {\n        for (int j = 0; j < cols; j++) {\n            cout << matrix[i][j] << \" \";\n        }\n        cout << \"\\n\";\n    }\n}\n\nint main() {\n    int A[MAX_SIZE][MAX_SIZE], B[MAX_SIZE][MAX_SIZE], C[MAX_SIZE][MAX_SIZE];\n    int r1, c1, r2, c2;\n\n    cout << \"Enter rows and columns for first matrix: \";\n    cin >> r1 >> c1;\n    cout << \"Enter rows and columns for second matrix: \";\n    cin >> r2 >> c2;\n\n    if (c1 != r2) {\n        cout << \"Error: Columns of first matrix must equal rows of second matrix!\\n\";\n        return 1;\n    }\n\n    cout << \"Enter elements of first matrix:\\n\";\n\n    for (int i = 0; i < r1; i++)\n        for (int j = 0; j < c1; j++)\n            cin >> A[i][j];\n\n    cout << \"Enter elements of second matrix:\\n\";\n\n    for (int i = 0; i < r2; i++)\n        for (int j = 0; j < c2; j++)\n            cin >> B[i][j];\n\n    multiply(A, B, C, r1, c1, r2, c2);\n\n    cout << \"Resultant matrix:\\n\";\n\n    display(C, r1, c2);\n\n    return 0;\n}\n\n

Sample Output

\nEnter rows and columns for first matrix: 2 3\nEnter rows and columns for second matrix: 3 2\nEnter elements of first matrix:\n1 2 3\n4 5 6\n\nEnter elements of second matrix:\n7 8\n9 10\n11 12\n\nResultant matrix:\n58 64\n139 154\n

Complexity Analysis

Time Complexity: O(n³)
Space Complexity: O(n²)

Technique 2: Strassen's Algorithm

Algorithm Overview

Strassen's algorithm reduces the time complexity to O(n^log₂7) ≈ O(n²-⁸¹) by:\n1. Dividing matrices into submatrices\n2. Using 7 recursive multiplications instead of 8\n3. Combining results with additions

Implementation (4×4 Matrices)

\n#include <iostream>\nusing namespace std;\n\nvoid inputMatrix(double mat[4][4]) {\n    for(int i = 0; i < 4; i++) {\n        for(int j = 0; j < 4; j++) {\n            cin >> mat[i][j];\n        }\n    }\n}\n\nvoid strassenMultiply(double A[4][4], double B[4][4]) {\n    // Dividing into 2x2 submatrices\n\n    double A11 = (A[0][0] + A[1][1]) * (B[0][0] + B[1][1]);\n    double A12 = (A[0][1] + A[1][1]) * B[1][0];\n    double A21 = A[1][0] * (B[0][1] - B[1][1]);\n    double A22 = A[1][1] * (B[1][0] - B[0][0]);\n    double B11 = (A[0][0] + A[0][1]) * B[1][1];\n    double B21 = (A[1][0] - A[0][0]) * (B[0][0] + B[0][1]);\n    double B22 = (A[0][1] - A[1][1]) * (B[1][0] + B[1][1]);\n\n    // Calculating result submatrices\n    double C11 = A11 + A22 - B11 + B22;\n    double C12 = A21 + B11;\n    double C21 = A12 + A22;\n    double C22 = A11 + A21 - B11 - B21;\n\n    // Output result\n    cout << \"Result Matrix:\\n\";\n    cout << C11 << \" \" << C12 << \"\\n\";\n    cout << C21 << \" \" << C22 << \"\\n\";\n}\n\nint main() {\n    double A[4][4], B[4][4];\n    cout << \"Enter matrix A (4x4):\\n\";\n    inputMatrix(A);\n    cout << \"Enter matrix B (4x4):\\n\";\n    inputMatrix(B);\n    strassenMultiply(A, B);\n    return 0;\n}\n

Sample Output

Enter matrix A (4x4):\n1 2 3 4\n5 6 7 8\n9 10 11 12\n13 14 15 16\n\nEnter matrix B (4x4):\n16 15 14 13\n12 11 10 9\n8 7 6 5\n4 3 2 1\n\nResult Matrix:\n386 444\n962 1108\n

Comparison

Naive Matrix Multiplication

Time Complexity: O(n³)\nSpace Complexity: O(n²)

Best For: Small matrices

Strassen’s Algorithm

Time Complexity: O(n^2.81)\nSpace Complexity: O(n²)

Best For: Large matrices

Conclusion

The naive method is simpler but less efficient for large matrices. Strassen's algorithm provides better asymptotic performance but has higher constant factors, making it more suitable for larger matrices. The choice depends on your specific requirements and matrix sizes.

For most practical applications with small matrices (n < 100), the naive implementation is often preferred due to its simplicity. For larger matrices or performance-critical applications, Strassen's algorithm or more advanced methods like Coppersmith-Winograd may be preferable.

\n","title":"Matrix multiplication in C++","authorDetails":{"name":"Juhi Kamdar","slug":"juhi-kamdar"},"seo":{"title":"Matrix multiplication in C++ | Strassen's Algorithm"},"description":"Learn to write a Program to Multiply two matrices in C++ programming language using Basic Matrix multiplication and Strassen's Algorithm.","slug":"cpp/examples/multiply-two-matrices-in-cpp/","articleId":"636a83457bb1ce5072622c16","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null},"lastUpdated":"2025-09-02T05:49:52.796Z"}