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

Test network connections between any two pcs, Use Packet Tracer software to... Use Packet Tracer software to model the network that you have designed, and configure the network to make sure it is running properly. The following requirements should be met:

What is workstation, What is workstation? A workstation is a node in ne... What is workstation? A workstation is a node in network that is more useful and can occur local information processing or graphics processing. A workstation generally has an in

Subnet layer of the tcp-ip model, Q. Subnet layer of the TCP-IP model? ... Q. Subnet layer of the TCP-IP model? These two layers of the OSI correspond straight to the subnet layer of the TCP/IP model. Majority of the time the lower layers under the

Difference between trigger and rule, What is the difference between trigger... What is the difference between trigger and rule? Ans) The triggers are known as implicitly by database generated events, whereas stored procedures are known as explicitly by cli

Html, Write an HTML program segment that contains hypertext links from one ... Write an HTML program segment that contains hypertext links from one document to another.

Purpose of the tcp three step handshakes, Identify the purpose of the TCP t... Identify the purpose of the TCP three step handshakes Ans) The three step handshake establishes the parameters needed for a TCP connection. During the handshake process series n

Distance vector multicast routing protocol, DVMRP • Distance vector mu... DVMRP • Distance vector multicast routing protocol: Distance vector multicast routing protocol are abbreviated as DVMRP. These protocols are suitable for small networks which

Udp connection establishment & termination, simple introduction,defination ... simple introduction,defination and with example & digram

Determine the advantages of fast ethernet, Fast Ethernet Operates a... Fast Ethernet Operates at 100 Mbps faster speeds required for image processing, CAD, real-time audio and video No change in frame addressing, format or access method

Defining error detection, Problem 1. Explain the term Switching. Descri... Problem 1. Explain the term Switching. Describe the following Switching Mechanisms a) Circuit Switching b) Packet Switching c) Message Switching Defining Switching