Scribd
Upload
24 views

Sparse matrix

Uploaded by

poonmmalhotra698547
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
24 views

Sparse matrix

Uploaded by

poonmmalhotra698547
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/ 16

BCAC303

Data Structure and Algorithm

Module-2:Sparse Matrix
Introduction

● In scientific computing and numerical analysis, a sparse array or sparse


matrix is a matrix where a large portion of the components are zero.
● There is no precise meaning of the number of components that should be
zero for a matrix to be viewed as sparse, yet a typical measure is that the
number of non-zero components is generally the number of columns or rows.
● A sparse array is an array of data where numerous components have an
estimation of zero value. This is as opposed to a dense array, where the vast
majority of the components have non-zero values or are “full” of numbers.
Why is a sparse matrix required if we can use the simple matrix to store elements?

There are the following benefits of using the sparse matrix -


Storage - We know that a sparse matrix contains lesser non-zero elements than zero, so less memory can be used
to store elements. It evaluates only the non-zero elements.
Computing time: In the case of searching in sparse matrix, we need to traverse only the non-zero elements rather
than traversing all the sparse matrix elements,It saves computing time.
Representation of sparse matrix

There are two ways to represent the sparse matrix that are listed as follows -
Array representation
Linked list representation
Example
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.

● 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).

Example -
Let's understand the array representation of sparse matrix with the help of the example given below -

Consider the sparse matrix -


Linkedlist Representation of Sparse Matrix

In a linked list representation of a sparse


matrix, each non-zero element is represented
as a node in a linked list.
Each node stores:

1. Row index (i)


2. Column index (j)
3. Value (val)
4. Pointer to the next node
Types of sparse matrix

1). Lower triangular sparse matrix


2). Upper triangular sparse matrix
3). Tri-diagonal matrix
LOWER TRIANGULAR MATRIX/SPARSE MATRIX

In a Lower triangular sparse matrix, all elements above the main diagonal have a zero value.
A lower-triangular Matrix Array of size n*n has one non-zero element in the first row, two non-zero elements in
the second row, and similarly n non-zero elements in the nth row.
Example:-
UPPER TRIANGULAR MATRIX/SPARSE MATRIX

In the Upper triangular sparse matrix, all elements below the main diagonal
have a zero value.

An n*n upper-triangular matrix Arr has n non-zero elements in the first row,
n–1 non-zero element in the second row, and likewise one non-zero element
in the nth row.

Example:-
TRI-DIAGONAL MATRIX

Tri-diagonal matrix is also another type of a sparse matrix, where elements with a non-zero value appear only on
the diagonal or immediately below or above the diagonal.
In a tridiagonal matrix, Arr i,j=0, where |i – j| > 1.
Example:-
Sparse Matrices In Data Structures

● Sparse matrix is a two dimensional array in which most of the elements have null value or zero “0”.
● In large number of applications sparse matrices are used.It is wastage of memory and processing time it
store null values of a matrix in array.
● To avoid such circumstances different techniques are used such as linked list.
● In simple words sparse matrices are matrices that allow special techniques to take advantage of the large
number of null elements and the structure.
Applications of Sparse Matrices

● Machine Learning: Storing large datasets with many zeroes (e.g., document-term matrices).
● Graph Theory: Adjacency matrices are often sparse in large graphs.
● Optimization Problems: Sparse matrices are used to store and solve linear equations.
● Image Processing: Efficiently storing and processing images with mostly black pixels.
Advantages of Using Sparse Matrices

● Memory Efficiency: Reduces the storage required for large datasets.


● Speed: Operations like matrix multiplication are faster as they skip zero elements.
● Scalability: Suitable for large-scale problems (e.g., scientific computing).
Challenges with Sparse Matrices

● Complex Representation: More sophisticated data structures are required.


● Conversion Overhead: Converting between sparse and dense matrices can be costly.
● Not Always Faster: For small matrices, the overhead of sparse representation can outweigh the benefits.
THANK YOU
www.inspiria.edu.in

You might also like