Matrix multiplication in C++ | Strassen's Algorithm

Strassen’s Algorithm | Multiply two matrices in C++

Many times, during complex mathematical calculations, we require to multiply two matrices.

To implement the multiplication of two matrices, we can choose from the following techniques:

Basic Matrix multiplication
Strassen’s Algorithm

Technique 1: Basic Matrix multiplication

In this method, we use the pen paper trick itself. The algorithm for the same is stated below:

Logic:

Multiply rows of first matrix with columns of second matrix. We take each row r at a time, take its first element r1 , then, we multiply it with all the elements of column C c1,2,3,..n . We use this in an iterative manner and get the result.

Algorithm:

Input the no. of rows and columns of both the elements.
Check if the number of columns of first matrix is same as the rows of second matrix(condition for matrix multiplication)
Applying proper loops, use the formula Cij = ∑(Aik * Bik) where, i,j,k are positive integers and i,j,k<=n
Next, we display the final matrix.

Code:

#include <iostream>
using namespace std;

void multiply(int[5][5], int[5][5], int, int, int);
int display(int[5][5], int, int);

int main()
{

    int a[5][5], b[5][5], r1, c1, r2, c2;
    cout << "\n Enter rows for first matrix: ";
    cin >> r1;
    cout << "\n Enter columns for second matrix: ";
    cin >> c1;

    cout << "\n Enter rows for first matrix: ";
    cin >> r2;
    cout << "\n Enter columns for second matrix: ";
    cin >> c2;

    // To check if columns of first matrix are equal to rows of second matrix

    if (c1 != r2)
        return 0;

    // Storing elements of first matrix.

    cout << "\n Enter elements of first matrix \n";

    for (int i = 0; i < r1; i++) {
        for (int j = 0; j < c1; j++)
            cin >> a[i][j];
    }
    // Storing elements of second matrix.
    cout << "\n Enter elements of second matrix\n";

    for (int i = 0; i < r2; i++) {
        for (int j = 0; j < c2; j++)
            cin >> b[i][j];
    }
    display(a, r1, c1);
    display(b, r2, c2);
    //calling the function to multiply a and b. passing number of rows
    //and columns in both of them
    multiply(a, b, r1, c2, c1);
    return 0;
}

void multiply(int a[5][5], int b[5][5], int row, int col, int c1)
{
    int c[5][5];
    //input 0 for all values of c, in order to remove
    //the garbage values assigned earlier
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            c[i][j] = 0;
    }
    //we apply the same formula as above
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            for (int k = 0; k < c1; k++) //columns of first matrix || rows of second matrix
                c[i][j] += a[i][k] * b[k][j];
        }
    }
    //to display matrix
    cout << "\n Matrix c after matrix multiplication is:\n";
    display(c, row, col);
}

int display(int c[5][5], int row, int col)
{
    cout << "\n Matrix is:\n";
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            cout << c[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

Output:

Enter rows for first matrix: 2

Enter columns for second matrix: 3

Enter rows for first matrix: 3

Enter columns for second matrix: 2
Enter elements of first matrix

5 7 6
1 3 7

Enter elements of second matrix

6 2
8 9
3 6

Matrix is
5 7 6
1 3 7

Matrix is
6 2
8 9
3 6

Matrix c after matrix multiplication is:

Matrix is
104 109
51 71

Technique 2: Strassen’s Algorithm

In this method, we use the algorithm given by Strassen. The advantage of this algorithm is, that it uses less number of operations then the naive method.

It uses divide and conquer strategy, and thus, divides the square matrix of size n to n/2.

It reduces the 8 recursive calls to 7.

In this program, we use a 4×4 matrix.

Logic:

Divide the matrix A into four sub-matrices: A11, A12, A21, and A22.
Divide the matrix B into four sub-matrices: B11, B12, B21, and B22.
Calculate the values of p, q, r, s, t, u, and v using the Strassen's formulae.
Calculate the values of C11, C12, C21, and C22 using the values of p, q, r, s, t, u, and v.
Reassemble the matrix C from the sub-matrices C11, C12, C21, and C22.

Algorithm:

Input the no. rows and columns of both the elements
Check ifthe number of columns of first matrix is same as the rows of second matrix(condition for matrix multiplication).
Use the strassen’s formulae.
Feeding the values in the final matrix.
Next, we display the final matrix.

Code:

#include<iostream>
using namespace std;

double a[4][4];
double b[4][4];

void insert(double x[4][4])
{
	double val;
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			cin>>val;
			x[i][j]=val;
		}
	}
}

double cal11(double x[4][4])
{
	return (x[1][1] * x[1][2])+ (x[1][2] * x[2][1]);
}

double cal21(double x[4][4])
{
	return (x[3][1] * x[4][2])+ (x[3][2] * x[4][1]);
}

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

double cal22(double x[4][4])
{
	return (x[2][3] * x[1][4])+ (x[2][4] * x[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;
	//insert values in the matrix a
	cout<<"\n a: \n";
	insert(a);
	//insert values in the matrix a
	cout<<"\n b: \n";
	insert(b);
	
	//dividing single 4x4 matrix into four 2x2 matrices
	a11=cal11(a);
	a12=cal12(a);
	a21=cal21(a);
	a22=cal22(a);
	b11=cal11(b);
	b12=cal12(b);
	b21=cal21(b);
	b22=cal22(b);
   
	//assigning variables acc. to strassen's algo
	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);

    //outputting the final matrix
    cout<<"\n final matrix";
 	cout<<"\n"<<p+s-t+v<<" "<<r+t;
	cout<<"\n"<<q+s<<" "<<p+r-q+u;
    return 0;
}

Output:

a:

1 5 3 7
4 2 6 2
7 2 7 2
9 2 6 2

b:

5 4 2 6
4 6 6 1
5 4 2 6
7 1 4 7

Final matrix:

1440 2072
1680 1444