STRASSEN’S MATRIX MULTIPLICATION

We have used many multiplication processes like matrix multiplication. But in matrix multiplication the 2*2 matrix multiplication is easy but for 3*3 matrix multiplication is difficult. We use divide and conquer approach to easy multiply. Like I will explain it with a simple example:

Example 1:

Step 1: First this 3 * 3 matrix should change to 4 * 4 matrix adding remaining spaces with zeroes.

A = [[1 1 1 0][1 1 1 0][1 1 1 0][0 0 0 0]]

B = [[1 1 1 0][1 1 1 0][1 1 1 0][0 0 0 0]]

Step 2: Now we will divide A and B matrix into 4 (2*2) matrices

We will create a C matrix:

Step 3: Here c11 = A11.B11 + A12.B21

c12 = A11.B12 + A12.B22

c21 = A21.B11 + A22.B21

c22 = A21.B12 + A22.B22

Step 4: Here “+” means Matrix addition

Step 5: Now, we will Combine c11,c12,c21,c22 to C and we will get

Complexity Analysis:

Let T(n) be the time complexity of matrix multiplication using divide and conquer of given matrix n*n , then —

T(n) = 8T(n/2) + n² = theta(n³)..

As this matrix multiplication takes more time to solve, We are taking Strassen’s Matrix Multiplication…

Strassen’s Matrix Multiplication

Strassen discovered a way to compute the Cij’s using seven multiplication operations and 18 addition or subtraction operations.

We will use 7 easy formulas and we will combine these formulas as c11,c12,c21,c22.

First we will take a matrix

We will use seven constants here as P,Q,R,S,T,U,V

P = (A11 + A22) (B11 + B12)

Q = (A21 + A22)(B11)

R = (A11) (B12 − B22)

S = (A22) (B21 − B11)

T = (A11 + A12) (B22)

U = (A21−A11) (B11 + B12)

V = (A12 −A22) (B21 + B22)

c11 = P + S−T + V

c12 = R + T

c21 = Q + S

c22 = P + R − Q + U

By using these we will create a C matrix that is the matrix multiplication matrix.

Complexity :

T(n) = 7T(n/2) + 18n²

T(n) = 7T(n/2) + theta(n²)

Complexity Analysis:

T(n) = { 7T(n/2) + theta (n²) — — n>2

1 — — — - n ≤ 2}

complexity= theta(n^log7 base 2= n^2.81)

Algorithm:

1. Input the rows and columns of both the elements
2. Check if the number of columns of first matrix is same as the rows of second matrix(condition for matrix multiplication).
3. Use the Strassen’s formulae.
4. Keep values in the final matrix.
5. Next, display the final matrix.

Code:

#include<iostream>   
using namespace std;
double A[4][4];        #input the A and B matrices
double B[4][4];

void insert(double a[4][4])
{
	double val;
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			cin>>val;
			a[i][j]=val;
		}
	}
}
double cal11(double a[4][4])
{
	return (a[1][1] * a[1][2])+ (a[1][2] * a[2][1]);
}
double cal21(double a[4][4])
{
	return (a[3][1] * a[4][2])+ (a[3][2] * a[4][1]);
}

double cal12(double a[4][4])
{
	return (a[1][3] * a[2][4])+ (a[1][4] * a[2][3]);
}

double cal22(double a[4][4])
{
	return (a[2][3] * a[1][4])+ (a[2][4] * a[1][3]);
}

int main()
{
	double a11,a12,a22,a21,b11,b12,b21,b22,a[4][4],b[4][4];
	double p,q,r,s,t,u,v,c11,c12,c21,c22;
	cout<<"\n a: \n";
	insert(a);
	cout<<"\n b: \n";
	insert(b);
	
	a11=cal11(a);
	a12=cal12(a);
	a21=cal21(a);
	a22=cal22(a);
	b11=cal11(b);
	b12=cal12(b);
	b21=cal21(b);
	b22=cal22(b);
   
	p=(a11+a22)*(b11+b22);
	q=(a21+a22)*b11;
	r=a11*(b12-b22);
	s=a22*(b21-b11);
	t=(a11+a12)*b22;
	u=(a11-a21)*(b11+b12);
	v=(a12-a22)*(b21+b22);
cout<<"\n final matrix";
 	cout<<"\n"<<p+s-t+v<<" "<<r+t;
	cout<<"\n"<<q+s<<" "<<p+r-q+u;
    return 0;
}

Strassen’s matrix multiplication is easy multiplication technique than the standard normal matrix multiplication for large matrices.

I hope u all got to know about Strassen’s Matrix Multiplication.

Thank You