Strassen’s Matrix Multiplication

Introduction

Strassen's Matrix Multiplication is a divide-and-conquer technique used to efficiently solve matrix multiplication problems.

Multiplication of two matrices requires O(N^3) running time but we can reduce this time to O(N^2.81) by using an efficient approach which is known as Strassen Matrix multiplication.

In this blog, we will implement that efficient Strassen’s Matrix Multiplication approach in detail to solve our problem.

Recommended Topic, Array Implementation of Queue

What is Strassen’s Matrix Multiplication Algorithm

Here's how Strassen's Matrix Multiplication Algorithm works:

Divide: Take the two matrices you want to multiply, let's call them A and B. Split them into four smaller matrices, each about half the size of the original matrices.
Calculate: Use these smaller matrices to calculate seven special values, which we'll call P1, P2, P3, P4, P5, P6, and P7. You do this by doing some simple additions and subtractions of the smaller matrices.
Combine: Take these seven values and use them to compute the final result matrix, which we'll call C. You calculate the values of C using the values of P1 to P7.

This method may sound a bit more complicated, but it's faster for really big matrices because it reduces the number of multiplications you need to do, even though it involves more additions and subtractions. For smaller matrices, the regular multiplication is faster, but for huge matrices, Strassen's method can save a lot of time.

Problem Statement

Find the multiplication matrix of two square matrices A and B of size n x n each.

Example

Input

Output

Explanation

The result we get is after the multiplication of Matrix A and B.

Brute force Approach

The idea is to use 3 nested loops to calculate the value for each cell individually.

Pseudocode

Algorithm MULTIPLY_MATRIX(A, B, C)
for i <- 1 to n do
  for j <- 1 to n do
    C[i][j] <- 0
    for k <- 1 to n do
      C[i][j] <- C[i][j] + A[i][k]*B[k][j]
    end
  end
end

Implementation

C++
Java
Python
JS
C#

C++

#include <bits/stdc++.h>
using namespace std;

// print the matrix
void print(vector<vector<int> > matrix) {
	for(int i = 0; i < matrix.size(); i++){
        for(int j = 0; j < matrix[i].size(); j++){
            cout << matrix[i][j] << ' ';
        }
        cout << endl;
    }
}

void multiply(vector<vector<int>> &A, vector<vector<int>> &B, vector<vector<int>> &C) {
	int N = 4;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            C[i][j] = 0;
            for (int k = 0; k < N; k++) {
                C[i][j] += A[i][k]*B[k][j];
            }
        }
    }
}

