Is there any trick to find the products of two or three matrices of order 3×3 quickly?
Is there any trick to find the products of two or three matrices of order 3×3 quickly?
We have
Strassen’s Matrix Multiplication Algorithm 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 matriceswhere n is a power of 2. Order of both of the matrices are n × n.
Here Im giving Example on by 2 matrix
consider X, Y and Z matrices as represented below −
Z=[I J] X=[A B]and Y=[E F]
K L C D G H
To compute Z=X*Y
Using Strassen’s Algorithm compute the following −
M1:=(A+C)×(E+F) M2:=(B+D)×(G+H)
M3:=(A−D)×(E+H)
M4:=A×(F−H)
M5:=(C+D)×(E)
M6:=(A+B)×(H)
M7:=D×(G−E)
only using 7 multiplications
Then,
I:=M2+M3−M6−M7
J:=M4+M6
K:=M5+M7
L:=M1−M3−M4−M5
You may feel steps invlved in this algorithm to find result is larger in number than our conventional method. But we can observe that With this construction we have not reduced the number of multiplications. We need 8 multiplications to calculate the Zi,j matrices, when using standard matrix multiplication. But in stressens algorithm we need 7 multiplication to find product of 2 2by 2 matrix.So complexity reduced
As the order increases the complexity change will make that difference
We can also implement algorithms into programs using programming languages like C,CPP through this iterations can be done easily. So the result can be found quickly.
Strassen’s Matrix Multiplication Algorithm
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 matriceswhere n is a power of 2. Order of both of the matrices are n × n.
Here Im giving Example on by 2 matrix
consider X, Y and Z matrices as represented below −
Z=[I J] X=[A B]and Y=[E F]
K L C D G H
To compute Z=X*Y
Using Strassen’s Algorithm compute the following −
M1:=(A+C)×(E+F)M2:=(B+D)×(G+H)
M3:=(A−D)×(E+H)
M4:=A×(F−H)
M5:=(C+D)×(E)
M6:=(A+B)×(H)
M7:=D×(G−E)
only using 7 multiplications
Then,
I:=M2+M3−M6−M7
J:=M4+M6
K:=M5+M7
L:=M1−M3−M4−M5
You may feel steps invlved in this algorithm to find result is larger in number than our conventional method. But we can observe that With this construction we have not reduced the number of multiplications. We need 8 multiplications to calculate the Zi,j matrices, when using standard matrix multiplication. But in stressens algorithm we need 7 multiplication to find product of 2 2by 2 matrix.So complexity reduced
As the order increases the complexity change will make that difference
We can also implement algorithms into programs using programming languages like C,CPP through this iterations can be done easily. So the result can be found quickly.
