Sparse Matrix Representation and Operations

Sparse Matrix Representation and Operations

6 mins read814 Views Comment
Vikram
Vikram Singh
Assistant Manager - Content
Updated on Apr 12, 2024 10:40 IST

Matrix types having most of their elements set to zero are called sparse matrices. In other terms, the definition of a sparse matrix is one in which the number of 0 entries is greater than the number of non-zero elements.

2023_02_MicrosoftTeams-image-281.jpg

This article will discuss a sparse matrix and its representation in arrays and linked lists. We will also talk about various operations performed on sparse matrices. 

What is a Sparse matrix?

A sparse matrix is defined as a 2-D matrix representing the total values of m x n and is composed of n columns and m rows. A matrix is referred to as sparse if the majority of its elements have a value of 0.

The use of a sparse matrix over a basic matrix is executed as

  • Storage: Since fewer non-zero elements exist than zeroes, fewer elements can be stored in a given amount of memory.
  • Computing time: By logically creating a data structure that only traverses non-zero components, computation time can be minimized.

The basic representation of a sparse matrix is given below:

The figure shows the basic representation of a sparse matrix.

Representation of Sparse Matrix

The triplets—columns, rows, and values—can be used to store the non-zero elements of a sparse matrix. The following list includes two ways to express the sparse matrix:

  • Array representation
  • Linked list representation

Array Representation of Sparse Matrix

It wastes a lot of memory to represent a sparse matrix using a 2D array. This is due to the fact that 0s in a matrix are useless, making it wasteful to store them with non-zero elements. We can only keep non-zero elements to prevent this kind of waste. The storage space and traversal time decrease if we save non-zero elements.

There are basically 3 fields utilized in the 2D array form of the sparse matrix, and they are as follows:

  • Row: The index of the row in the matrix where a non-zero component is present.
  • Column: It is defined as the index of the matrix column containing the non-0 element.
  • Value: It refers to the non-0 value element at the index.
The figure shows a node structure.

Let’s use the example below to illustrate how an array represents a sparse matrix:

The figure shows an image related to sparse matrix.

A 5×4 sparse matrix with 7 non-zero along with 13 – zero elements can be seen in the image above. The above matrix requires 5×4 = 20 bytes of memory. The wastage of space will rise as the matrix size increases.

The representation of the matrix in tabular form will be:

The figure shows sparse matrix in a tabular format.

The first column in the above picture denotes the rows, and the 2nd and the 3rd columns will be the non-zero values. These triplets are shown in the table’s first row. The initial triplet indicates that value four is kept in the first column and the first row. Similar to the first triplet, the second shows that value 5 is kept in the first row and third column. The triplets will represent the non-zero matrix elements’ stored locations similarly.

The total non-zero items in the specified sparse matrix define the table size. The memory space required by the above table, 8×3 = 24, is greater than that required by a sparse matrix.

Let us see the code below to understand the array representation of a sparse matrix better:


 
#include < stdio.h > int main()
{ int sparse [4][5] = {
{0 , 0 , 6 , 0 , 9 },
{0 , 0 , 4 , 6 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 1 , 2 , 0 , 0 }
};
int s = 0;
for(int x=0; x < 4; x++)
{
for(int y=0; y < 5; y++)
{
if(sparse[x][y]!=0)
{
s++;
}
}
}
int matrix[3][s];
int z=0;
for(int x=0; x < 4; x++)
{
for(int y=0; y < 5; y++)
{
if(sparse[ix] [y]!=0)
{
matrix[0][z] = x;
matrix[1][z] = y;
matrix[2][z] = sparse[x] [y];
z++;
}
}
}
for(int x=0 ;x < 3; x++)
{
for(int y=0; y < s; y++)
{
printf(%d “, matrix[x] [y]);
printf(“ ”);
}
printf(“ ”);
}
return 0;
}
Copy code

 

The output of the above code will be:

0 0 1 1 3 32 4 2 3 1 2 6 9 4 6 1 2 

Linked List Representation of Sparse Matrix

The sparse matrix represented by a linked list provides the benefit of using a linked list instead of an array for representing a sparse matrix is that it’s simpler to add or remove nodes from a linked list than from an array.

A node present in the representation of a sparse matrix via a linked list has four fields as opposed to three in the array representation. The linked list’s four fields are listed as follows:

  • Row: It depicts the representation of the position of the non-zero elements in the row at the specified index.
  • Column: It serves as a placeholder for the non-zero element’s column index.
  • Value: This term refers to the non-zero element at the index (row as well as column).
  • Next node: It is defined as the address of the following node once it is stored.
The figure shows a node structure.

 
class Node {
int rx;
int cx;
int valx;
Node next;
Node(int r, int c, int val)
{ rx = r; cx = c; this.valx = val; }
}
public class Sp{
public static void main(String[] args)
{
int sparseMatrix[][] = {
{0, 0, 1, 2},
{3, 0, 0, 0},
{0, 4, 5, 0},
{0, 6, 0, 0}
};
Node s = null;
Node tail = null;
int k = 0;
for (int x = 0; x < 4; x++)
for (int y = 0; y < 4; y++)
{
if (sparseMatrix[x][y] != 0)
{
Node temp = new Node(x, y, sparseMatrix[x][y]);
temp.next = null;
if(s == null){
s = temp;
tail=temp;
}
else{
tail.next = temp;
tail = tail.next;
}
}
}
Node itr = s;
while(s != null){
System.out.println(s.rx + ” ” + s.cx + ” ” + s.valx); s = s.next;
} } }
Copy code

 