int main() {

    // Input Matrix A
	vector<vector<int>> A = {{2, 2, 3, 1},{1, 4, 1, 2},{2, 3, 1, 1}, {1, 3, 1, 2}};
    
	// Input Matrix B
    vector<vector<int>> B = {{2, 1, 2, 1},{3, 1, 2, 1},{3, 2, 1, 1}, {1, 4, 3, 2}};

	vector<vector<int>> C(4, vector<int>(4));
    
	multiply(A, B, C);

    // Printing the result
	print(C);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.Arrays;

public class MatrixMultiplication {
    static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }

    static void multiply(int[][] A, int[][] B, int[][] C) {
        int N = 4;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                C[i][j] = 0;
                for (int k = 0; k < N; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] A = {{2, 2, 3, 1}, {1, 4, 1, 2}, {2, 3, 1, 1}, {1, 3, 1, 2}};
        int[][] B = {{2, 1, 2, 1}, {3, 1, 2, 1}, {3, 2, 1, 1}, {1, 4, 3, 2}};
        int[][] C = new int[4][4];

        multiply(A, B, C);
        printMatrix(C);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def print_matrix(matrix):
    for row in matrix:
        print(" ".join(map(str, row)))

def multiply(A, B, C):
    N = 4
    for i in range(N):
        for j in range(N):
            C[i][j] = sum(A[i][k] * B[k][j] for k in range(N))

A = [[2, 2, 3, 1], [1, 4, 1, 2], [2, 3, 1, 1], [1, 3, 1, 2]]
B = [[2, 1, 2, 1], [3, 1, 2, 1], [3, 2, 1, 1], [1, 4, 3, 2]]
C = [[0] * 4 for _ in range(4)]

multiply(A, B, C)
print_matrix(C)

You can also try this code with Online Python Compiler

Run Code

JS

function printMatrix(matrix) {
    matrix.forEach(row => console.log(row.join(" ")));
}

function multiply(A, B, C) {
    let N = 4;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            C[i][j] = 0;
            for (let k = 0; k < N; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

let A = [[2, 2, 3, 1], [1, 4, 1, 2], [2, 3, 1, 1], [1, 3, 1, 2]];
let B = [[2, 1, 2, 1], [3, 1, 2, 1], [3, 2, 1, 1], [1, 4, 3, 2]];
let C = Array.from({ length: 4 }, () => Array(4).fill(0));

multiply(A, B, C);
printMatrix(C);

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;

class MatrixMultiplication {
    static void PrintMatrix(int[,] matrix) {
        int N = matrix.GetLength(0);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Console.Write(matrix[i, j] + " ");
            }
            Console.WriteLine();
        }
    }

    static void Multiply(int[,] A, int[,] B, int[,] C) {
        int N = 4;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                C[i, j] = 0;
                for (int k = 0; k < N; k++) {
                    C[i, j] += A[i, k] * B[k, j];
                }
            }
        }
    }

    static void Main() {
        int[,] A = { { 2, 2, 3, 1 }, { 1, 4, 1, 2 }, { 2, 3, 1, 1 }, { 1, 3, 1, 2 } };
        int[,] B = { { 2, 1, 2, 1 }, { 3, 1, 2, 1 }, { 3, 2, 1, 1 }, { 1, 4, 3, 2 } };
        int[,] C = new int[4, 4];

        Multiply(A, B, C);
        PrintMatrix(C);
    }
}

Output

20 14 14 9 
19 15 17 10 
17 11 14 8 
16 14 15 9

Time Complexity

There are three for loops that enclose the inner statement. So, The Running time of the above algorithm is O(N^3).

Space Complexity

A new matrix is used to store the result of the multiplication. So, the space complexity is O(N^2).

Optimized Approach

We can implement Strassen’s Matrix Multiplication and the idea is to use the divide and conquer approach to divide the matrices into sub-matrices of size N/2 and then solve these sub-matrices using a formula given by Strassen's method

Pseudocode

// Algorithm to calculate multiplication of two matrices
// Here A and B are the input Matrices
// and C is the output Matrix and n represents the size
Algorithm STRASSEN_METHOD (A, B, C, int n)
if n == 1 then
  C = C + (A) * (B)
else
  STRASSEN_METHOD (A, B, C, n/4)
  STRASSEN_METHOD (A, B + (n/4), C + (n/4), n/4)
  STRASSEN_METHOD (A + 2 * (n/4), B, C + 2 * (n/4), n/4)
  STRASSEN_METHOD (A + 2 * (n/4), B + (n/4), C + 3 * (n/4), n/4)
  STRASSEN_METHOD (A + (n/4), B + 2 * (n/4), C, n/4)
  STRASSEN_METHOD (A + (n/4), B + 3 * (n/4), C + (n/4), n/4)
  STRASSEN_METHOD (A + 3 * (n/4), B + 2 * (n/4), C + 2 * (n/4), n/4)
  STRASSEN_METHOD (A + 3 * (n/4), B + 3 * (n/4), C + 3 * (n/4), n/4)
end

Implementation

C++
Java
Python
JS
C#

C++

// Strassen’s Matrix Multiplication
#include <bits/stdc++.h>
using namespace std;

// Size of two matrices
#define ROW_1 4
#define COL_1 4
#define ROW_2 4
#define COL_2 4

// print the matrix
void print(vector<vector<int> > matrix) {
	for(int i = 0; i < matrix.size(); i++){
        for(int j = 0; j < matrix[i].size(); j++){
            cout << matrix[i][j] << ' ';
        }
        cout << endl;
    }
}

