Strassen’s Algorithm for Matrix multiplication is a recursive algorithm for multiplying **n x n matrices** in O(n^{log(7)}) ie O(n^{2.81}) time. It outperforms the naive O(n^3) matrix multiplication algorithm.

#### Naive Matrix-Multiplication (A, B) Pseudocode

1. n = Length[A] 2. C = n x n matrix 3. for i = 1 to n 4. do for j = 1 to n 5. do C_{ij}= 0 6. for k = 1 to n 7. do C_{ij}= C_{ij}+ a_{ik}* b_{kj}8. return C

#### Code Implementation

```
//
// main.cpp
// Matrix multiplication
//
// Created by Himanshu on 17/09/21.
//
#include <iostream>
using namespace std;
const int N = 2, M = 2;
void multiplyMatrices (int A[N][M], int B[N][M]) {
int C[N][M];
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
C[i][j] = 0;
for (int k=0; k<N; k++) {
C[i][j] += A[i][k]*B[k][j];
}
}
}
cout<<"Multiplication of Matrices A and B:"<<endl;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
cout<<C[i][j]<<" ";
}
cout<<endl;
}
}
int main() {
int A[N][M] = {{1, 2}, {3, 4}};
int B[N][M] = {{5, 6}, {7, 8}};
multiplyMatrices(A, B);
}
```

**Output: **

Multiplication of Matrices A and B: 19 22 43 50

Here’s a working example:

Matrix Multiplication

#### Strassen’s Algorithm for Matrix multiplication

Strassen’s algorithm is based on a familiar design technique – Divide & Conquer. Now if we wish to compute the product C = AB, where each of A, B and C are n x n (2 x 2) matrices. Let, we divide each of A, B and C into four n/2 x n/2 matrices, and rewrite C = A x B as follows:

**This equation corresponds to the following 4 equations:**

r = ae + bg s = af + bh t = ce + dg u = cf + dh

Each of these 4 equations specifies multiplication of n/2 x n/2 matrices and addition of their n/2 x n/2 products. Using divide-and-conquer strategy, we derive the following recurrence relation:

T(n) = 8T(n/2) + O(n^2)Here we do 8 multiplications for matrices of size N/2 x N/2 or (1 x 1) and 4 (N^2) additions. Hence the above recurrence relation. The above recurrence has T(n) = O(n^3) solution.

Now, Strassen discovered a different recursive approach that requires only 7 recursive multiplication of (N/2) x (N/2) matrices and O(n^2) scalar additions and subtractions, resulting in:

T(n) = 7T(n/2) + O(n^{2})

T(n) = O(n^{lg7})

T(n) = O(n^{2.81})

which is a great improvement than naive O(n^3) for a larger N.

###### Strassen’s Matrices

P_{1}= A_{1}B_{1}= (a.(f - h)) = af - ah P_{2}= A_{2}B_{2}= ((a + b).h) = ah + bh P_{3}= A_{3}B_{3}= ((c + d).e) = ce + de P_{4}= A_{4}B_{4}= (d.(g - e)) = dg - de P_{5}= A_{5}B_{5}= ((a + d).(e + h)) = ae + ah + de + dh P_{6}= A_{6}B_{6}= ((b - d).(g + h)) = bg + bh - dg - dh P_{7}= A_{7}B_{7}= ((a - c).(e + f)) = ae + af - ce - cf

Now, these 7 matrices (P_{1}, P_{2}, P_{3}, P_{4}, P_{5}, P_{6}, P_{7}) can be used to calculate – **r, s, t, u** (C = A x B) in the following manner:

r = P_{5}+ P_{4}- P_{2}+ P_{6}= ae + bg s = P_{1}+ P_{2}= af + bh t = P_{3}+ P_{4}= ce + dg u = P_{5}+ P_{1}- P_{3}- P_{7}= cf + dh

Thus, we calculated C = A x B using only 7 matrix multiplication.

However, Strassen’s algorithm is often not the method of choice for practical applications, for 4 reasons:

- The constant factor hidden in the running time of Strassen’s algorithm is larger than the constant factor in the naive O(n^3) method.
- When the matrices are sparse, specially tailored methods for sparse matrices are fast.
- Strassen’s algorithm is not quite as numerically stable as naive method.
- The sub-matrices formed at the levels of recursion consume space.

**Reference:**

Introduction to Algorithms – (CLRS book)

## One thought on “Strassen’s Algorithm for Matrix multiplication”