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

What are the things require to implement abstract data types, What are the ...

What are the things require to implement ADT Abstract data types are very useful for helping us understand the mathematical objects which we use in our computations but, of cou

Which are the two standard ways of traversing a graph, Which are the two st...

Which are the two standard ways of traversing a graph? i. The depth-first traversal   ii. The breadth-first traversal

Efficient algorithms.., implementation of fast fourier transforms for non p...

implementation of fast fourier transforms for non power of 2

Program for linear search, Program for Linear Search. Program: Linear S...

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Linked list, how to creat atm project by using linked list?

how to creat atm project by using linked list?

Bubble sort, In this sorting algorithm, multiple swapping occurs in one pas...

In this sorting algorithm, multiple swapping occurs in one pass. Smaller elements move or 'bubble' up to the top of the list, so the name given to the algorithm. In this method,

Write down the algorithm of quick sort, Write down the algorithm of quick s...

Write down the algorithm of quick sort. An algorithm for quick sort: void quicksort ( int a[ ], int lower, int upper ) {  int i ;  if ( upper > lower ) {   i = split ( a,

Comparisions and assignments in worst case, Q. Calculate that how many key ...

Q. Calculate that how many key comparisons and assignments an insertion sort makes in its worst case?        Ans: The worst case performance occurs in insertion

Queues, Queue is a linear data structure utilized in several applications o...

Queue is a linear data structure utilized in several applications of computer science. Such as people stand in a queue to get a specific service, several processes will wait in a q

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