Matrix computation and multiplication, Computer Networking

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







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
Related Questions
TCP creates a reliable data transfer service, in addition to IP''s unreliable best-effort service. Study the related sections of the text, and in your own words, summarize how TCP

Programming Based on Data Parallelism In a data parallel programming model, the focus is on data distribution. Every processor works with a portion of data. We shall discuss on

Can you describe how BGP does the decision process?

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

Elaborate the term - Database Connectivity Basic connectivity A number of database management systems are available today such as the Oracle, Sybase, Ingres, etc. Most

Cost Saving Better performance  scalability  and viability  translates into  saving  for  website  operators.  Because  fewer  application  web servers are required  to meet

Name the types of OSPF Configuration? Ans) There are Two Types of OSPF configuration A ) SINGLE AREA b) MULTI AREA

Router A router is used to route (transfer) data among two or more same networks. It verifies the next network point to which a data packet should be forwarded. The router is l

What is a Counter A software code that indicates how many times a site has been visited. It gets automatically updated and is usually represented by a small rectangle with n

What is the default CDP broadcast update rate for Cisco routers? Ans) Cisco Discovery Protocol is a proprietary protocol to permit you to access configuration information on oth