Sparse Matrix in Data Structure

In programming, we usually represent a 2-D array in the form of a matrix. However, if a matrix has most of its elements equal to zero, then the matrix is known as a sparse matrix. In the case of a sparse matrix, we don’t store the zeros in the memory to reduce memory usage and make it more efficient. We only store the non-zero values of the sparse matrix inside the memory.

For example, in the following 5*4 matrix, most of the numbers are zero. Only a few elements are non-zero which makes it a sparse matrix.

Thus, a sparse matrix is a matrix in which the number of zeros is more than the number of non-zero elements. If we store this sparse matrix as it is, it will consume a lot of space. Therefore, we store only non-zero values in the memory in a more efficient way.

Why Sparse Matrix:

There are mainly two reasons for using sparse matrices. These are:

1. Computation time: If we store the sparse matrix in a memory-efficient manner, we can save a lot of computational time to perform operations on the matrix.

2. Storage: When we store only non-zero elements, we can save a lot of memory/space that we can use for storing other data structures or performing other operations.

Memory Representation of Sparse Matrix:

There are two types of representations for sparse matrices. These are based on the type of data structure used to store the sparse matrix. Based on this, the representations are:

1. Array representation
2. Linked list representation

Array Representation:

In an array representation, we make use of arrays to store a sparse matrix. The sparse matrix is stored in a 2-D array having three rows as follows:

1. Row: It stores the index of the row, where we have a non-zero element in the sparse matrix.

2. Column: It stores the index of the column, where we have the non-zero element in the sparse matrix.

3. Value: This variable consists of the actual non-zero value being stored.

For example, the following diagram shows how we can represent a sparse matrix with the help of an array by storing only non-zero elements in the array along with their row number and column number.

Linked List Representation:

A linked list is a combination of interconnected rows joined in a linear manner. In linked list representation, each node consists of four components:

1. Row: It stores the index of the row, where we have a non-zero element in the sparse matrix.

2. Column: It stores the index of the column, where we have the non-zero element in the sparse matrix.

3. Value: This variable consists of the actual non-zero value being stored.

4. Next node: It is a pointer to store the address of the next connected node.

Thus, we can represent the node as follows:

In the following diagram, we can see the linked list representation of a sparse matrix.

Array Implementation in C:

int main()
{
  int sparse_matrix[5][4] =
  {
    {0, 0, 3, 0},
    {0, 0, 5, 7},
    {0, 0, 0, 0},
    {0, 2, 6, 0},
    {4, 0, 0, 0}
  };

  int size = 0;
  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 4; j++)
      if (sparse_matrix[i][j] != 0)
        size++;

  int new_matrix[3][size];
  int k = 0;
  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 4; j++)
      if (sparse_matrix[i][j] != 0)
      {
        new_matrix[0][k] = i;
        new_matrix[1][k] = j;
        new_matrix[2][k] = sparse_matrix[i][j];
        k++;
      }
  for (int i=0; i<3; i++)
  {
    for (int j=0; j<size; j++)
      printf("%d ", new_matrix[i][j]);
    printf("\n");
  }
  return 0;
}

Output:

Array Implementation in C++:

#include<bits/stdc++o.h>

int main()
{
  int sparse_matrix[5][4] =
  {
    {0, 0, 3, 0},
    {0, 0, 5, 7},
    {0, 0, 0, 0},
    {0, 2, 6, 0},
    {4, 0, 0, 0}
  };

  int size = 0;
  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 4; j++)
      if (sparse_matrix[i][j] != 0)
        size++;

  int new_matrix[3][size];
  int k = 0;
  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 4; j++)
      if (sparse_matrix[i][j] != 0)
      {
        new_matrix[0][k] = i;
        new_matrix[1][k] = j;
        new_matrix[2][k] = sparse_matrix[i][j];
        k++;
      }
  for (int i=0; i<3; i++)
  {
    for (int j=0; j<size; j++)
      cout << new_matrix[i][j];
    cout << endl;
  }
  return 0;
}

Output:

Array Implementation in Java:

class TechVidvan
{

  public static void main(String[] args)
  {
    int sparse_matrix[][]
        = {
          {0, 0, 3, 0},
               			{0, 0, 5, 7},
                		{0, 0, 0, 0},
                		{0, 2, 6, 0},
               			 {4, 0, 0, 0}
        };

    int size = 0;
    for (int i = 0; i < 5; i++)
    {
      for (int j = 0; j < 4; j++)
      {
        if (sparse_matrix[i][j] != 0)
          size++;
      }
    }

    int new_matrix[][] = new int[3][size];
    int k = 0;
    for (int i = 0; i < 4; i++)
    {
      for (int j = 0; j < 5; j++)
      {
        if (sparse_matrix[i][j] != 0)
        {
          new_matrix[0][k] = i;
          new_matrix[1][k] = j;
          new_matrix[2][k] = sparse_matrix[i][j];
          k++;
        }
      }
    }

    for (int i = 0; i < 3; i++)
    {
      for (int j = 0; j < size; j++)
      {
        System.out.print("%d ", new_matrix[i][j]);
      }
      System.out.print("\n");
    }
  }
}

Output:

Array Implementation in Python:

sparse_matrix = [[0,0,3,0],[0,0,5,7],[0,0,0,0],[0,2,6,0],[4,0,0,0]]

size = 0

for i in range(5):
  for j in range(4):
    if (sparse_matrix[i][j] != 0):
      size += 1


rows, cols = (3, size)
new_matrix = [[0 for i in range(cols)] for j in range(rows)]

k = 0
for i in range(5):
  for j in range(4):
    if (sparse_matrix[i][j] != 0):
      new_matrix[0][k] = i
      new_matrix[1][k] = j
      new_matrix[2][k] = sparse_matrix[i][j]
      k += 1

