Three types of Sparse Matrix
1). Lower triangular sparse matrix
2). Upper triangular sparse matrix
3). Tri-diagonal matrix
Lower Triangular Matrix / Sparse Matrix
In a Lower triangular sparse matrix, all elements above the main diagonal have a zero value. This type of sparse matrix is also known as a lower triangular matrix. If you see its pictorial representation, then you find that all the elements having non-zero value are appear below the diagonal.
In a lower triangular matrix, Arr i,j=0 where i<j.
A lower-triangular Matrix Arr of size n*n has one non-zero element in the first row, two non-zero elements in the second row, and similarly n non-zero elements in the nth row.
We use a one-dimensional array to store a lower-triangular matrix efficiently in the memory. This array stores only non-zero elements. To store in a one-dimensional array, we do the mapping between a two-dimensional matrix and a one-dimensional array. We can be done the mapping in any one of the following ways:
(a) Row-wise mapping— Here the contents of array Arr[] will be {1, 2, 2, 1, 4, 3, 9, 8, 7, 1, 1, 2, 7, 8, 9}
(b) Column-wise mapping— Here the contents of array Arr[] will be {1, 2, 1, 9, 1, 2, 4, 8, 2, 3, 7, 7, 1, 8, 9}
Upper Triangular Matrix / Sparse Matrix
In the Upper triangular sparse matrix, all elements below the main diagonal have a zero value. This type of sparse matrix is also known as an upper triangular matrix. If you see its pictorial representation, then you find that all the elements having non-zero value are appear above the diagonal.
In an upper-triangular matrix, Arr i,j=0 where i>j. An n*n upper-triangular matrix Arr has n non-zero elements in the first row, n–1 non-zero element in the second row, and likewise one non-zero element in the nth row.
(a) Row-wise mapping— Here the contents of array Arr[] will be {1, 1, 2, 5, 8, 2, 8, 9, 7, 3, 7, 2, 1, 5, 9}
(b) Column-wise mapping— Here the contents of array Arr[] will be {1, 1, 2, 2, 8, 3, 5, 9, 7, 1, 8, 7, 2, 5, 9}
Tri-diagonal matrix
Tri-diagonal matrix is also another type of a sparse matrix, where elements with a non-zero value appear only on the diagonal or immediately below or above the diagonal.
In a tridiagonal matrix, Arr i,j=0, where |i – j| > 1.
For matrix being a tridiagonal matrix element should present
(a) On the main diagonal means all non-zero elements at i=j and at all rest place zero. In this case, the total number of non-zero elements is n.
(b) at above the main diagonal means all non-zero elements at i=j–1. In this case, the total number of non-zero elements is n-1.
(c) at below the main diagonal means all non-zero elements for i=j+1. In this case, the total number of non-zero elements is n-1.
We only store non-zero elements. We can do the mapping between a two-dimensional matrix and a one-dimensional array the following ways:
(a) Row-wise mapping— Here the contents of array Arr[] will be {1, 1, 5, 2, 8, 8, 3, 2, 4, 1, 5, 7, 9}
(b) Column-wise mapping— Here the contents of array Arr[] will be {1, 5, 1, 2, 8, 8, 3, 4, 2, 1, 7, 5, 9}
(c) Diagonal-wise mapping— Here the contents of array Arr[] will be {1, 8, 2, 5, 1, 2, 3, 1, 9, 5, 8, 4, 7}