Scribd
Upload
13 views2 pages

Sparse Matrix Representation Explained

A sparse matrix is a two-dimensional matrix predominantly filled with zero values, allowing for efficient storage and computation by only storing non-zero elements. It can be represented using triplets (row, column, value) and can be stored in either array or linked list formats to minimize memory usage. The document discusses the advantages of sparse matrix representation, including reduced memory wastage and improved traversal time.

Uploaded by

alphadaddy9969
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
13 views2 pages

Sparse Matrix Representation Explained

A sparse matrix is a two-dimensional matrix predominantly filled with zero values, allowing for efficient storage and computation by only storing non-zero elements. It can be represented using triplets (row, column, value) and can be stored in either array or linked list formats to minimize memory usage. The document discusses the advantages of sparse matrix representation, including reduced memory wastage and improved traversal time.

Uploaded by

alphadaddy9969
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

Sparse Matrix and its representations

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total
m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.

Use Sparse Matrix instead of simple matrix

Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used
to store only those elements.
Computing time: Computing time can be saved by logically designing a data structure traversing
only non-zero elements..
Example:

00304
00570
00000
02600

Representation of sparse matrix


The non-zero elements in the sparse matrix can be stored using triplets that are rows, columns,
and values.

There are two ways to represent the sparse matrix


Array representation
Linked list representation
Array representation of the sparse matrix

Representing a sparse matrix by a 2D array leads to the wastage of lots of memory. This is
because zeroes in the matrix are of no use, so storing zeroes with non-zero elements is
wastage of memory. To avoid such wastage, we can store only non-zero elements. If we store
only non-zero elements, it reduces the traversal time and the storage space.

In 2D array representation of sparse matrix, there are three fields used that are named as -

Row - It is the index of a row where a non-zero element is located in the matrix.
Column - It is the index of the column where a non-zero element is located in the matrix.
Value - It is the value of the non-zero element that is located at the index (row, column).

Consider the sparse matrix -


In the above figure, we can observe a 5x4 sparse matrix containing 7 non-zero elements and 13
zero elements. The above matrix occupies 5x4 = 20 memory space. Increasing the size of
matrix will increase the wastage space.

he tabular representation of the above matrix is given below -

In the above structure, first column represents the rows, the second column represents
the columns, and the third column represents the non-zero value. The first row of the
table represents the triplets. The first triplet represents that the value 4 is stored at 0th
row and 1st column.

You might also like