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

Indexed sequential files, Indexed Sequential Files An index is inserted...

Indexed Sequential Files An index is inserted to the sequential file to provide random access. An overflow area required to be maintained to permit insertion in sequence. I

Graphs, c program to represent a graph as an adjacency multilist form

c program to represent a graph as an adjacency multilist form

Pipelining., How branching takes place in Instruction pipeline. Explain wit...

How branching takes place in Instruction pipeline. Explain with suitable examples

Define threaded binary tree, Threaded Binary Tree:- By changing the NUL...

Threaded Binary Tree:- By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using

Implement the physat algorithm, The first assignment in this course require...

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

Program on radix sort., Write a program that uses the radix sort to sort 10...

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

What is assertions, What is Assertions Introduction At every point...

What is Assertions Introduction At every point in a program, there are generally constraints on the computational state that should hold for program to be correct. For ins

Explain worst fit method, Worst Fit method:- In this method the system alw...

Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

Usage of linked lists for polynomial manipulation, Q. Establish the usage o...

Q. Establish the usage of linked lists for polynomial manipulation.                                       Ans. Usag e of Linked List for Polynomial Manipulation. Link

Program segment for deletion of any element from the queue, Program segment...

Program segment for deletion of any element from the queue delete() { int delvalue = 0; if (front == NULL) printf("Queue Empty"); { delvalue = front->value;

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