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

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.

Posted Date: 7/13/2012 2:56:02 AM | Location : United States







Related Discussions:- Representing sparse matrix in memory using array, Assignment Help, Ask Question on Representing sparse matrix in memory using array, Get Answer, Expert's Help, Representing sparse matrix in memory using array Discussions

Write discussion on Representing sparse matrix in memory using array
Your posts are moderated
Related Questions
What do you mean by complexity of an algorithm? The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space need of the algorithm i

Your objective is to write a generic doubly linked list class called CS228LinkedList that implements the List interface and uses a type variable T. All methods except for subList a

Binary Search Tree let three types of traversals by its nodes. They are: Pre Order Traversal In Order Traversal Post Order Traversal In Pre Order Traversal, we ca

The space-complexity of the algorithm is a constant. It just needs space of three integers m, n and t. Thus, the space complexity is O(1). The time complexity based on the loop

What is the time complexity of Merge sort and Heap sort algorithms? Time complexity of merge sort is O(N log2 N) Time complexity of heap sort is   O(nlog2n)

Explain about Franklin Algorithm We mentioned how the number of possible comparisons of polygons grows as the square of the number of polygons in the scene. Many of the hidden-

Q. The two Binary Trees are said to be similar if they are both empty or if they are both non- empty and left and right sub trees are similar. Write down an algorithm to determine

Algorithm for determining strongly connected components of a Graph: Strongly Connected Components (G) where d[u] = discovery time of the vertex u throughout DFS , f[u] = f

Q. Explain that how do we implement two stacks in one array A[1..n] in such a way that neither the stack overflows unless the total number of elements in both stacks together is n.

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.