Sparse Matrix Representation in C

Sparse Matrix: A sparse matrix is a matrix with the majority of its elements equal to zero. To identify a sparse matrix, we will check all the elements in the sparse matrix one by one and count the number of 0’s in it if the number of zeros’ is greater than 50% of the total elements then the matrix can be called sparse matrix.

Example of the Sparse Matrix:

Here in this matrix, there are 12 elements in a 4X3 matrix in which there are 9 0’s and 3 1’s total memory consumed by the matrix is equal to 12X4(size of int in the most modern compiler) total memory consumed by the matrix is equal to 48 bytes. But if we only store the non-zero element we can save 9X3 = 27 bytes.

------------------------------------------------------------
-------ROW NUMBER------COLUMN NUMBER------VALUE----
------------------------------------------------------------
            0               0               9 
            2               1               5 
            2               3               8 
            3               0               3 
--------------------------------------------------------------

Write a C program to compress the size of the sparse matrix without losing the information in the sparse matrix.

As we can see the matrix is a 2-dimensional array which means that every element in the sparse matrix is stored in some column of some row. If we can store the values of columns and rows of those non-zeros elements in the matrix and leave all the zero-containing elements we can compress the matrix to some extent.

Algorithm:
1. Traverse the matrix from one element in the matrix to the last element in the matrix.
2. If the element is equal to 0 leave that element.
3. Else store the row number, column number, and the value in the element.
4. Also find the total rows and columns in the matrix and store them.

There are several ways to compress the size of the sparse matrix in C language. Let’s take a detailed look at all the approaches to compress the size of the sparse matrix in C.

• Sparse Matrix Representation in C using a Two-dimensional Array
• Sparse Matrix Representation in C using an Array of Structures
• Sparse Matrix Representation in C using a Linked List

As we have discussed earlier we only need to store the non-zero element in the compressed form of the sparse matrix thus we will first find the number of non-zero elements in the matrix. Then declare a 2-d-array of type int [non-zero-elements][3]. And then we will traverse the sparse matrix and store all the non-zero elements in the 2-d array along with row number and column number.

The data structure used to store the compressed form of the sparse matrix: 2-d array.

Dimensions of the 2-d array are total non-zero elements X 3. 3 is the total columns in the 2-d array to store row number, column number, and non-zero element.

Here is source code of the C program to compress the size of the sparse matrix using two-dimensional array. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * Sparse Matrix Representation in C Using a Two-dimensional Array
 */
 
#include<stdio.h>
int Sparse_Matrix[4][4] =
{
    {9 , 0 , 0 , 0 },
    {0 , 0 , 0 , 0 },
    {0 , 5 , 0 , 8 },
    {3 , 0 , 0 , 0 }
};
int main()
{
    int non_zeros;
 
    // Step 1: Count the number of non-zeros in the sparse matrix.
    for (int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(Sparse_Matrix[i][j] != 0)
            {
                non_zeros++;
            }
        }
    }
 
    // Step 2: Declare the 2-d array to store the compressed sparse matrix.
    int Compressed_Sparse_Matrix[non_zeros][3];
    int temp = 0;
    for (int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(Sparse_Matrix[i][j] != 0)
            {
                Compressed_Sparse_Matrix[temp][0]=i;
                Compressed_Sparse_Matrix[temp][1]=j;
                Compressed_Sparse_Matrix[temp][2]=Sparse_Matrix[i][j];
                temp++;
            }
        }
    }// Sparse matrix is compressed.
 
    printf("------------------------------------------------------------\n");
    printf("-------ROW NUMBER-----------COLUMN NUMBER----------VALUE----\n");
    printf("------------------------------------------------------------\n");
    for (int i=0;i<temp;i++)
    {
        printf("%15d %15d %15d \n",Compressed_Sparse_Matrix[i][0], Compressed_Sparse_Matrix[i][1], 
               Compressed_Sparse_Matrix[i][2]);
    }
    printf("---------------------------------------------------------------- \n");
    // Print the Compressed form of a sparse matrix.
}

1. First count the number of zeros in the sparse matrix.
2. Then declare the 2-d array to store the compressed sparse matrix with rows equal to counted non-zero elements and columns equal to 3.
3. After that store the row number column number and value of the non-0 element in the compressed form of the sparse matrix.

Time Complexity: O(rows * columns)
The time complexity of sparse matrix representation is O(rows * columns).

Space Complexity: O(rows * columns + non-zero elements * 3)
The time complexity of sparse matrix representation is O(rows * columns + non-zero elements * 3).

In this case, we are compressing the size of the sparse matrix without losing the information in the sparse matrix.

------------------------------------------------------------
-------ROW NUMBER------COLUMN NUMBER------VALUE----
------------------------------------------------------------
            0               0               9 
            2               1               5 
            2               3               8 
            3               0               3 
--------------------------------------------------------------

An array of structures is the array of structures. Here structure holds the information of the non-zero elements and we use an array of structures because there are multiple non-zero elements in the sparse matrix.

The structure to hold the information of the non-zero elements of the sparse matrix is:-

