Matrix with a relatively high proportion of zero entries are called sparse matrix. There are three types of sparse matrices:

__LOWER TRIANGULAR MATRIX:__

__UPPER TRIANGULAR MATRIX:__

In the upper triangular matrix all the entries below the matrix diagonal are zero.

__TRIDIAGONAL MATRIX:__

In the tridiagonal matrix the non-zero entries can occur only on the diagonal or immediately above or below the diagonal.

These incident and adjacency matrix represenation of graphs will usually results in these type of sparse matrices.

If we use the conventional 2D array representation to store the above matrix there will be wastage of storage spaces. So an alternative representation is needed for sparse matrix. It is possible to store information regarding non-zero elements.

- Integer representing its row.
- Integer representing its column
- The data associated with the element.

That is, we can store the matrix as a list of three tuples of the form (i, j, value)

E.g. consider the matrix

The repesetation is as follows

Row column value

A[0 ] 5 5 15

A[1] 0 0 4

A[2] 1 0 3

A[3] 1 1 2

A[4] 2 0 -1

A[5] 2 1 1

A[6] 2 2 6

A[7] 3 0 5

A[8] 3 1 -2

A[9] 3 2 2

A[10] 3 3 3

A[11] 4 0 6

A[12] 4 1 2

A[13] 4 2 3

A[14] 4 3 4

A[15] 4 4 4

## Comments

## Post a Comment