Storing a sparse matrix in memory, Data Structure & Algorithms

Explain an efficient method of storing a sparse matrix in memory. Write a module to find the transpose of the sparse matrix stored in this way.

A matrix which contains number of zero entries in much higher number than the number of non zero entries is called sparse matrix. The normal method of representing matrices in memory as two-dimensional arrays may not be appropriate for sparse matrices. One may save space by storing only nonzero entries in the matrix. For example the matrix A (3*3 matrix) represented below

0      2     0

5     0     0

0     6     9

can be written in the sparse matrix form as follows:

3     3     4

0     1     2

1     0     5

2     2     6

2     3     9

Where the first row represent the dimension of matrix and last column tells us the number of nonzero values; second row onwards it is giving the position and value of the non zero number.

 

A function which is used to find transpose of a sparse matrix is:

void  transpose(x,r,y)

int x[3][3],y[3][3],r;

{

int i,j,k,m,n,t,p,q,col;

m=x[0][0];

n=x[0][1];

t=x[0][2]; y[0][0]=n; y[0][1]=m; y[0][2]=t;

if(t>0)

{

q=1;

for (col=0;col<=n;col++)

for(p=1;p<=t;p++)

if(x[p][1]==col)

{

y[q][0]=x[p][1]; y[q][1]=x[p][0]; y[q][2]=x[p][2];

q++;

}

}

return;

}

 

Posted Date: 7/9/2012 9:54:19 PM | Location : United States







Related Discussions:- Storing a sparse matrix in memory, Assignment Help, Ask Question on Storing a sparse matrix in memory, Get Answer, Expert's Help, Storing a sparse matrix in memory Discussions

Write discussion on Storing a sparse matrix in memory
Your posts are moderated
Related Questions
In this unit, we discussed Binary Search Trees, AVL trees and B-trees. The outstanding feature of Binary Search Trees is that all of the elements of the left subtree of the root

. Create a decision table that describes the movement of inventory

Explain the Assertions in Ruby Ruby offers no support for assertions whatever. Moreover, because it's weakly typed, Ruby doesn't even enforce rudimentary type checking on opera

In file access: what is the difference between serial, sequential and indexed sequential searching

Data records are stored in some particular sequence e.g., order of arrival value of key field etc. Records of sequential file cannot be randomly accessed i.e., to access the n th

A full binary tree with 2n+1 nodes have n non-leaf nodes

State the example of pre- and post-conditions Suppose that function f(x) should have a non-zero argument and return a positive value. We can document these pre- and post-condit

The structures of files vary from operating system to operating system. In this unit, we will discuss the fundamentals of file structures with the generic file organisations. A

Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text