Algorithm:
1. Declare a structure that can hold the values of row number(int type), column number (int type), and non-zero number (int type).
2. Declare a variable count = 0.
3. Traverse the matrix from one element in the matrix to the last element in the matrix.
4. If the element is equal to 0 leave that element.
5. Else increase the value of count by 1.
6. Declare the array of structures with size = count.
7. Traverse the matrix from one element in the matrix to the last element in the matrix.
8. If the element is equal to 0 leave that element.
9. Else store the value in an array of structures.

Here is source code of the C program to compress the size of the sparse matrix using array of structures. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * Sparse Matrix Representation in C Using an array of structures
 */
 
#include<stdio.h>
#include<stdlib.h>
struct non_zero_values
{
    int row, column, value;
};
int main()
{
    int Sparse_Matrix[4][4] ={ {12 , 0 , 44 , 0 },{0 , 234 , 0 , 0 },{0 , 1 , 0 , 8 },{0 , 0 , 0 , 0 } };
    int count = 0 ;
 
    // Increase the
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(Sparse_Matrix[i][j] != 0)
            {
                count++;
            }
        }
    }
    struct non_zero_values compressed_form[count];
    int temp = 0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(Sparse_Matrix[i][j] != 0)
            {
                compressed_form[temp].row = i;
                compressed_form[temp].column = j;
                compressed_form[temp].value = Sparse_Matrix[i][j];
                temp++;
            }
        }
    }
    // print the Array of structures.
    printf("row number -> column number -> value at sparse[row][column] \n");
    for(int i =0 ;i<count; i++)
    {
        printf("%d %d %d \n",compressed_form[i].row, compressed_form[i].column, 
                compressed_form[i].value);
    }
}

1. At first, count the number of zeros in the sparse matrix.
2. Then declare an array of structures to store the compressed sparse matrix with the size of the array equal to counted non-zero elements and columns equal to 5.
3. Then we store the row number column number and value of the non-zero element in the array of the structure of non-zero elements of the sparse matrix.
4. Finally print the array of structures.

Time Complexity: O(rows * columns)
The time complexity of sparse matrix representation is O(rows * columns).

Space Complexity: O(rows * columns + non-zero elements * 3)
The space complexity of sparse matrix representation is O(rows * columns + non-zero elements * 3).

In this case, we are compressing the size of the sparse matrix without losing the information in the sparse matrix using array.

row number -> column number -> value at sparse[row][column]
0                0               12
0                2               44
1                1               234
2                1               1
2                3               8

A link list is a dynamic data structure i.e its memory size can increase or decrease at run-time. In the previous method, we were forced to provide a size for the 2-d array to store the compressed form of the sparse matrix but in the case of link list, we don’t need to allocate memory in the program instead sufficient memory is being provided whenever a non-zero element in found in the sparse matrix by the runtime environment itself.

Here is source code of the C program to compress the size of the sparse matrix using linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * Sparse Matrix Representation in C Using a Linked List
 */
 
#include<stdio.h>
#include<stdlib.h>
struct list
{
    int row, column, value;
    struct list *next;
};
struct list *HEAD=NULL;
void insert(int, int , int );
void print ();
int main()
{
    int Sparse_Matrix[4][4] ={ {9 , 0 , 0 , 0 },{0 , 0 , 0 , 0 },{0 , 5 , 0 , 8 },{3 , 0 , 0 , 0 } };
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(Sparse_Matrix[i][j] != 0)
            {
                insert(i, j, Sparse_Matrix[i][j]);
            }
        }
    }
    // print the linked list.
    print();
}
void insert( int r, int c, int v)
{
    struct list *ptr,*temp;
    int item;
    ptr = (struct list *)malloc(sizeof(struct list));
    if(ptr == NULL)
    {
        printf("\n OVERFLOW");
    }
    else
    {
        ptr->row = r;
        ptr->column = c;
        ptr->value = v;
        if(HEAD == NULL)
        {
            ptr->next = NULL;
            HEAD = ptr;
        }
        else
        {
            temp = HEAD;
            while (temp -> next != NULL)
            {
                temp = temp -> next;
            }
            temp->next = ptr;
            ptr->next = NULL;
        }
    }
}
void print()
{
    struct list *tmp = HEAD;
    printf("ROW NO      COLUMN NO.        VALUE \n");
    while (tmp != NULL)
    {
        printf("%d \t\t %d \t\t %d \n", tmp->row, tmp->column, tmp->value);
        tmp = tmp->next;
    }
}

1. Iterate the sparse matrix.
2. Find the non-zero element and store their row number column number and value at that row and column in the link list.
3. Print the value.

Time Complexity: O(rows * columns *non-zero elements)
Iterate the sparse matrix that takes the O(rows * columns) time complexity and we also insert a non-zero element in the list which takes linear time, thus our time complexity comes out to be O(rows * columns *non-zero elements), we can also optimize the time complexity of inserting an element to constant time by making a pointer that always points to the end of the link list.

Space Complexity: O(rows * columns + non-zero elments)
The space complexity of sparse matrix representation is O(rows * columns + non-zero elments).

In this case, we are compressing the size of the sparse matrix without losing the information in the sparse matrix using linked list.

 
ROW NO      COLUMN NO.        VALUE
0                0               9
2                1               5
2                3               8
3                0               3

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.