Scribd
Upload
143 views

Sparse Matrix

This document discusses sparse matrices and their representations. A sparse matrix is a matrix with mostly zero values. Storing only the non-zero elements saves memory and computing time compared to a standard matrix. There are two common representations for sparse matrices: using arrays to store the row, column, and value of each non-zero element, or using linked lists where each node contains those fields plus a pointer to the next node. The homework is to implement transposing a sparse matrix using its sparse representation.

Uploaded by

Shreyansh Shukla
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
143 views

Sparse Matrix

This document discusses sparse matrices and their representations. A sparse matrix is a matrix with mostly zero values. Storing only the non-zero elements saves memory and computing time compared to a standard matrix. There are two common representations for sparse matrices: using arrays to store the row, column, and value of each non-zero element, or using linked lists where each node contains those fields plus a pointer to the next node. The homework is to implement transposing a sparse matrix using its sparse representation.

Uploaded by

Shreyansh Shukla
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/ 10

Data Structures KCS301

Sparse matrices and their


representation
Lecture W5.L1
Department of Computer Science and Engineering
Sparse Matrix
 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.
Why to 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
Representing a sparse matrix by a 2D array leads to
wastage of lots of memory as zeroes in the matrix are
of no use in most of the cases. So, instead of storing
zeroes with non-zero elements, we only store non-zero
elements. This means storing non-zero elements
with triples- (Row, Column, value).
Sparse Matrix
Representations
1. Array representation
2. Linked list representation
Method 1: Using Arrays
2D array is used to represent a sparse matrix in which
there are three rows named as
• Row: Index of row, where non-zero element is
located
• Column: Index of column, where non-zero element is
located
• Value: Value of the non zero element located at
index – (row, column)
Method 2: Using Linked Lists
In linked list, each node has four fields. These four
fields are defined as:
• Row: Index of row, where non-zero element is
located
• Column: Index of column, where non-zero element is
located
• Value: Value of the non zero element located at
index – (row, column)
• Next node: Address of the next node
Homework
 Transpose of a sparse matrix using
sparse representation.

You might also like