Representing sparse matrix in memory using array, Data Structure & Algorithms

Assignment Help:

Q. What do you understand by the term sparse matrix? How sparse matrix is stored in the memory of a computer? Write down the function to find out the transpose of a sparse matrix using this particular representation.                                                                                                             

Ans.

Sparse Matrix is described below

A m x n matrix A would be a sparse if most of its elements are zero. A matrix that is not sparse is known as dense matrix.

Representing Sparse Matrix in Memory Using Array is described below

In an array representation an array of triplets of type < row, col, element> is used to store non-zero elements, where 1st field of the triplet is used to trace row position second to record column and the 3rd to record the non zero elements of  sparse matrix.

In addition, we are required to record the size of the matrix ( i.e. number of rows and the number of columns) and non zero elements of array of triplets are used for this purpose where the 1st filed saves the number of rows and the 2nd field saves the number of columns and the third field saves the number of non zero elements. The remaining elements of the array saves matrix on row major order. The array representation will be

[2 * (n+1) * size of (int) + n*size of(T)] bytes of memory where n is the number of non-zero elements and T is the data type of the element.

Ex: consider a 5*6 sparse matrix which is written below

1713_sparse matrix2.png 

Array Representation of Sparse Matrix is given below

1754_sparse matrix3.png

Here n = 5 but the size of array is 6 as first row saves the order of array along with a number non-zero elements.

Memory declaration will be as followsas shown below

# define Max 50 struct triplet

{   int row;

int col;

float element;

}

struct triplet sparse_mat [MAX];

sparse matrix represented as above

[n is the number of non zero elements in array]

for I= 1,2,...n+1 temp = a[I].row a[I].row= a[I].col a[I].col = temp endfor.


Related Discussions:- Representing sparse matrix in memory using array

Binary search tree (bst), Q. Explain what do we understand by Binary Search...

Q. Explain what do we understand by Binary Search Tree (BST)? Make a BST for the following given sequence of the numbers. 45, 32, 90, 21, 78, 65, 87, 132, 90, 96, 41, 74, 92

Write a function that performs integer division, Write a function that perf...

Write a function that performs integer division. The function should take the large number in memory location 1 and divide it by the large number in memory location 2 disregarding

State the output of avaerage value of numbers, Draw trace table and determi...

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

Data type, Data type An implementation of an abstract data type on a...

Data type An implementation of an abstract data type on a computer. Therefore, for instance, Boolean ADT is implemented as the Boolean type in Java, and bool type in C++;

How do collisions happen during hashing, How do collisions happen during ha...

How do collisions happen during hashing? Usually the key space is much larger than the address space, thus, many keys are mapped to the same address. Assume that two keys K1 an

Efficient way of storing two symmetric matrices, Explain an efficient way o...

Explain an efficient way of storing two symmetric matrices of the same order in memory. A n-square matrix array is said to be symmetric if a[j][k]=a[k][j] for all j and k. For

Draw a b-tree., Q. Draw a B-tree of order 3 for the sequence of keys writte...

Q. Draw a B-tree of order 3 for the sequence of keys written below: 2, 4, 9, 8, 7, 6, 3, 1, 5, 10

Data manipulation, perform the following length operation LENGTH("welcome t...

perform the following length operation LENGTH("welcome to ICA")=

Program to implementing stack using linked lists, include include i...

include include include /* Definition of structure node */ typedef struct node { int data; struct node *next; } ; /* Definition of push function */

Multiple stacks in a single array, implement multiple stacks in an array an...

implement multiple stacks in an array and write different algorithms to perform operations on it

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