In this article, we will learn about Sparse matrix, its use and its different representation.

## What is a sparse matrix?

A matrix can be defined with a 2-dimensional array with column **m** and row **n** represented as **m * n** matrix. However, there may be a matrix or matrices that may contain less **Non-Zero** values than **Zero** values. Such a matrix is known as the Sparse matrix.

We can say that it is a matrix that contains a few **Non-Zero** elements.

**Why** **use Sparse Matrix instead of a simple** **matrix?**

There are mainly two reasons:

**Storage**: Sparse matrix allows us to use the memory to store only non-zero elements. So, less storage is required.**Computing time**: designing a data- structure that traverses only Non-Zero elements, computing time can be saved.

**Sparse Matrix Representation**:

There are two ways to represent a sparse matrix:

- Triplet Representation(Array Representation)
- Linked Representation

### 1. **Triplet Representation(Array Representation)**

It is an array representation where only **Non-Zero** elements are store in three rows named as:

**Row**: This contains an index number for a row where**non-zero**elements are situated.**Column:**This contains an index number for a column where the**non-zero**element is stored.**Value:**These contain all the values of**Non-Zero**elements located at their respective index i.e. rows and columns.

In the above diagram of matrix size 5* 6, there are 5 **non-zero** elements (8, 7, 5, 3, 1). The right-hand side table indicates it’s a sparse matrix with Rows, Columns, and Values. Values are the non-zero elements that are present in their particular row and column. **Eg**. 0th row and 2nd column contain the non-zero element 8 in the sparse matrix. Ans the following shows a similar pattern.

#### Triplet Representation(Array Representation) **using C++**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include<iostream> using namespace std; int main() { // sparse matrix of class 5x6 with 6 non-zero values int sparseMatrix[5][6] = { {0 , 0 , 0 , 0 , 4, 0 }, {0 , 6 , 0 , 0 , 0, 0 }, {0 , 4 , 0 , 0 , 0, 1 }, {0 , 0 , 0 , 0 , 0, 5 }, {0 , 0 , 9 , 0 , 0, 0 } }; // Looking for non-zero values in the sparse matrix int size = 0; for (int row = 0; row < 5; row++){ for (int column = 0; column < 6; column++){ if (sparseMatrix[row][column] != 0){ size++; } } } //result Matrix int resultMat[3][size]; int k = 0; for (int row = 0; row < 5; row++) for (int column = 0; column < 6; column++) if (sparseMatrix[row][column] != 0) { resultMat[0][k] = row; resultMat[1][k] = column; resultMat[2][k] = sparseMatrix[row][column]; k++; } // Displaying result cout<<"Triplet Representation of Sparse Matrix : "<<endl; for (int row=0; row<3; row++) { for (int column = 0; column<size; column++) cout<<resultMat[row][column]<<" "; cout<<endl; } return 0; } |

**Output of sparse matrix using C++:**

1 2 3 4 | Triplet Representation of Sparse Matrix : 0 1 2 2 3 4 4 1 1 5 5 2 4 6 4 1 5 9 |

**2. Linked List Representation:**

The Linked list data structure is used to represent a sparse matrix.

Here, each node has four fields and they are:

**Row**: This contains an index number for a row where non-zero elements are situated.**Column:**This contains an index number for a column where a non-zero element is stored.**Value:**These contain all the values of Non-Zero elements located at their respective index i.e. rows and columns.**Next Node:**This contains the address of the next node.

## C Program** **to** **determine if a given matrix is in a sparse matrix or not.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | //(Remainder) Sparse matrix has more zero values than non-zero values. #include <stdio.h> void main () { static int arr[20][20]; int i, j, m, n; int counter = 0; printf("Enter the order of the matix \n"); scanf("%d %d", &m, &n); printf("Enter the matix \n"); for (i = 0; i < m; ++i) { for (j = 0; j < n; ++j) { scanf("%d", &array[i][j]); if (arr[i][j] == 0) { ++counter; } } } if (counter > ((m * n) / 2)) { printf("The given matrix is a sparse matrix \n"); } else printf("The given matrix is not a sparse matrix \n"); printf("Number of zeros is %d", counter); } |

**Output of sparse matrix using C:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | Enter the order of the matix 3 3 Enter the matix 0 2 0 0 5 0 6 0 0 The given matrix is a sparse matrix Number of zeros is 6 |