Sparse MatrixA matrix can be defined as a twodimensional array having 'm' columns and 'n' rows representing m*n matrix. Sparse matrices are those matrices that have the majority of their elements equal to zero. In other words, the sparse matrix can be defined as the matrix that has a greater number of zero elements than the nonzero elements. Why do we need to use a sparse matrix instead of a simple matrix? We can also use the simple matrix to store the elements in the memory; then why do we need to use the sparse matrix. The following are the advantages of using a sparse matrix:
Representing a sparse matrix by a 2D array leads to the wastage of lots of memory. The zeroes in the matrix are of no use to store zeroes with nonzero elements. To avoid such wastage, we can store only nonzero elements. If we store only nonzero elements, it reduces the traversal time and the storage space. Sparse Matrix RepresentationThe nonzero elements can be stored with triples, i.e., rows, columns, and value. The sparse matrix can be represented in the following ways:
Array Representation The 2d array can be used to represent a sparse matrix in which there are three rows named as:
Let's understand the sparse matrix using array representation through an example. As we can observe above, that sparse matrix is represented using triplets, i.e., row, column, and value. In the above sparse matrix, there are 13 zero elements and 7 nonzero elements. This sparse matrix occupies 5*4 = 20 memory space. If the size of the sparse matrix is increased, then the wastage of memory space will also be increased. The above sparse matrix can be represented in the tabular form shown as below: In the above table structure, the first column is representing the row number, the second column is representing the column number and third column represents the nonzero value at index(row, column). The size of the table depends upon the number of nonzero elements in the sparse matrix. The above table occupies (7 * 3) = 21 but it more than the sparse matrix. Consider the case if the matrix is 8*8 and there are only 8 nonzero elements in the matrix then the space occupied by the sparse matrix would be 8*8 = 64 whereas, the space occupied by the table represented using triplets would be 8*3 = 24. In the 0^{th} row and 1^{nd} column, 4 value is available. In the 0^{th} row and 3^{rd} column, value 5 is stored. In the 1^{st} row and 2^{nd} column, value 3 is stored. In the 1^{st} row and 3^{rd} column, value 6 is stored. In 2^{nd} row and 2^{nd} column, value 2 is stored. In the 3^{rd} row and 0^{th} column, value 2 is stored. In the 3^{rd} row and 1^{st} column, value 3 is stored. Array implementation of sparse matrix in C Output Linked List RepresentationIn linked list representation, linked list data structure is used to represent a sparse matrix. In linked list representation, each node consists of four fields whereas, in array representation, there are three fields, i.e., row, column, and value. The following are the fields in the linked list:
Let's understand the sparse matrix using linked list representation through an example. In the above figure, sparse represented in the linked list form. In the node, first field represents the index of row, second field represents the index of column, third field represents the value and fourth field contains the address of the next node.
Next TopicDetect loop in a Linked list
