Strassenâs Matrix Multiplication
”;
Strassen”s Matrix Multiplication is the divide and conquer approach to solve the matrix multiplication problems. The usual matrix multiplication method multiplies each row with each column to achieve the product matrix. The time complexity taken by this approach is O(n3), since it takes two loops to multiply. Strassenâs method was introduced to reduce the time complexity from O(n3) to O(nlog 7).
Naive Method
First, we will discuss Naive method and its complexity. Here, we are calculating Z=ð¿X à Y. Using Naive method, two matrices (X and Y) can be multiplied if the order of these matrices are p à q and q à r and the resultant matrix will be of order p à r. The following pseudocode describes the Naive multiplication −
Algorithm: Matrix-Multiplication (X, Y, Z) for i = 1 to p do for j = 1 to r do Z[i,j] := 0 for k = 1 to q do Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]
Complexity
Here, we assume that integer operations take O(1) time. There are three for loops in this algorithm and one is nested in other. Hence, the algorithm takes O(n3) time to execute.
Strassenâs Matrix Multiplication Algorithm
In this context, using Strassenâs Matrix multiplication algorithm, the time consumption can be improved a little bit.
Strassenâs Matrix multiplication can be performed only on square matrices where n is a power of 2. Order of both of the matrices are n × n.
Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below −
$Z = begin{bmatrix}I & J \K & L end{bmatrix}$ $X = begin{bmatrix}A & B \C & D end{bmatrix}$ and $Y = begin{bmatrix}E & F \G & H end{bmatrix}$
Using Strassenâs Algorithm compute the following −
$$M_{1} : colon= (A+C) times (E+F)$$
$$M_{2} : colon= (B+D) times (G+H)$$
$$M_{3} : colon= (A-D) times (E+H)$$
$$M_{4} : colon= A times (F-H)$$
$$M_{5} : colon= (C+D) times (E)$$
$$M_{6} : colon= (A+B) times (H)$$
$$M_{7} : colon= D times (G-E)$$
Then,
$$I : colon= M_{2} + M_{3} – M_{6} – M_{7}$$
$$J : colon= M_{4} + M_{6}$$
$$K : colon= M_{5} + M_{7}$$
$$L : colon= M_{1} – M_{3} – M_{4} – M_{5}$$
Analysis
$$T(n)=begin{cases}c & if:n= 1\7:x:T(frac{n}{2})+d:x:n^2 & otherwiseend{cases} :where: c: and :d:are: constants$$
Using this recurrence relation, we get $T(n) = O(n^{log7})$
Hence, the complexity of Strassenâs matrix multiplication algorithm is $O(n^{log7})$.
Example
Let us look at the implementation of Strassen”s Matrix Multiplication in various programming languages: C, C++, Java, Python.
#include<stdio.h> int main(){ int z[2][2]; int i, j; int m1, m2, m3, m4 , m5, m6, m7; int x[2][2] = { {12, 34}, {22, 10} }; int y[2][2] = { {3, 4}, {2, 1} }; printf("The first matrix is: "); for(i = 0; i < 2; i++) { printf("n"); for(j = 0; j < 2; j++) printf("%dt", x[i][j]); } printf("nThe second matrix is: "); for(i = 0; i < 2; i++) { printf("n"); for(j = 0; j < 2; j++) printf("%dt", y[i][j]); } m1= (x[0][0] + x[1][1]) * (y[0][0] + y[1][1]); m2= (x[1][0] + x[1][1]) * y[0][0]; m3= x[0][0] * (y[0][1] - y[1][1]); m4= x[1][1] * (y[1][0] - y[0][0]); m5= (x[0][0] + x[0][1]) * y[1][1]; m6= (x[1][0] - x[0][0]) * (y[0][0]+y[0][1]); m7= (x[0][1] - x[1][1]) * (y[1][0]+y[1][1]); z[0][0] = m1 + m4- m5 + m7; z[0][1] = m3 + m5; z[1][0] = m2 + m4; z[1][1] = m1 - m2 + m3 + m6; printf("nProduct achieved using Strassen''s algorithm: "); for(i = 0; i < 2 ; i++) { printf("n"); for(j = 0; j < 2; j++) printf("%dt", z[i][j]); } return 0; }
Output
The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassen''s algorithm: 104 82 86 98
#include<iostream> using namespace std; int main() { int z[2][2]; int i, j; int m1, m2, m3, m4 , m5, m6, m7; int x[2][2] = { {12, 34}, {22, 10} }; int y[2][2] = { {3, 4}, {2, 1} }; cout<<"The first matrix is: "; for(i = 0; i < 2; i++) { cout<<endl; for(j = 0; j < 2; j++) cout<<x[i][j]<<" "; } cout<<"nThe second matrix is: "; for(i = 0;i < 2; i++){ cout<<endl; for(j = 0;j < 2; j++) cout<<y[i][j]<<" "; } m1 = (x[0][0] + x[1][1]) * (y[0][0] + y[1][1]); m2 = (x[1][0] + x[1][1]) * y[0][0]; m3 = x[0][0] * (y[0][1] - y[1][1]); m4 = x[1][1] * (y[1][0] - y[0][0]); m5 = (x[0][0] + x[0][1]) * y[1][1]; m6 = (x[1][0] - x[0][0]) * (y[0][0]+y[0][1]); m7 = (x[0][1] - x[1][1]) * (y[1][0]+y[1][1]); z[0][0] = m1 + m4- m5 + m7; z[0][1] = m3 + m5; z[1][0] = m2 + m4; z[1][1] = m1 - m2 + m3 + m6; cout<<"nProduct achieved using Strassen''s algorithm: "; for(i = 0; i < 2 ; i++) { cout<<endl; for(j = 0; j < 2; j++) cout<<z[i][j]<<" "; } return 0; }
Output
The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassen''s algorithm: 104 82 86 98
public class Strassens { public static void main(String[] args) { int[][] x = {{12, 34}, {22, 10}}; int[][] y = {{3, 4}, {2, 1}}; int z[][] = new int[2][2]; int m1, m2, m3, m4 , m5, m6, m7; System.out.print("The first matrix is: "); for(int i = 0; i<2; i++) { System.out.println();//new line for(int j = 0; j<2; j++) { System.out.print(x[i][j] + "t"); } } System.out.print("nThe second matrix is: "); for(int i = 0; i<2; i++) { System.out.println();//new line for(int j = 0; j<2; j++) { System.out.print(y[i][j] + "t"); } } m1 = (x[0][0] + x[1][1]) * (y[0][0] + y[1][1]); m2 = (x[1][0] + x[1][1]) * y[0][0]; m3 = x[0][0] * (y[0][1] - y[1][1]); m4 = x[1][1] * (y[1][0] - y[0][0]); m5 = (x[0][0] + x[0][1]) * y[1][1]; m6 = (x[1][0] - x[0][0]) * (y[0][0]+y[0][1]); m7 = (x[0][1] - x[1][1]) * (y[1][0]+y[1][1]); z[0][0] = m1 + m4- m5 + m7; z[0][1] = m3 + m5; z[1][0] = m2 + m4; z[1][1] = m1 - m2 + m3 + m6; System.out.print("nProduct achieved using Strassen''s algorithm: "); for(int i = 0; i<2; i++) { System.out.println();//new line for(int j = 0; j<2; j++) { System.out.print(z[i][j] + "t"); } } } }
Output
The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassen''s algorithm: 104 82 86 98
import numpy as np x = np.array([[12, 34], [22, 10]]) y = np.array([[3, 4], [2, 1]]) z = np.zeros((2, 2)) m1, m2, m3, m4, m5, m6, m7 = 0, 0, 0, 0, 0, 0, 0 print("The first matrix is: ") for i in range(2): print() for j in range(2): print(x[i][j], end="t") print("nThe second matrix is: ") for i in range(2): print() for j in range(2): print(y[i][j], end="t") m1 = (x[0][0] + x[1][1]) * (y[0][0] + y[1][1]) m2 = (x[1][0] + x[1][1]) * y[0][0] m3 = x[0][0] * (y[0][1] - y[1][1]) m4 = x[1][1] * (y[1][0] - y[0][0]) m5 = (x[0][0] + x[0][1]) * y[1][1] m6 = (x[1][0] - x[0][0]) * (y[0][0] + y[0][1]) m7 = (x[0][1] - x[1][1]) * (y[1][0] + y[1][1]) z[0][0] = m1 + m4 - m5 + m7 z[0][1] = m3 + m5 z[1][0] = m2 + m4 z[1][1] = m1 - m2 + m3 + m6 print("nProduct achieved using Strassen''s algorithm: ") for i in range(2): print() for j in range(2): print(z[i][j], end="t")
Output
The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassen''s algorithm: 104.0 82.0 86.0 98.0
”;