Question

Define a sparse matrix. Explain an efficient way of storing sparse matrix in the memory of a computer. Write an algorithm to find the transpose of sparse matrix using this representation. 

Answer 1

Sparse Matrix Definition: - A matrix in which number of zero entries are much higher than the number of non zero entries is called sparse matrix.

An efficient way of storing sparse matrix

The natural method of representing matrices in memory as two-dimensional arrays may not be suitable for sparse matrices. One may save space by storing only nonzero entries. For example matrix A (4*4 matrix) represented below 

0	0	0	12
0	0	0	0
0	9	0	0
0	0	4	0

Here the memory required is 16 elements x 2 bytes = 32 bytes The above matrix can be written in sparse matrix form as: 

4	4	3
0	3	1
2	1	9
3	2	4

Here the memory required is 12 elements x 2 bytes = 24 bytes where first row represent the dimension of matrix and last column tells the number of non zero values; second row onwards it is giving the position and value of non zero number. 

An algorithm to find transpose of a sparse matrix is as below: 

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; 

}