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
Decision Tree - ID3 algorithm: Imagine you only ever do one of the following four things for any weekend:   go shopping   watch a movie   play tennis   just

Ordinary variable An ordinary variable of a easy data type can store a one element only

Addition of new records in a Binary tree structure always occurs as leaf nodes, which are further away from the root node making their access slower. If this new record is to be ac

how to creat atm project by using linked list?

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

Complexity is the rate at which the needed storage or consumed time rise as a function of the problem size. The absolute growth based on the machine utilized to execute the program

Tree is a widely used data structure employed for representing several problems. We studied tree like a special case of acyclic graph. Though, rooted trees are most prominent of al

Example 1:  Following are Simple sequence of statements Statement 1;  Statement 2; ... ... Statement k; The entire time can be found out through adding the times for

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

Ans: A procedure to reverse the singly linked list: reverse(struct node **st) { struct node *p, *q, *r; p = *st; q = NULL; while(p != NULL) { r =q;