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

Example of Area Subdivision Method The procedure will be explained with respect to an illustrative problem, with the image consisting of five objects, namely a triangle (T), qu

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive me

Explain process of B-TREE and what difference between AVL Tree Using Algorithms

Typical programming languages such as Pascal, C or Java give primitive data kinds such as integers, boolean, reals values and strings. They give these to be organised into arrays,

This is a k-ary position tree wherein all levels are filled from left to right. There are a number of specialized trees. They are binary trees, AVL-trees, binary search trees, 2

There are three kinds of tree traversals, namely, Postorder , Preorder and Inorder. Preorder traversal: Each of nodes is visited before its children are visited; first the roo

This question deals with AVL trees. You must use mutable pairs/lists to implement this data structure: (a) Define a procedure called make-avl-tree which makes an AVL tree with o


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