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.

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]=b₁₁, C[2]=b₂₁, C[3]=b₂₂, C[4]=b₄₁, ….

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]=b_jk, L represents the number of elements in the list upto and including b_jk. There are

1+2+3+…+(J-1)=J(J-1)/2 elements in rows above b_jk, K elements in row J upto and including b_jk. Accordingly, L = J(J-1)/2+K yields the index that accesses the value b_jk from linear array C.