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

Worst case and average case, Worst Case: For running time, Worst case runn...

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo

Write down any four applications of queues, Write down any four application...

Write down any four applications of queues.            Application of Queue (i)  Queue is used in time sharing system in which programs with the similar priority form a queu

Sparse matrices, SPARSE MATRICES Matrices along with good number of zer...

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

Recursive and iterative handling of a binary search tree, This section pres...

This section prescribes additional exercise with the recursive and iterative handling of a binary search tree. Adding to the Binary Search Tree Recursively Add implementation

Discuss the brute force algorithm, Question 1 What do you mean by Amortiza...

Question 1 What do you mean by Amortization? Question 2 Explain the following Big Oh notation (O) Omega notation (Ω) Theta notation (Θ)   Question 3 Di

Process of channel access, Channel access In first generation systems, ...

Channel access In first generation systems, every cell supports a number of channels. At any given time a channel is allocated to only one user. Second generation systems also

HUFFMAN CODING, Ask question 1. Indicate whether each of the following prop...

Ask question 1. Indicate whether each of the following properties is true for every Huffman code. a. The codewords of the two least frequent symbols have the same length. b. The

Explain the memory function method, Explain the Memory Function method ...

Explain the Memory Function method The Memory Function method seeks to combine strengths of the top  down and bottom-up approaches  to  solving  problems  with  overlapping  su

Illustrate an example of algorithm, Illustrate an example of algorithm ...

Illustrate an example of algorithm Consider that an algorithm is a sequence of steps, not a program. You might use the same algorithm in different programs, or express same alg

Data mining assignment, The assignment aims at consolidating your knowledge...

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn

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