// Add two matrices and return the result
vector<vector<int>> add(vector<vector<int> > A, vector<vector<int> > B, int split_index, int multiplier = 1) {
	for (auto i = 0; i < split_index; i++)
		for (auto j = 0; j < split_index; j++)
			A[i][j] = A[i][j] + (multiplier * B[i][j]);
	return A;
}

vector<vector<int> >
strassen_multiplication(vector<vector<int> > A, vector<vector<int> > B) {
	
	// calculating the size of matrix
	int col_1 = A[0].size();
	int row_1 = A.size();
	int col_2 = B[0].size();
	int row_2 = B.size();

	// checking if multiplication is possible or not 
	// between the input matrices
	if (col_1 != row_2) {
		cout << "The Two Matrices cannot be multiplied";
		return {};
	}

	// creating an empty matrix to store the result
	vector<int> result_row(col_2, 0);
	vector<vector<int> > result(row_1, result_row);

	// Base case 
	// if size of matrix is 1
	if (col_1 == 1)
		result[0][0]
			= A[0][0] * B[0][0];
	else {

		// split index
		int split_index = col_1 / 2;

		vector<int> row_vector(split_index, 0);

		// Splitting the matrices in sub matrices
		vector<vector<int> > a00(split_index, row_vector);
		vector<vector<int> > a01(split_index, row_vector);
		vector<vector<int> > a10(split_index, row_vector);
		vector<vector<int> > a11(split_index, row_vector);
		vector<vector<int> > b00(split_index, row_vector);
		vector<vector<int> > b01(split_index, row_vector);
		vector<vector<int> > b10(split_index, row_vector);
		vector<vector<int> > b11(split_index, row_vector);

		// calculating and storing the result
		// inside our quadrants
		for (auto i = 0; i < split_index; i++)
			for (auto j = 0; j < split_index; j++) {
				a00[i][j] = A[i][j];
				a01[i][j] = A[i][j + split_index];
				a10[i][j] = A[split_index + i][j];
				a11[i][j] = A[i + split_index]
									[j + split_index];
				b00[i][j] = B[i][j];
				b01[i][j] = B[i][j + split_index];
				b10[i][j] = B[split_index + i][j];
				b11[i][j] = B[i + split_index]
									[j + split_index];
			}

		// Calculating the multiplication using the formula
		// given by strassent algorithm
		vector<vector<int>> p1(
			strassen_multiplication(a00, add(b01, b11, split_index, -1))
		);
		vector<vector<int>> p2(
			strassen_multiplication(add(a00, a01, split_index), b11)
		);
		vector<vector<int>> p3(
			strassen_multiplication(add(a10, a11, split_index), b00)
		);
		vector<vector<int>> p4(
			strassen_multiplication(a11, add(b10, b00, split_index, -1))
		);
		vector<vector<int>> p5(
			strassen_multiplication(add(a00, a11, split_index),add(b00, b11, split_index))
		);
		vector<vector<int>> p6(
			strassen_multiplication(add(a01, a11, split_index, -1),add(b10, b11, split_index))
		);
		vector<vector<int>> p7(
			strassen_multiplication(
				add(a00, a10, split_index, -1),
				add(b00, b01, split_index)
			)
		);

		// calculating the result
		vector<vector<int> > result_00(
			add(add(add(p5, p4, split_index), p6, split_index), p2, split_index, -1)
		);
		vector<vector<int> > result_01(
			add(p1, p2, split_index)
		);
		vector<vector<int> > result_10(	
			add(p3, p4, split_index)
		);
		vector<vector<int> > result_11(
			add(add(add(p5, p1, split_index), p3, split_index, -1), p7, split_index, -1)
		);

		// calulating and storing the result
		// inside matrix
		for (auto i = 0; i < split_index; i++){
			for (auto j = 0; j < split_index; j++) {
				result[i][j] = result_00[i][j];
				result[i][j + split_index] = result_01[i][j];
				result[split_index + i][j] = result_10[i][j];
				result[i + split_index][j + split_index] = result_11[i][j];
			}
		}

		// clearing all the arrays
		a00.clear();
		a01.clear();
		a10.clear();
		a11.clear();
		b00.clear();
		b01.clear();
		b10.clear();
		b11.clear();
		p1.clear();
		p2.clear();
		p3.clear();
		p4.clear();
		p5.clear();
		p6.clear();
		p7.clear();
		result_00.clear();
		result_01.clear();
		result_10.clear();
		result_11.clear();
	}
	return result;
}

