Storing a sparse matrix in memory, Data Structure & Algorithms

Assignment Help:

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;

}

 


Related Discussions:- Storing a sparse matrix in memory

Darw a flowchart that inputs country someone is visiting, Regis lives in Br...

Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f

Usage of linked lists for polynomial manipulation, Q. Establish the usage o...

Q. Establish the usage of linked lists for polynomial manipulation.                                       Ans. Usag e of Linked List for Polynomial Manipulation. Link

Problem logicall, Given a list containing Province, CustomerName and SalesV...

Given a list containing Province, CustomerName and SalesValue (sorted by Province and CustomerName), describe an algorithm you could use that would output each CustomerName and Sal

Determination of time complexity, Determination of Time Complexity The...

Determination of Time Complexity The RAM Model The random access model (RAM) of computation was devised through John von Neumann to study algorithms. In computer science,

Multiple stacks, how multiple stacks can be implemented using one dimension...

how multiple stacks can be implemented using one dimensional array

The best average behaviour, The best average behaviour is shown by  Qui...

The best average behaviour is shown by  Quick Sort

Estimate the probability that the noncritical path , An advertising project...

An advertising project manager developed the network diagram shown below for a new advertising campagign.  In addition, the manager gathered the time information for each activity,

Time complexity of merge sort and heap sort algorithms, What is the time co...

What is the time complexity of Merge sort and Heap sort algorithms? Time complexity of merge sort is O(N log2 N) Time complexity of heap sort is   O(nlog2n)

Technique for direct search, Technique for direct search is    Hashing ...

Technique for direct search is    Hashing is the used for direct search.

Inorder traversal, Inorder traversal: The left sub tree is visited, then t...

Inorder traversal: The left sub tree is visited, then the node and then right sub-tree. Algorithm for inorder traversal is following: traverse left sub-tree visit node

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd