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.

Posted Date: 3/2/2013 6:54:05 AM | Location : United States

Ask an Expert

Related Discussions:- Matrix computation and multiplication, Assignment Help, Ask Question on Matrix computation and multiplication, Get Answer, Expert's Help, Matrix computation and multiplication Discussions

Write discussion on Matrix computation and multiplication
Your posts are moderated

Write your message here..

Related Questions

Difference between a domain and workgroup, What is a difference between a d... What is a difference between a domain and workgroup?

State about the future of the intranet, Future of the intranet At ... Future of the intranet At present, the world of information technology is guided bythe C 3 paradigm that stands for Command, Control and Communication, which is normally

Calculate the efficiency of stop and wait arq, (i)  Suppose that frames are... (i)  Suppose that frames are 1250 bytes long including 25 bytes of overhead. Also assume that ACK frames are 25 bytes long. a)  Calculate the efficiency of stop-and-wait ARQ in

What are the trends in network security, Q. What are the trends in Network ... Q. What are the trends in Network Security ? Trends in Network Security Improved vigilance for virus infections Continual maturation of firewall technologies

Name some common or popular databases, Name some common or popular database... Name some common or popular databases Many of the popular databases also provide support of and to the middleware and consequently, the term middleware has become lesser known.

What is full-duplex ethernet, Full-Duplex Ethernet 10Base5 as well ... Full-Duplex Ethernet 10Base5 as well as 10Base2 are half-duplex Full-duplex raises capacity of each domain No require for CSMA/CD

Security control procedures , a) An Introduction/Overview of Network Securi... a) An Introduction/Overview of Network Security issues. b) A Risk Assessment  analysis- to include:             Assets                                                         T

Little spider, #question.what can we do with a spider when it red?. #question.what can we do with a spider when it red?.

Explain the characteristics of mobile computing applications, Question : ... Question : a) In your view, what are the top three strengths and weaknesses of wireless systems? Rank them in order of priority. What can be done to address the weaknesses?

Processor arrangements-array, Processor Arrangements It is a very frequ... Processor Arrangements It is a very frequent event in data parallel programming to group a number of processors to perform definite tasks. To reach this goal, HPF gives a direc