Matrix computation and multiplication, Computer Networking

Assignment Help:

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.


Related Discussions:- Matrix computation and multiplication

Explain point-to-point connection type, Explain Point-to-Point connection t...

Explain Point-to-Point connection type. Many point-to-point connections are associated with modems and PSTN (Public Switched Telephone Network) communications.

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

Analysis of parallel algorithms, A generic algorithm is mostly analyzed on ...

A generic algorithm is mostly analyzed on the basis of the following parameters: the time complexity (implementation time) and the space complexity (amount of space necessary). Usu

Calculate the amplifier''s gain in db, Quetion: An amplifier increases ...

Quetion: An amplifier increases the peak-to-peak voltage of a signal from 1 V to 20 V. What is the amplifier's gain in dB?

Analysis of sort_bitonic, The bitonic sorting network needed log n number o...

The bitonic sorting network needed log n number of stages for performing the task of sorting the list. The first n-1 stages of the circuit are able to sort two n/2 numbers and the

Parallel programming environment characteristics, Parallel Programming Envi...

Parallel Programming Environment Characteristics  The parallel programming environment consists of an debugger, a editor,  performance evaluator and programme visualizer for i

What are the control frames for lost tokens, Control Frames for Lost Tokens...

Control Frames for Lost Tokens If station goes down ... token lost Predecessor listens for data frame or token Noticing none, retransmits token Sends whofoll

Vpn technology - point to point , VPN Technology For an organization  ...

VPN Technology For an organization  VPN  technology  uses some main  techniques for privacy a.Encryption /Authentication b.Tunnelling c.Fire walls

#incident response scenario, assignment is for incident response In this ...

assignment is for incident response In this final week, you will provide a short procedures document (2–3 pages) concerning the steps by which to prepare for and execute expert te

Protocol comes under hybrid dynamic type, Which protocol comes under Hybrid...

Which protocol comes under Hybrid dynamic type? Ans)  EIGRP (ENHANCED INTERIOR GATEWAY ROUTING PROTOCOL) comes under hybrid dynamic.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd