# Sparse Matrix

Sparse Matrix:

A matrix that has minimum number of non-zero elements is called a sparse matrix i.e. very few elements are sparsely distributed in the matrix.

Example: An array of order 3 x 4 containing sparsely located non-zero elements.

 0 1 2 3 0 0 25 0 7 1 0 0 2 8 2 0 0 1 0

(Order 3 x 4)

In the above example, out of 12 elements only 5 elements contain non zero values.  Such a matrix is called sparse matrix.

Representation of Sparse Matrix:

• 3-Tuple Representation
• List Representation

1.  3-Tuple Representation: An array of three columns is required.  The size of the array is the number of non-zero elements plus one.  First row is called the header row that contains total number of rows, total number of columns and non-zero element’s value i.e.

Header Row:    Row    |      Column     |     Element

 rows columns Elements (non zero) 0 3 4 5 1 0 1 25 2 0 3 7 3 1 2 2 4 1 3 8 5 2 2 1

Sparse Matrix representation for the array given above

Number of rows:  3

Number of columns:  4

Number of elements:  5

Order of Sparse Matrix = (5+1) x 3 = 6 x 3.

2.  List Representation:  Each row is converted to a node in linked representation where each node contains, row subscripts, column subscript and non-zero element.  The first node returns the total number of rows, columns and elements.

Example:

3|4|5 -> 0|1|25 -> 0|3|7 -> 1|2|2 -> 1|3|8 -> 2|2|1 -> NULL