The output of the above code will be:

0 2 10 3 2 1 0 32 1 42 2 53 1 6

The node is represented by each row in the output. In each row, the first element denotes the non-zero element’s row index location, the second element denotes its column index location, and the 3rd element denotes the actual non-zero element.

Operations on Sparse Matrix

Addition

In order to combine the matrices, a user can simply go over each element of each matrix, one at a time, and insert the smaller element—the one with the smaller row and column values—into the resulting matrix. If an element has the same column and row values as another element, we add their values and insert the new data into the final matrix.

Transpose

To make our comparisons easier and keep the sorted order, firstly calculate the transpose of the 2nd matrix before multiplying the matrices. In order to obtain the resultant matrix, the length of both matrices must be traversed, and the relevant multiplied values must be added.

Any row in the 1st matrix with a value equal to x and any row in the 2nd matrix (the transposed one) with a value equal to y will contribute to the result[x][y]. The result [x][y] is derived by multiplying all elements with col values in both matrices and only adding those with row values of x in the original matrix and y in the 2nd transposed matrix.

Multiplication

To make our comparisons easier and keep the sorted order, we first calculate the transpose of the 2nd matrix before multiplying the matrices. In order to obtain the resultant matrix, the length of matrices must be traversed, and the relevant multiplied values must be added.

All About Skew Symmetric Matrix
All About Skew Symmetric Matrix
A skew-symmetric matrix is a square matrix whose transpose is equal to its negative. In other words, it is a matrix that satisfies the condition A^T = -A. This type...read more

All about Symmetric Matrix
All about Symmetric Matrix
A matrix is a rectangular arrangement of numbers (real or complex) or symbols arranged in rows and columns. The number in the matrix are called the elements, and if the...read more

Matrix Multiplication in C
Matrix Multiplication in C
A matrix is a collection of numbers organized in rows and columns. Matrices can be manipulated using operations like Addition, Subtraction, and Multiplication. Multiplying two matrices is only possible when...read more

Types of Matrix
Types of Matrix
In Linear Algebra, Matrices are one of the most important topics of mathematics. The application of matrix is not just limited to mathematical solving problems; it has its applications across...read more

Adjacency Matrix For Graphs
Adjacency Matrix For Graphs
An Adjacency Matrix is a method of representing graphs in matrix form. The adjacency matrix plays a vital role in describing finite graphs, making them easier to understand and compact...read more

Lower Triangular Matrix: Definition, Example, and Properties
Lower Triangular Matrix: Definition, Example, and Properties
Discover the essentials of lower triangular matrices in linear algebra. Explore their unique properties, practical applications in solving linear systems, and their significance in mathematical computations. Perfect for students and...read more

Transpose of a Matrix
Transpose of a Matrix
Transpose of a matrix is a matrix flipped over its main diagonal, switching the matrix’s rows and column indices. In this article, we will briefly discuss what transpose of a...read more

Confusion Matrix in Machine Learning
Confusion Matrix in Machine Learning
Are you tired of your AI models getting confused? Untangle their mysteries with the Confusion Matrix, your secret weapon for accuracy! Decode True Positives, False Negatives, and more to uncover...read more

Diagonal Matrix: Definition, Example, and Properties
Diagonal Matrix: Definition, Example, and Properties
A diagonal matrix is a special type of square matrix in which all non-diagonal entries are equal to zero, but all diagonal entries can either be zero or non-zero. This...read more

Identity Matrix: Definition, Examples, and Properties
Identity Matrix: Definition, Examples, and Properties
A square matrix of order n x n with ones on the main diagonal and zeros elsewhere is known as an Identity Matrix. From solving a system of linear equations...read more

Why, How, and When to Adopt a Matrix Organizational Structure
Why, How, and When to Adopt a Matrix Organizational Structure
Discover the meaning, types, advantages and disadvantages of the matrix organizational structure. This article delves into its real-world applications, guiding you through adoption steps, potential pitfalls, and when it's best...read more

Matrix Multiplication: A Beginner’s Guide to Understand and Implement
Matrix Multiplication: A Beginner’s Guide to Understand and Implement
Matrix multiplication is a binary operation whose output is also a binary operation. If A and B are two matrices of order m x n and n x p, then the order of the output matrix will...read more

Upper Triangular Matrix: Definition, Example, and Properties
Upper Triangular Matrix: Definition, Example, and Properties
Explore the world of upper triangular matrices in our comprehensive guide. Understand their definition, properties, and practical applications in solving linear equations and beyond. Dive into the role of these...read more

How to Calculate the Determinant of a Matrix?
How to Calculate the Determinant of a Matrix?
The determinant of a matrix is a scalar value that is calculated from the elements of the Square matrix. It is used to determine whether a given matrix is invertible...read more

Conclusion

In this article, we have discussed sparse matrixes in detail. A sparse matrix is a 2-D matrix representing the total values of m x n and is composed of n columns and m rows. We have discussed how to represent a sparse matrix using arrays and linked lists, as well as various operations performed on sparse matrixes. 

About the Author
author-image
Vikram Singh
Assistant Manager - Content

Vikram has a Postgraduate degree in Applied Mathematics, with a keen interest in Data Science and Machine Learning. He has experience of 2+ years in content creation in Mathematics, Statistics, Data Science, and Mac... Read Full Bio