int main() {

    // Input Matrix A
	vector<vector<int>> A = {{2, 2, 3, 1},{1, 4, 1, 2},{2, 3, 1, 1}, {1, 3, 1, 2}};
    
	// Input Matrix B
    vector<vector<int>> B = {{2, 1, 2, 1},{3, 1, 2, 1},{3, 2, 1, 1}, {1, 4, 3, 2}};

    // Getting the result
	vector<vector<int> > result(strassen_multiplication(A, B));

    // Printing the result
	print(result);
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.Arrays;

public class StrassenMatrixMultiplication {
    static int[][] add(int[][] A, int[][] B, int splitIndex, int multiplier) {
        int[][] result = new int[splitIndex][splitIndex];
        for (int i = 0; i < splitIndex; i++) {
            for (int j = 0; j < splitIndex; j++) {
                result[i][j] = A[i][j] + multiplier * B[i][j];
            }
        }
        return result;
    }

    static int[][] strassenMultiplication(int[][] A, int[][] B) {
        int N = A.length;
        int[][] C = new int[N][N];

        if (N == 1) {
            C[0][0] = A[0][0] * B[0][0];
            return C;
        }

        int splitIndex = N / 2;
        int[][] a00 = new int[splitIndex][splitIndex];
        int[][] a01 = new int[splitIndex][splitIndex];
        int[][] a10 = new int[splitIndex][splitIndex];
        int[][] a11 = new int[splitIndex][splitIndex];
        int[][] b00 = new int[splitIndex][splitIndex];
        int[][] b01 = new int[splitIndex][splitIndex];
        int[][] b10 = new int[splitIndex][splitIndex];
        int[][] b11 = new int[splitIndex][splitIndex];

        for (int i = 0; i < splitIndex; i++) {
            for (int j = 0; j < splitIndex; j++) {
                a00[i][j] = A[i][j];
                a01[i][j] = A[i][j + splitIndex];
                a10[i][j] = A[i + splitIndex][j];
                a11[i][j] = A[i + splitIndex][j + splitIndex];
                b00[i][j] = B[i][j];
                b01[i][j] = B[i][j + splitIndex];
                b10[i][j] = B[i + splitIndex][j];
                b11[i][j] = B[i + splitIndex][j + splitIndex];
            }
        }

        int[][] p1 = strassenMultiplication(a00, add(b01, b11, splitIndex, -1));
        int[][] p2 = strassenMultiplication(add(a00, a01, splitIndex, 1), b11);
        int[][] p3 = strassenMultiplication(add(a10, a11, splitIndex, 1), b00);
        int[][] p4 = strassenMultiplication(a11, add(b10, b00, splitIndex, -1));
        int[][] p5 = strassenMultiplication(add(a00, a11, splitIndex, 1), add(b00, b11, splitIndex, 1));
        int[][] p6 = strassenMultiplication(add(a01, a11, splitIndex, -1), add(b10, b11, splitIndex, 1));
        int[][] p7 = strassenMultiplication(add(a00, a10, splitIndex, -1), add(b00, b01, splitIndex, 1));

        int[][] c00 = add(add(add(p5, p4, splitIndex, 1), p6, splitIndex, 1), p2, splitIndex, -1);
        int[][] c01 = add(p1, p2, splitIndex, 1);
        int[][] c10 = add(p3, p4, splitIndex, 1);
        int[][] c11 = add(add(add(p5, p1, splitIndex, 1), p3, splitIndex, -1), p7, splitIndex, -1);

        for (int i = 0; i < splitIndex; i++) {
            for (int j = 0; j < splitIndex; j++) {
                C[i][j] = c00[i][j];
                C[i][j + splitIndex] = c01[i][j];
                C[i + splitIndex][j] = c10[i][j];
                C[i + splitIndex][j + splitIndex] = c11[i][j];
            }
        }

        return C;
    }

    static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }

    public static void main(String[] args) {
        int[][] A = {{2, 2, 3, 1}, {1, 4, 1, 2}, {2, 3, 1, 1}, {1, 3, 1, 2}};
        int[][] B = {{2, 1, 2, 1}, {3, 1, 2, 1}, {3, 2, 1, 1}, {1, 4, 3, 2}};

        int[][] result = strassenMultiplication(A, B);
        printMatrix(result);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def add(A, B, split_index, multiplier=1):
    return [[A[i][j] + multiplier * B[i][j] for j in range(split_index)] for i in range(split_index)]

def strassen_multiplication(A, B):
    N = len(A)
    if N == 1:
        return [[A[0][0] * B[0][0]]]

    split_index = N // 2
    a00 = [[A[i][j] for j in range(split_index)] for i in range(split_index)]
    a01 = [[A[i][j] for j in range(split_index, N)] for i in range(split_index)]
    a10 = [[A[i][j] for j in range(split_index)] for i in range(split_index, N)]
    a11 = [[A[i][j] for j in range(split_index, N)] for i in range(split_index, N)]
    
    b00 = [[B[i][j] for j in range(split_index)] for i in range(split_index)]
    b01 = [[B[i][j] for j in range(split_index, N)] for i in range(split_index)]
    b10 = [[B[i][j] for j in range(split_index)] for i in range(split_index, N)]
    b11 = [[B[i][j] for j in range(split_index, N)] for i in range(split_index, N)]

    p1 = strassen_multiplication(a00, add(b01, b11, split_index, -1))
    p2 = strassen_multiplication(add(a00, a01, split_index), b11)
    p3 = strassen_multiplication(add(a10, a11, split_index), b00)
    p4 = strassen_multiplication(a11, add(b10, b00, split_index, -1))
    p5 = strassen_multiplication(add(a00, a11, split_index), add(b00, b11, split_index))
    p6 = strassen_multiplication(add(a01, a11, split_index, -1), add(b10, b11, split_index))
    p7 = strassen_multiplication(add(a00, a10, split_index, -1), add(b00, b01, split_index))

    c00 = add(add(add(p5, p4, split_index), p6, split_index), p2, split_index, -1)
    c01 = add(p1, p2, split_index)
    c10 = add(p3, p4, split_index)
    c11 = add(add(add(p5, p1, split_index), p3, split_index, -1), p7, split_index, -1)

    result = [[0] * N for _ in range(N)]
    for i in range(split_index):
        for j in range(split_index):
            result[i][j] = c00[i][j]
            result[i][j + split_index] = c01[i][j]
            result[i + split_index][j] = c10[i][j]
            result[i + split_index][j + split_index] = c11[i][j]

    return result

def print_matrix(matrix):
    for row in matrix:
        print(" ".join(map(str, row)))

A = [[2, 2, 3, 1], [1, 4, 1, 2], [2, 3, 1, 1], [1, 3, 1, 2]]
B = [[2, 1, 2, 1], [3, 1, 2, 1], [3, 2, 1, 1], [1, 4, 3, 2]]

result = strassen_multiplication(A, B)
print_matrix(result)

You can also try this code with Online Python Compiler

Run Code

JS

function add(A, B, splitIndex, multiplier = 1) {
    let result = Array.from({ length: splitIndex }, () => Array(splitIndex).fill(0));
    for (let i = 0; i < splitIndex; i++) {
        for (let j = 0; j < splitIndex; j++) {
            result[i][j] = A[i][j] + multiplier * B[i][j];
        }
    }
    return result;
}

function strassenMultiplication(A, B) {
    let N = A.length;
    if (N === 1) {
        return [[A[0][0] * B[0][0]]];
    }

    let splitIndex = N / 2;
    let a00 = [], a01 = [], a10 = [], a11 = [];
    let b00 = [], b01 = [], b10 = [], b11 = [];

    for (let i = 0; i < splitIndex; i++) {
        a00.push(A[i].slice(0, splitIndex));
        a01.push(A[i].slice(splitIndex));
        a10.push(A[i + splitIndex].slice(0, splitIndex));
        a11.push(A[i + splitIndex].slice(splitIndex));

        b00.push(B[i].slice(0, splitIndex));
        b01.push(B[i].slice(splitIndex));
        b10.push(B[i + splitIndex].slice(0, splitIndex));
        b11.push(B[i + splitIndex].slice(splitIndex));
    }

    let p1 = strassenMultiplication(a00, add(b01, b11, splitIndex, -1));
    let p2 = strassenMultiplication(add(a00, a01, splitIndex), b11);
    let p3 = strassenMultiplication(add(a10, a11, splitIndex), b00);
    let p4 = strassenMultiplication(a11, add(b10, b00, splitIndex, -1));
    let p5 = strassenMultiplication(add(a00, a11, splitIndex), add(b00, b11, splitIndex));
    let p6 = strassenMultiplication(add(a01, a11, splitIndex, -1), add(b10, b11, splitIndex));
    let p7 = strassenMultiplication(add(a00, a10, splitIndex, -1), add(b00, b01, splitIndex));

    let c00 = add(add(add(p5, p4, splitIndex), p6, splitIndex), p2, splitIndex, -1);
    let c01 = add(p1, p2, splitIndex);
    let c10 = add(p3, p4, splitIndex);
    let c11 = add(add(add(p5, p1, splitIndex), p3, splitIndex, -1), p7, splitIndex, -1);

    let result = Array.from({ length: N }, () => Array(N).fill(0));
    for (let i = 0; i < splitIndex; i++) {
        for (let j = 0; j < splitIndex; j++) {
            result[i][j] = c00[i][j];
            result[i][j + splitIndex] = c01[i][j];
            result[i + splitIndex][j] = c10[i][j];
            result[i + splitIndex][j + splitIndex] = c11[i][j];
        }
    }
    return result;
}

function printMatrix(matrix) {
    matrix.forEach(row => console.log(row.join(" ")));
}

let A = [[2, 2, 3, 1], [1, 4, 1, 2], [2, 3, 1, 1], [1, 3, 1, 2]];
let B = [[2, 1, 2, 1], [3, 1, 2, 1], [3, 2, 1, 1], [1, 4, 3, 2]];

let result = strassenMultiplication(A, B);
printMatrix(result);

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;

class StrassenMultiplication {
    static int[,] Add(int[,] A, int[,] B, int splitIndex, int multiplier = 1) {
        int[,] result = new int[splitIndex, splitIndex];
        for (int i = 0; i < splitIndex; i++) {
            for (int j = 0; j < splitIndex; j++) {
                result[i, j] = A[i, j] + multiplier * B[i, j];
            }
        }
        return result;
    }

    static int[,] StrassenMultiply(int[,] A, int[,] B) {
        int N = A.GetLength(0);
        int[,] C = new int[N, N];

        if (N == 1) {
            C[0, 0] = A[0, 0] * B[0, 0];
            return C;
        }

        int splitIndex = N / 2;
        int[,] a00 = new int[splitIndex, splitIndex];
        int[,] a01 = new int[splitIndex, splitIndex];
        int[,] a10 = new int[splitIndex, splitIndex];
        int[,] a11 = new int[splitIndex, splitIndex];
        int[,] b00 = new int[splitIndex, splitIndex];
        int[,] b01 = new int[splitIndex, splitIndex];
        int[,] b10 = new int[splitIndex, splitIndex];
        int[,] b11 = new int[splitIndex, splitIndex];

        for (int i = 0; i < splitIndex; i++) {
            for (int j = 0; j < splitIndex; j++) {
                a00[i, j] = A[i, j];
                a01[i, j] = A[i, j + splitIndex];
                a10[i, j] = A[i + splitIndex, j];
                a11[i, j] = A[i + splitIndex, j + splitIndex];
                b00[i, j] = B[i, j];
                b01[i, j] = B[i, j + splitIndex];
                b10[i, j] = B[i + splitIndex, j];
                b11[i, j] = B[i + splitIndex, j + splitIndex];
            }
        }

        int[,] p1 = StrassenMultiply(a00, Add(b01, b11, splitIndex, -1));
        int[,] p2 = StrassenMultiply(Add(a00, a01, splitIndex), b11);
        int[,] p3 = StrassenMultiply(Add(a10, a11, splitIndex), b00);
        int[,] p4 = StrassenMultiply(a11, Add(b10, b00, splitIndex, -1));
        int[,] p5 = StrassenMultiply(Add(a00, a11, splitIndex), Add(b00, b11, splitIndex));
        int[,] p6 = StrassenMultiply(Add(a01, a11, splitIndex, -1), Add(b10, b11, splitIndex));
        int[,] p7 = StrassenMultiply(Add(a00, a10, splitIndex, -1), Add(b00, b01, splitIndex));

        int[,] c00 = Add(Add(Add(p5, p4, splitIndex), p6, splitIndex), p2, splitIndex, -1);
        int[,] c01 = Add(p1, p2, splitIndex);
        int[,] c10 = Add(p3, p4, splitIndex);
        int[,] c11 = Add(Add(Add(p5, p1, splitIndex), p3, splitIndex, -1), p7, splitIndex, -1);

        for (int i = 0; i < splitIndex; i++) {
            for (int j = 0; j < splitIndex; j++) {
                C[i, j] = c00[i, j];
                C[i, j + splitIndex] = c01[i, j];
                C[i + splitIndex, j] = c10[i, j];
                C[i + splitIndex, j + splitIndex] = c11[i, j];
            }
        }
        return C;
    }

    static void PrintMatrix(int[,] matrix) {
        int size = matrix.GetLength(0);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                Console.Write(matrix[i, j] + " ");
            }
            Console.WriteLine();
        }
    }

    static void Main() {
        int[,] A = {{2, 2, 3, 1}, {1, 4, 1, 2}, {2, 3, 1, 1}, {1, 3, 1, 2}};
        int[,] B = {{2, 1, 2, 1}, {3, 1, 2, 1}, {3, 2, 1, 1}, {1, 4, 3, 2}};

        int[,] result = StrassenMultiply(A, B);
        PrintMatrix(result);
    }
}

