Matrix is defined with a 2-dimensional array that has row and column. An array which has ‘m’ rows and ‘n’ columns represent an mXn matrix.
Sometimes it happens when a matrix has zero values is more than NON-ZERO values.
The matrix which has a greater number of zero values in comparison to the non-zero values is known as a sparse matrix.
In the above example we have 4 X 4 matrix where only 5 values are non-zero and rest of the value are zero.
So if we calculate the space
Integer value takes 2 bytes
Total space taken by 4 X 4 matrix is 4 X 4 X 2 = 32 bytes.
Where only 5 X 2 = 10 bytes are in use which has a non-zero value and the rest 32 – 10 = 22 bytes are wastage of memory. This can also be less.
But if we have large number of data in matrix like there is a matrix of size 100 X 100 which contains only 10 non-zero elements and 90 zero elements.
So from the above scenario, it is visible that only 10 spaces are filled with non-zero values, and the remaining spaces of a matrix are filled with zero values.
This matrix will take a total of 100 X 100 X 2 = 20000 bytes of space to store this integer matrix. And to search these 10 non-zero elements, we have to scan all elements of this matrix 10000 times.
Now to save the memory and searching time, we use Sparse matrix representation.
Loss of memory is high when we represent the sparse matrix with the help of a 2-dimensional array.
We can overcome this situation and can save money by the following representation explained below.
Sparse Matrix Representations
A sparse matrix can be represented in two way:
1. Triplet Representation
2. Linked Representation
Triplet Representation
In Triplet Representation of a sparse matrix, we consider only non-zero values along with their row and column index values. The 0th row of the matrix stores the total number of rows, total number of columns, and total non-zero values.
For example, consider a matrix of size 4 X 4 containing 5 number of non-zero values.
Sparse matrix representation in a data structure
In the above example of the matrix, there are only five non-zero elements, those are 3, 8, 1, 3, 7, and matrix size is 4 X 4. We represent this matrix in triplet representation (row, column, value), as shown in the above image.
Linked Lists Representation
In linked list representation, we use a linked list to represent a sparse matrix. Each node of the linked list has four fields.
These four fields are defined as:
Row: Row keeps row index of a non-zero element
Column: Column keeps column index of a non-zero element
Value: non zero element located at (row,column) index
Next node: Next node, stores the address of the next node
Why Sparse Matrix a better option over a simple matrix?
It saves the memory only by storing non-zero elements when a non-zero element is lesser than zeros.
It saves Computing time because, in a sparse matrix, logically designed data structure traverses only non-zero elements.
Operations of Sparse Matrix
We can perform 3 operations on Sparse Matrix
- Add
- Multiply
- Transpose
