In the following section, we shall discuss the algorithms for solving the matrix multiplication difficulty using the parallel models.
Matrix Multiplication Problem
Let there be two matrices, M1 and M2 of sizes a x b and b x c respectively. The product of
M1 x M2 is a matrix O of size a x c.
The values of elements stores in the matrix O are according to the given formulae:
Oij = Summation x of (M1ix * M2xj) x=1 to b, where 1 Keep in mind, for multiplying a matrix M1 with another matrix M2, the number of columns in M1 must equivalent number of rows in M2. The well identified matrix multiplication algorithm on sequential computers takes O(n3) running time. For multiplication of two 2x2, matrices, the algorithm needs 8 multiplication operations and 4 addition operations. Another algorithm known as Strassen algorithm has been devised which needs 7 multiplication operations and 14 addition and subtraction operations. Thus, the time complexity of Strassen's algorithm is O(n2.81). The basic sequential algorithm is given below: Algorithm: Matrix Multiplication Input// Two Matrices M1 and M2 For I=1 to n For j=1 to n { Oij = 0; For k=1 to n Oij= Oij + M1ik * M2kj End For } End For End For Now, let us change the above discussed matrix multiplication algorithm according to parallel computation models.
Keep in mind, for multiplying a matrix M1 with another matrix M2, the number of columns in M1 must equivalent number of rows in M2. The well identified matrix multiplication algorithm on sequential computers takes O(n3) running time. For multiplication of two 2x2, matrices, the algorithm needs 8 multiplication operations and 4 addition operations. Another algorithm known as Strassen algorithm has been devised which needs 7 multiplication operations and 14 addition and subtraction operations. Thus, the time complexity of Strassen's algorithm is O(n2.81). The basic sequential algorithm is given below:
Algorithm: Matrix Multiplication
Input// Two Matrices M1 and M2
For I=1 to n
For j=1 to n
{
Oij = 0;
For k=1 to n
Oij= Oij + M1ik * M2kj
End For
}
Now, let us change the above discussed matrix multiplication algorithm according to parallel computation models.