Simple2Code

Introduction to Sparse Matrix in Data Structure

Written by

admin

in

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

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

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.

//(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:

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

More posts