for i in new_matrix:
  print(i)

Output:

Linked List Implementation in C:

#include<stdio.h>
#include<stdlib.h>

struct Node
{
  int key;
  int row_position;
  int col_postion;
  struct Node *Next;
};

void create_new_node(struct Node** head, int non_zero_element,
          int row_index, int col_index )
{
  struct Node *temp, *r;
  temp = *head;
  if (temp == NULL)
  {
    temp = (struct Node *) malloc (sizeof(struct Node));
    temp->key = non_zero_element;
    temp->row_position = row_index;
    temp->col_postion = col_index;
    temp->Next = NULL;
    *head = temp;

  }
  else
  {
    while (temp->Next != NULL)
      temp = temp->Next;
    r = (struct Node *) malloc (sizeof(struct Node));
    r->key = non_zero_element;
    r->row_position = row_index;
    r->col_postion = col_index;
    r->Next = NULL;
    temp->Next = r;

  }
}

void Print_list(struct Node* head)
{
  struct Node *temp, *r, *s;
  temp = r = s = head;

  printf("row_position: ");
  while(temp != NULL)
  {

    printf("%d ", temp->row_position);
    temp = temp->Next;
  }
  printf("\n");

  printf("col_postion: ");
  while(r != NULL)
  {
    printf("%d ", r->col_postion);
    r = r->Next;
  }
  printf("\n");
  printf("Value: ");
  while(s != NULL)
  {
    printf("%d ", s->key);
    s = s->Next;
  }
  printf("\n");
}

int main()
{
  int sparse_matric[5][4] =
  {
    {0, 0, 3, 0},
    {0, 0, 5, 7},
    {0, 0, 0, 0},
    {0, 2, 6, 0},
    {4, 0, 0, 0}
  };

  struct Node* start = NULL;

  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 4; j++)
      if (sparse_matric[i][j] != 0)
        create_new_node(&head, sparse_matric[i][j], i, j);

  Print_list(head);

  return 0;
}

Linked List Implementation in C++:

#include<bits/stdc++.h>

struct Node
{
  int key;
  int row_position;
  int col_postion;
  struct Node *Next;
};

void create_new_node(struct Node** head, int non_zero_element,
          int row_index, int col_index )
{
  struct Node *temp, *r;
  temp = *head;
  if (temp == NULL)
  {
    temp = (struct Node *) malloc (sizeof(struct Node));
    temp->key = non_zero_element;
    temp->row_position = row_index;
    temp->col_postion = col_index;
    temp->Next = NULL;
    *head = temp;

  }
  else
  {
    while (temp->Next != NULL)
      temp = temp->Next;
    r = (struct Node *) malloc (sizeof(struct Node));
    r->key = non_zero_element;
    r->row_position = row_index;
    r->col_postion = col_index;
    r->Next = NULL;
    temp->Next = r;

  }
}

void Print_list(struct Node* head)
{
  struct Node *temp, *r, *s;
  temp = r = s = head;

  cout << "row_position: ";
  while(temp != NULL)
  {

    cout << temp->row_position;
    temp = temp->Next;
  }
  cout << endl;

  cout << "col_postion: ";
  while(r != NULL)
  {
    cout << r->col_postion;
    r = r->Next;
  }
  cout << endl;
  cout << "Value: ";
  while(s != NULL)
  {
    cout << s->key;
    s = s->Next;
  }
  cout << endl;
}

int main()
{
  int sparse_matric[5][4] =
  {
    {0, 0, 3, 0},
    {0, 0, 5, 7},
    {0, 0, 0, 0},
    {0, 2, 6, 0},
    {4, 0, 0, 0}
  };

  struct Node* start = NULL;

  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 4; j++)
      if (sparse_matric[i][j] != 0)
        create_new_node(&head, sparse_matric[i][j], i, j);

  Print_list(head);

  return 0;
}

Output:

Linked List Implementation in Python:

class Node:
  __slots__ = "row", "col", "key", "Next"
  def __init__(self, row=0, col=0, key=0, Next=None):

    self.row = row
    self.col = col
    self.key = key
    self.Next = Next

class Sparse:
  def __init__(self):
    self.head = None
    self.temp = None
    self.size = 0
  def __len__(self):
    return self.size
    
  def is_empty(self):
    return self.size == 0

  def create_new_node(self, row, col, key):
    new_node = Node(row, col, key, None)
    if self.is_empty():
      self.head = new_node
    else:
      self.temp.Next = new_node
    self.temp = new_node
    self.size += 1

  def Print_list(self):
    temp = r = s = self.head
    print("row_position:", end=" ")
    while temp != None:
      print(temp.row, end=" ")
      temp = temp.Next
    print()
    print("col_postion:", end=" ")
    while r != None:
      print(r.col, end=" ")
      r = r.Next
    print()
    print("Value:", end=" ")
    while s != None:
      print(s.key, end=" ")
      s = s.Next
    print()

if __name__ == "__main__":
  s = Sparse()
  sparse_matrix = [[0, 0, 3, 0],
          [0, 0, 5, 7],
          [0, 0, 0, 0],
          [0, 2, 6, 0],
          [4, 0, 0, 0]]
  for i in range(5):
    for j in range(4):
      if sparse_matric[i][j] != 0:
        s.create_new_node(i, j, sparse_matric[i][j])
  s.Print_list()

Output:

Conclusion:

In this article, we have discussed what is a sparse matrix, how do we define it, what is the need for a sparse matrix and how we can implement it in various programming languages. Thus, a sparse matrix is a very beneficial way of representing matrices as it reduces the computational time to a great extent.