Output

20 14 14 9 
19 15 17 10 
17 11 14 8 
16 14 15 9

Time Complexity

Using strassen's matrix multiplication method we can split the problem of size n into 7 subproblems of size (n - 2).
The recurrence equation for strassen's matrix multiplication method is T(n) = 7.T(n/2). After solving the recurrence relation we get O(n^2.81) as the running time of Strassen’s matrix multiplication algorithm.

Space Complexity

A new matrix is used to store the result of the multiplication. So, the space complexity of Strassen’s matrix multiplication method is O(N^2).

Frequently Asked Questions

What is Strassen’s Matrix Multiplication?

The Strassen algorithm is a recursive method for matrix multiplication in which each recursive step divides the matrix into four submatrices of dimensions n/2 x n/2.

Which technique is used in Strassen's matrix?

Strassen's matrix is an efficient technique that is used in matrix multiplication. This technique used the divide and conquer approach which reduces the number of calculations in matrix multiplications. The larger matrices get decomposed into smaller matrices which is an efficient approach.

Why Strassen's matrix multiplication is better than ordinary matrix multiplication?

Strassen's matrix multiplication is better than ordinary matrix multiplication because of its approach. The approach is divide and conquer which lesser the number of calculations which ultimately saves time and also exhibits better cache memory than any ordinary matrix multiplication.

What are the 4 methods of matrix?

The popular 4 methods of matrix multiplication are standard matrix multiplication which is the naive method, the second is matrix chain multiplication, the next is Strassen's matrix multiplication and the fourth is block matrix multiplication.

Conclusion

In this article, we have extensively discussed a coding problem where we have to multiply two matrices and we used two different approaches to solve the problem, one is the brute force approach and the other is Strassen’s Matrix Multiplication method. We hope that this blog has helped you enhance your knowledge about the above question and if you would like to learn more. Check out more of our blogs related to coding questions First non-repeating character in a stream, How to efficiently implement k Queues in a single array, Sorting of Queue, and many more on our Website.

Recommended Problems: