Sparse Matrix and its representations
If most of the elements of 2-D matrix of m x n size have 0
value, then it is called a Sparse Matrix.
Why to use Sparse Matrix instead of simple matrix ?
•Storage: There are lesser non-zero elements than zeros and
thus lesser memory can be used to store only those elements.
•Computing time: Computing time can be saved by logically
Example:
designing a data structure traversing only non-zero elements..
0 0 3 0
4
0 0 5 7
0
0 0 0 0
0
0 2 6 0
Representing a sparse matrix by a 2D array leads to wastage of lots
of memory as zeroes in the matrix are of no use in most of the cases.
So, instead of storing zeroes with non-zero elements, we only store
non-zero elements.
This means storing non-zero elements with tuples- (Row, Column,
value).
Matrix Tuple Structure
Sparse Matrix Representations can be done in many ways following
are two common representations:
•Array representation
•Linked list representation
Method 1: Using Arrays
2D array is used to represent a sparse matrix in which there are three rows
named as
•Row: Index of row, where non-zero element is located
•Column: Index of column, where non-zero element is located
•Value: Value of the non zero element located at index – (row, column)
Method 2: Using Linked Lists
In linked list, each node has four fields. These four fields are defined as:
•Row: Index of row, where non-zero element is located
•Column: Index of column, where non-zero element is located
•Value: Value of the non zero element located at index – (row, column)
•Next node: Address of the next node
There are two types of sparse matrices:
•Lower Triangular sparse Matrix: In this matrix, all elements above the
main diagonal have a zero value. a[i][j]=0 for i<j
•Upper Triangular sparse Matrix : In this matrix, all elements below the
main diagonal have a zero value a[i][j]=0 for i>j
• Tridiagonal sparse matrix: In this all the elements with non-zero value
appear only on the diagonal or above diagonal or below diagonal. A[i][j]=0
where |i-j|>1. a)In diagonal, non-zero elements for i=j.) In below, non-zero
elements for i=j+1. c) In above, non-zero elements for i=j-1
Why does storing of sparse matrices need extra consideration? How
are sparse matrices stored efficiently in the computer’s memory?
Sparse matrix is a matrix that has large number of elements with zero
value. In order to efficiently utilize in the memory, specialized algorithms
and data structures that take the advantage of the structure should be
used. If we apply the operations using standard matrix structures and
algorithms to sparse matrices, then the execution will slow down and the
matrix will consume larze amount of memory. Sparse data can be easily
compressed, which in turn can significantly reduce memory usage.
