Sparse Matrix
MCA, CS-04 2001 (June)
Q.1 (a). What is sparse matrix? Give example. [12]
Ans. Matrices with a relatively high proportion of zero entries are called sparse matrices. Two general types of n-square sparse matrices which will occur in various applications are pictured in Figure.
The first matrix, all entries above the main diagonal are zero or equivalent, where none-zero entries can only occur on or below the main diagonal is called a lower triangular matrix.
The second matrix, where non-zero entries can only occur on the diagonal or on elements immediately above or below the diagonal is called a tridiagonal matrix.
The first matrix, all entries above the main diagonal are zero or equivalent, where none-zero entries can only occur on or below the main diagonal is called a lower triangular matrix.
The second matrix, where non-zero entries can only occur on the diagonal or on elements immediately above or below the diagonal is called a tridiagonal matrix.
Fig: 1
Fig:2
One may save space by storing only those entries which may be non-zero.
In space array indices are permitted for a larger set, but those values actually added to the array consume memory. Thus the program can ask for Sparse Array [5] or Sparse Array [200], but the memory be allocated for only a small number of entries.
Example: Suppose we want to place in memory the triangular array B in first Figure. We store only those entries of B in linear array C as indicated by arrows i.e. C[1]=b11, C[2]=b21, C[3]=b22, C[4]=b41, ….
C will contain only 1+2+3+ …+ n = n(n+1)/2 elements, which is about half as many elements as a two-dimensional h x n array.
L is integer in terms of J and K, Where C[L]=bjk, L represents the number of elements in the list upto and including bjk. There are
1+2+3+…+(J-1)=J(J-1)/2 elements in rows above bjk, K elements in row J upto and including bjk. Accordingly, L = J(J-1)/2+K yields the index that accesses the value bjk from linear array C.
In space array indices are permitted for a larger set, but those values actually added to the array consume memory. Thus the program can ask for Sparse Array [5] or Sparse Array [200], but the memory be allocated for only a small number of entries.
Example: Suppose we want to place in memory the triangular array B in first Figure. We store only those entries of B in linear array C as indicated by arrows i.e. C[1]=b11, C[2]=b21, C[3]=b22, C[4]=b41, ….
C will contain only 1+2+3+ …+ n = n(n+1)/2 elements, which is about half as many elements as a two-dimensional h x n array.
L is integer in terms of J and K, Where C[L]=bjk, L represents the number of elements in the list upto and including bjk. There are
1+2+3+…+(J-1)=J(J-1)/2 elements in rows above bjk, K elements in row J upto and including bjk. Accordingly, L = J(J-1)/2+K yields the index that accesses the value bjk from linear array C.
