Sparse Matrix Representation and Operations
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.
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:
Best-suited Maths for Data Science courses for you
Learn Maths for Data Science with these high-rated online courses
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.
Let’s use the example below to illustrate how an array represents a 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 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; }
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.
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; } } }
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.
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.
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
Top Picks & New Arrivals
