Short Notes: Sparse Matrices | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

 Page 1


SPARSE MATRICES
> A sparse matrix is a matrix in which most of the elements of the array are 0.
> There is no exact definition of how many zeroes should be there for a matrix to be called a 
sparse matrix.
> The following matrix can be considered sparse.
0 22 0 1 0 0 0 0 55
0 0 0 0 0 1 55 0 9
0 8 2 0 0 4 0 0 0
4 0 0 0 3 0 0 0 0
78 0 0 0 0 0 0 4 9
0 4 0 2 0 71 3 0 0
> A sparse matrix can be represented as a general matrix. But considering the fact that most 
of the elements are zero, we can use a different representations that uses less amount of 
space.
> One such representation is 3-tuple form.
> In three tuple form, each element is represented by three fields. The first field is row 
number, second is column number and the third is the value.
> But we need not store the three tuple form of zeroes.
> The three tuple form of the above matrix (first three rows) is as follows:
int sparse[][]={ 0,1,22,
0,3,1,
0,8,55,
1,5,1,
1,6,55,
1,8,9,
2,1,8, // And so on
};
> Consider an n X m matrix. Let the number of non-zero elements be x. In 3-tuple form, we 
need 3*x number of storage. So if
3*x < n*m
then 3-tuple form saves space. Otherwise, this method is not very efficient.