Scribd
Upload
2 views

Sparse Matrix

A sparse matrix is a matrix predominantly filled with zero values, making traditional 2D array representation inefficient in terms of space and computation time. Sparse matrices can be represented using two methods: Triplet Representation, which stores non-zero values along with their indices, and Linked Representation, which uses nodes to store non-zero elements and their indices. Each representation has its advantages, with array representation being better for frequent access and linked representation being more efficient for insertion and deletion operations.

Uploaded by

temp.sonadi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views

Sparse Matrix

A sparse matrix is a matrix predominantly filled with zero values, making traditional 2D array representation inefficient in terms of space and computation time. Sparse matrices can be represented using two methods: Triplet Representation, which stores non-zero values along with their indices, and Linked Representation, which uses nodes to store non-zero elements and their indices. Each representation has its advantages, with array representation being better for frequent access and linked representation being more efficient for insertion and deletion operations.

Uploaded by

temp.sonadi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Topic: Sparse Matrix and its representations

What is Sparse Matrix?

In computer programming, a matrix can be defined with a 2-dimensional array. Any array with 'm' columns and
'n' rows represent a m X n matrix. There may be a situation in which a matrix contains more number of ZERO
values than NON-ZERO values. Such matrix is known as sparse matrix.

When a sparse matrix is represented with a 2-dimensional array, we waste a lot of space to represent that matrix.
For example, consider a matrix of size 100 X 100 containing only 10 non-zero elements. In this matrix, only 10
spaces are filled with non-zero values and remaining spaces of the matrix are filled with zero. That means, totally
we allocate 100 X 100 X 2 = 20000 bytes of space to store this integer matrix. And to access these 10 non-zero
elements we have to make scanning for 10000 times. To make it simple we use the following sparse matrix
representation.

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.

Sparse Matrix Representations

A sparse matrix can be represented by using TWO representations, those are as follows...

1. Triplet Representation (Array Representation)


2. Linked Representation

1. Triplet Representation (Array Representation)

In this representation, we consider only non-zero values along with their row and column index values. In this
representation, the 0th row stores the total number of rows, total number of columns and the total number of
non-zero values in the sparse matrix.

Example: - consider a matrix of size 5 X 6 containing 6 number of non-zero values. This matrix can be represented
as shown in the image...

In above example matrix, there are only 6 non-zero elements (those are 9, 8, 4, 2, 5 & 2) and matrix size is 5 X 6.
We represent this matrix as shown in the above image. Here the first row in the right side table is filled with values
5, 6 & 6 which indicates that it is a sparse matrix with 5 rows, 6 columns & 6 non-zero values. The second row is
filled with 0, 4, & 9 which indicates the non-zero value 9 is at the 0th-row 4th column in the sparse matrix. In the
same way, the remaining non-zero values also follow a similar pattern.

1|Page
2. Linked Representation

This type of representation is similar to array representation in storing row, column index, and value of the non-
zero elements.

Step 1: List the non-zero elements in the matrix with their row and column index.

Step 2: Create new nodes with the above-given structure and put values of row and column index and the value
of the non-zero elements.

Step 3: Point the next pointer of the elements to the next element to form the linked list.

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:

Example:-

Advantages of Array representation

Array representation is helpful when access operations are more frequent because elements in the array list can
be accessed on the basis of their indexes. Thus it is easier to access an element in an array list as compared to
linked list.

Advantages of linked list representation:

Linked list representation is helpful when insertion and deletion operations are more frequent because the
complexity of inserting and deleting a node in linked list is very less than array.
References: You may read more from following links: http://www.btechsmartclass.com/data_structures/sparse-matrix.html
https://www.scaler.com/topics/data-structures/sparse-matrix-in-data-structure/
https://www.educba.com/sparse-matrix-in-data-structure/; https://techvidvan.com/tutorials/sparse-matrix-in-data-structure/

2|Page

You might also like