Sparse Matrix:
A matrix that has minimum number of non-zero elements is called a sparse matrix i.e. very few elements are sparsely distributed in the matrix.
Example: An array of order 3 x 4 containing sparsely located non-zero elements.
|
0 |
1 |
2 |
3 |
|
|
0 |
0 |
25 |
0 |
7 |
|
1 |
0 |
0 |
2 |
8 |
|
2 |
0 |
0 |
1 |
0 |
(Order 3 x 4)
In the above example, out of 12 elements only 5 elements contain non zero values. Such a matrix is called sparse matrix.
Representation of Sparse Matrix:
- 3-Tuple Representation
- List Representation
1. 3-Tuple Representation: An array of three columns is required. The size of the array is the number of non-zero elements plus one. First row is called the header row that contains total number of rows, total number of columns and non-zero element’s value i.e.
Header Row: Row | Column | Element
|
rows |
columns |
Elements (non zero) |
|
|
0 |
3 |
4 |
5 |
|
1 |
0 |
1 |
25 |
|
2 |
0 |
3 |
7 |
|
3 |
1 |
2 |
2 |
|
4 |
1 |
3 |
8 |
|
5 |
2 |
2 |
1 |
Sparse Matrix representation for the array given above
Number of rows: 3
Number of columns: 4
Number of elements: 5
Order of Sparse Matrix = (5+1) x 3 = 6 x 3.
2. List Representation: Each row is converted to a node in linked representation where each node contains, row subscripts, column subscript and non-zero element. The first node returns the total number of rows, columns and elements.
Example:
3|4|5 -> 0|1|25 -> 0|3|7 -> 1|2|2 -> 1|3|8 -> 2|2|1 -> NULL
Array representation of Sparse Matrix
Linked representation of Sparse Matrix