Sparse Matrix

These are special type of matrices in which most of the elements are "0s" (zeros). That is, if a lot of elements  from a matrix have a value 0 then the matrix is known as sparse matrix.

There is no precise definition of when a matrix is sparse and when it is not, but it is a concept, which we all recognize intuitively. If the matrix is a sparse, we must consider an alternative way of representing it rather than the normal row-major or column-major arrangement. This is because a sparse matrix is a matrix containing very few non-zero elements. If the user stores the entire matrix including zero elements then there is a wastage of storage space.

There are two ways of representing a sparse matrix:

• Arrays representation
• Linked representation

In array representation of of a sparse matrix, only the non-zero elements are stored so that storage space can be reduced. Each non-zero element in the sparse matrix is represented as (Row, Column, Value).

For this, a two-dimensional array containing 3 columns can be used. The first column is for storing the row number, the second column is for storing the column number and the third column is represents the value of corresponding to non-zero element at (row, column) in the first two columns. For example, consider the following sparse matrix.

Sparse Matrix of 5X6 Order

The above matrix can be represented as

Row	Column	Value
0	3	8
1	2	1
1	5	7
2	1	3
3	2	2
4	5	5

The structure declaration of array is given below:

#define MAX 50

struct triplet

{

int row;

int column;

int element;

}spmatrix[MAX];

The maximum number of non-zero elements in the sparse matrix is defined by constant MAX.

The array representation will use, [2*(n+1)*size of (int) + n*size of (T)] bytes of memory where n is the number of non-zero bytes and T is the data type of elements.

The major limitation of of array representation of a sparse matrix is that we need to know the number of non-zero elements in the matrix.

In the linked list representation, a separate list is maintained for each column as well as each row of the matrix, i.e., if the matrix is of size 4 X 4, then there would be 4 lists for 4 columns and 4 lists for 4 rows.

The head node for the column list stores the column number, a pointer to the node which comes first in the column and a pointer to the next column head node.

The head node for the row list stores, a pointer to the node, which comes first in the row list, and a pointer to the next row head node.

A node on the other hand stores the row number, column number and the value of the non-zero element of the sparse matrix. It also stores a pointer to the node that is immediatly to the right of the node in the row list as well as a pointer to the node that is immediatly below the node in the column list.

For example: A sparse matrix (5 X 6), the figure is given above:

The linked list representation of the above matrix is:

Linked List Representation of Sparse Matrix