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
A common person's faith is that a computer can do anything. It is far from truth. In realism computer can carry out only definite predefined instructions. The formal illustration o

what is frequency count with examble

This algorithm inputs 3 numbers, every number goes through successive division by 10 until its value is less than 1. An output is produced which comprise the number input and a val

For AVL trees the deletion algorithm is a little more complicated as there are various extra steps involved in the deletion of node. If the node is not a leaf node, then it contain

implement multiple stacks ina single dimensional array. write algorithams for various stack operation for them.

write a c++ program to find out the area of a curve y=f(x) between x=a and x=b

SPARSE MATRICES Matrices along with good number of zero entries are called sparse matrices. Refer the following matrices of Figure (a)

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

1. Start 2. Get h 3. If h T=288.15+(h*-0.0065) 4. else if h T=216.65 5. else if h T=216.65+(h*0.001) 6. else if h T=228.65+(h*0.0028) 7. else if h T=270.65 8.

Prim's algorithm employs the concept of sets. Rather than processing the graph by sorted order of edges, this algorithm processes the edges within the graph randomly by building up