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

Building a http server, IMPORTANT: The web server should be able to serve H... IMPORTANT: The web server should be able to serve HTTP files only. You will not need to implement the directory listing and CGI-bin. Purpose The objective is to implement a H

Error control in TCP, Q. Show the Error control in TCP? Error control ... Q. Show the Error control in TCP? Error control in TCP Detect lost segments, out-of-order segments, corrupted segments and duplicated segments Three tools: chec

Ajax, Ajax is a relatively new set of techniques that, in a sense, implemen... Ajax is a relatively new set of techniques that, in a sense, implement some of the functionalities originally provided by RPC. Ajax is primarily used to build web applications with

State in brief about the information access intranet, State in brief about ... State in brief about the Information Access Intranet This type of Intranet is the type commonly found on the World Wide Web. The static web page may include information on

What are the value added services, What are the value added services Ma... What are the value added services Many organisations are demanding higher services (also called value added services) such as faxing, minimal cost call routing, connectivity to

Persistent and no persistent connections, Persistent and No persistent Conn... Persistent and No persistent Connections HTTP can use  both  persistent  and non persistent connection. By defaults  uses persistent  connections. Persistent Connections

Application layer - computer network, Application Layer The  applicati... Application Layer The  application layer is where  network  applications and their  application layer protocols  reside. The internet application layer includes many protocols

Disadvantage of vpns - point to point , Disadvantage of VPNs The disad... Disadvantage of VPNs The disadvantages of VPN  are related to implementation troubleshooting  trust and  internet  availability. a.Implementation  can be time consuming: Im

Which layer are called upper layer, Three layers are called upper layers ... Three layers are called upper layers a) Application Layer - 7 b) Presentation Layer - 6 c) Session Layer - 5

Describe the concept of nat, Can you describe the concept of NAT Can you describe the concept of NAT