Sparse Matrices
A matrix were most of the elements are zeros is called sparse matrix. Sparse matrix cannot be efficiently handled, when we are dealing with matrices of size 100 X 100 and if only 1000 entries are non-zeros and remaining location are filled with zeros. These leads to huge amount of memory wastage. The waste memory locations are 10000-1000=9000 i.e., 9000 memory location filled with zeros. Hence huge amount of memory is wasted. To avoid this we use another alternative representation, which will explicitly stores non-zero elements. This representation is called 3-Tuples or Triples.
In this representation, each element of the matrix is characterized by its row and column position say I, j. We will store the matrix as a list of three tuples in the form of (I, j, value).
Consider a sparse matrix shown below
0 1 0 0
B= 2 0 0 -3
The 3- tuples representation of above matrix is as follows
B
|
Row
|
Column
|
value
|
0
|
3
|
4
|
4
|
1
|
1
|
2
|
1
|
2
|
2
|
1
|
2
|
3
|
2
|
4
|
-3
|
4
|
3
|
3
|
-4
|
The size of these 3-tuples B[0..t, 1..3] where t= no. of non-zero elements, which 4 in the above matrix. The no. of columns of 3-tuples is always fixed as 3. Hence it is called as 3-tuples. The no. of rows in 3-tuples is equal to no. of non-zero elements of the sparse matrix + 1. Here
B[0,1]= No. of rows of the sparse matrix.
B[0,2]= No. of column of the sparse matrix
B[0,3]= No. of non-zero elements of the sparse matrix
B[i,1] represents row position of the non-zero element (where i=1..t)
B[i,2] represents column position of the non-zero element (where i=1..t)
B[i,3] represents actual non-zero elements in the matrix.
4 0 1 0 0 0
B= 0 0 0 0 0 9
0 7 0 0 0 1
0 0 12 0 0 0
0 0 1 0 5 0
0 24 0 6 0 0
B
|
Row
|
Column
|
value
|
0
|
6
|
6
|
10
|
1
|
1
|
1
|
4
|
2
|
1
|
3
|
1
|
3
|
2
|
6
|
9
|
4
|
3
|
2
|
7
|
5
|
3
|
6
|
1
|
6
|
4
|
3
|
12
|
7
|
5
|
3
|
1
|
8
|
5
|
5
|
5
|
9
|
6
|
2
|
24
|
10
|
6
|
4
|
6
|
Thanx a TON sir..:)
ReplyDelete