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

Array representation of Sparse Matrix
Linked representation of Sparse Matrix