Introduction to Sparse Matrix in Data Structure

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:

  1. Storage: Sparse matrix allows us to use the memory to store only non-zero elements. So, less storage is required.
  2. 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:

  1. Triplet Representation(Array Representation)
  2. 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.
Sparse matrix

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++

Output of sparse matrix using C++:


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.

Output of sparse matrix using C:

Java program for Sparse Matrix Representation using array