Representation of a sparse matrix, Data Structure & Algorithms

Assignment Help:

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroes. It is nothing but wastage of memory. In real life, such wastage might count to megabytes. Thus, an efficient method of storing sparse matrices ought to be looked into.

Figure illustrates a sparse matrix of order 7 × 6.

 

 

0

 

1

 

2

 

3

 

4

 

5

 

0

 

0

 

0

 

0

 

5

 

0

 

0

 

1

 

0

 

4

 

0

 

0

 

0

 

0

 

2

 

0

 

0

 

0

 

0

 

9

 

0

 

3

 

0

 

3

 

0

 

2

 

0

 

0

 

4

 

1

 

0

 

2

 

0

 

0

 

0

 

5

 

0

 

0

 

0

 

0

 

0

 

0

 

6

 

0

 

0

 

8

 

0

 

0

 

0

 

Figure: Representation of a sparse matrix of order 7 × 6

A general way of representing non zero elements of any sparse matrix is the 3-tuple form. The primary row of sparse matrix always indicates the number of columns, the number of rows, & number of non zero elements in the matrix. The number seven represents the entire number of rows sparse matrix. Alike, in the matrix the number six represents the total number of columns. The number eight represents the overall number of non zero elements in the matrix. Each of non zero element is stored from the second row, along the 1st & 2nd elements of the row, mentioning the row number & column number respectively wherein the element is present in the original matrix. In this row the 3rd element stores the actual value of the non zero element. For instance, the 3- tuple representation of the matrix of Figure is illustrated in Figure

1382_Representation of a sparse matrix.png

Figure: tuple representation of above figure

The following program 1 accepts a matrix as input that is sparse & prints the corresponding 3-tuple representations.


Related Discussions:- Representation of a sparse matrix

Enumerate about the data structure, Enumerate about the Data structure ...

Enumerate about the Data structure An arrangement of data in memory locations to signify values of the carrier set of an abstract data type. Realizing computational mechanis

Array, extra key inserted at end of array is called

extra key inserted at end of array is called

Multiple stacks, how multiple stacks can be implemented using one dimension...

how multiple stacks can be implemented using one dimensional array

Progrrame, how to write a code for for a company , for calculate the salary...

how to write a code for for a company , for calculate the salary pay

Insertion in list, In the array implementation of lists, elements are store...

In the array implementation of lists, elements are stored into continuous locations. In order to add an element into the list at the end, we can insert it without any problem. But,

Write a procedure that produces independent stack, Write a procedure (make-...

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g. (define stack1 (make-stack))  (define stack2 (make-stack)) W

Depth first search and breadth first search, Q. Illustrate the result of ru...

Q. Illustrate the result of running BFS and DFS on the directed graph given below using vertex 3 as source.  Show the status of the data structure used at each and every stage.

The complexity of multiplying two matrices, The complexity of multiplying t...

The complexity of multiplying two matrices of order m*n and n*p is    mnp

Determine the algorithm for z-buffer method, Algorithm for Z-Buffer Method ...

Algorithm for Z-Buffer Method (a)  Initialize every pixel in the viewport to the smallest value of z, namely z0 the z-value of the rear clipping plane or "back-ground". Store a

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