Sparse Matrix in C

In this tutorial, we are going to learn about the sparse matrix in C. 

Before we start let us first discuss what a little bit about two-dimensional arrays. A matrix is represented by 2D arrays where the first index represents the number of rows and the second index represents the number of columns in the matrix. An m*n matrix is represented by a 2D array.

arr[m][n]

Sparsity: A matrix is said to be sparse matrix if most of the elements (More than half) elements in the matrix are zero and the number of elements divided by the total number of elements present in the array is called the sparsity of the matrix.

Sparsity = Number of non-zero elements/ Total number of elements

Matrix is sparse if sparsity is less than 0.5 and dense otherwise.

When storing data in the array the zero does not actually represent any information but they are taking space in memory so instead of storing this type of data in the 2D arrays we can store that data in some other format and reduce the overall space required by the program.

Creating table from the sparse matrix : 

Instead of having an array containing zeroes we can actually remove all those zeroes from the array and to can store indices of the elements in the array separately. 

The above array can be converted to a sparse matrix using the following code: 

#include <stdio.h>

int nonZeroElements(int m,int n,int arr[][n])
{
	int i,j;
	int counter = 0;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			if(arr[i][j]!=0)
				counter++;
		}
	}
	
	return counter;
}

void convertIntoSparse(int m,int n,int arr[][n])
{
	int nonZero = nonZeroElements(m,n,arr);
	
	double sparsity = nonZero/16.0;
	int applicable = sparsity <= 0.5;
	
	if(applicable)
	{
		int sparseMatrix[3][nonZero];
		int i,j,counter = 0;
		
		for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
			{
				if(arr[i][j]!=0)
				{
					sparseMatrix[0][counter] = i;
					sparseMatrix[1][counter] = j;
					sparseMatrix[2][counter] = arr[i][j];
					counter++;
				}
			}
		}
		
		printf("The final Sparse Matrix is : \n");
		
		for(i=0;i<nonZero;i++)
		{
			printf("At (%d, %d) value is : %d\n",sparseMatrix[0][i],sparseMatrix[1][i],sparseMatrix[2][i]);
		}
		
	}
	else
	{
		printf("Matrix is not a sparse matrix !!");
	}
	
}

int main(void) {
	
	
	/* 
	int m,n,i,j;
	scannf("%d%d",&m,&n);
	
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			scanf("%d",&arr[i][j]);
		}
	}
	
	*/
	
	int m = 4, n = 4;
	int arr[4][4] = { 
		{4, 0, 1, 0},
		{0, 0, 2, 3},
		{0, 0, 0, 5}
	};
	
	convertIntoSparse(m,n,arr);
	
	return 0;
}

Using a linked list: 

We can also use a linked list for the same purpose. The structure of the linked list will look as below : 

struct node{
	int rows;
	int cols;
	int val;
	struct node* next;
}

All the other operations can be performed similary on the linked list and space can be saved.

Most of the languages nowadays use vector of pairs/structures or list of pairs/structures to store the sparse matrix.