A matrix is known as a sparse matrix when it contains more ZERO values than NON-ZERO values. A matrix that is not sparse is a knows as a dense matrix.
Wikipedia SVG image for Sparse Matrix
This concept is essential as the matrix can be designed to:
- Save Space: The sparse matrix is represented using forms where only the NON-ZERO elements and their locations are stored. This saves space over a simple matrix where ZERO elements would also consume memory.
- Save Computing Time: The sparse matrix can be stored in a way that accessing the elements becomes efficient.
Representation of sparse matrix
Sparse Matrices can be represented more efficiently by using the Triplet Representation or Linked Representation.
Array Triplet Representation
In this representation, only the NON-ZERO values are stored along with their row and column positions in the table. The triplet refers to the collection of the row, column and the value.
The representation is of the type:
< row, col, element >
The size of the matrix and also the number of NON-ZERO elements are also counted. This is stored in the first field in the array of triplets.
The array representation will use:
[2 * (n+1) * sizeof(int) + n * sizeof(T)] bytes of memory
where n is the number of NON-ZERO elements and T is the data type of the elements.
Linked Representation
A linked list may be used to store a sparse matrix by representing each NON-ZERO value as a node and linking this Node in a specific way such that it represents the position in the original array. Each node in the linked list has four fields:
- Row: Index of the row where the non-zero element is located
- Column: Index of the column where the non-zero element is located
- Value: Stores the value of the non-zero element
- Next node: Stores the address of the next node
Using this representation, each of the nodes that store a NON-ZERO value can be accessed quickly by traversing the linked list.
Both representations save space in storing the elements compared to a traditional array.