What is Sparse Matrix. Give the Triplet form of given Matrix. Also give Transpose Algorithm and Program
Sparse Matrix
A matrix which contains many zero entries or very few non-zero entries is called as Sparse matrix.
Triplet form of Matrix
An element within a matrix can characterize by using the triple that is Row, Column and Value This means that, an array of triples is used to represent a sparse matrix.
Why should we use Triplet form of matrix?
Triplet form of matrix can be used to use the available space efficiently.
The above Sparse matrix has 4 rows and 4 columns which means it contains 4*4 that is 16 elements inside it and each element is integer value which contains 2 bytes of storage and the total storage in the sparse matrix is 2*16 that is 32.
we can reduce this storge by eliminating the zero values. This can be done by representing the non zero values in array form.
We will represent 3 elements in array that is Row, Column and Value.
| ROW | COLUMN | VALUE |
|---|---|---|
| 1 | 3 | 3 |
| 2 | 4 | 8 |
| 3 | 1 | 1 |
| 3 | 3 | 3 |
| 4 | 3 | 7 |
Above we have used a 2 Dimensional array stored Row, Column and Value with 5 Rows and 3 Columns the total elements are 5*3 that is 15. and the total storage is 15*2 that is 30 which is lesser than the Sparse matrix.
by this method larger number of unused storage can be saved in large scale applications.
below is representation in linked list
Transpose of Matrix
To transpose a matrix, interchange the rows and columns. This means that each element a[i][j] in the original matrix becomes element a[j][i] in the transpose matrix.
Algorithm:-
- for all elements in column j
- place element in i, j, value in element j, i, value
Program:-
transpose(term a[], termb[]) {
/* b is set to the transpose of a */
int n, i, j, currentb;
n = a[0].value; /* total number of elements */
b[0].row = a[0].col; /* rows in b = columns in a */
b[0].col = a[0].row; /* columns in b = rows in a */
b[0].value = n;
if (n > 0) {
currentb = 1;
for (i = 0; i < a[O].col; i++)
for (j = 1; j <= n; j++)
if (a[j].col == i) {
b[currentb].row = a[j].col;
b[currentb].col = a[j].row;
b[currentb].value = a[j].value;
currentb++;
}
}
}