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
This algorithm inputs 5 values and outputs how many input numbers were positive and how many were negative. Data to be used: N = 1, -5, 2, -8, -7

Write an algorithm using pseudocode which takes temperatures input over a 100 day period (once per day) and output the number of days when the temperature was below 20C and the num

In the amortized analysis, the time needed to perform a set of operations is the average of all operations performed. Amortized analysis considers as a long sequence of operations

Define File organization''s and it''s types

Linked lists are among the most common and easiest data structures. They may be used to implement various other common abstract data types, including queues, stacks, symbolic expre

Part1: Deque and Bag Implementation First, complete the Linked List Implementation of the Deque (as in Worksheet 19) and Bag ADTs (Worksheet 22). Files Needed: linkedList.c Linke

A mathematical-model with a collection of operations described on that model is known as??? Abstract Data Type

implementation of fast fourier transforms for non power of 2

implement multiple stacks in an array and write different algorithms to perform operations on it

Deletion Algorithm for dequeue Step 1: [check for underflow]   If front = 0 and rear = 0   Output "underflow" and return Step 2: [delete element at front end]   If front