Sparse Matrix

A 2-dimensional array in programming is often represented by ‘m’ rows and ‘n’ columns, written as m x n matrix.

A data element held in each slot of a matrix is called matrices.

Matrices that contain mostly zero values are called sparse, distinct from matrices where most of the values are non-zero, called dense.
A matrix that has more zero matrices than non-zero matrices, is called a Sparse Matrix.

For example:

0	0	54	0	0
0	22	0	0	0
12	0	0	34	0
0	0	0	0	0
0	0	0	0	78

To understand what is sparse matrix, consider the below matrix for example. It contains 5 rows and 7 columns, with the possibility to hold 35 matrices or elements.

0	0	0	0	0	0	89
0	22	0	0	56	0	0
12	0	34	0	0	0	0
0	0	0	54	0	0	98
0	0	0	0	42	78	0

Of these 35 matrices, only 9 are non-zero elements while 26 are zero. This is an example of a sparse matrix, with 74% sparsity (26/35) and 26% (9/35) density.

Definition:

A sparse matrix is a matrix in which many or most of the elements have a value of zero.
This is in contrast to a dense matrix, where many or most of the elements have a non-zero value.
Sparse matrices are used in specific ways in computer science, and have different data analysis and storage protocols and techniques related to their use.

Representation of Sparse Matrix:

Now to keep track of non-zero elements in a sparse matrix we have 3-tuple method using an array.
Elements of the first row represent the number of rows, columns and non-zero values in the sparse matrix.
Elements of the other rows give information about the location and value of non-zero elements.

Thus, in a sparse matrix there are 3 columns and rows are equal to total no of non zero elements +1