SPARSE MATRIX AND ITS OPERATION
LEARNING OBJECTIVES
o To know the concept of sparse matrix
o To represent sparse matrix
o To perform operations like
o Add
o Multiply
o Transpose
SPARSE MATRIX
Matrix in General
M rows
N columns
Store a two dimensional matrix in an array
Col 1 Col 2 Col 3
Row 0 27 7 3
Row 1 6 82 2
Row 2 109 64 11
Row 3 48 27 47
SPARSE MATRIX
A matrix is sparse if most of its entries are zero.
The opposite of a sparse matrix is one that has more non-zero elements
than zero elements and is called a dense matrix.
It is often most efficient to store only the nonzero entries of a sparse
matrix, but this requires that location information also be stored.
Total number of elements that are equal to zero > (m * n)/2 (check
condition for sparse matrix)
SPARSE MATRIX EXAMPLE
WHY TO USE SPARSE 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.
SPARSE MATRIX REPRESENTATION
A sparse matrix can be represented by using TWO representations, those
are as follows...
Triplet Representation (Array Representation)
Linked Representation
TRIPLET REPRESENTATION
triples- (Row, Column,
value)
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)
TRIPLET REPRESENTATION
triples- (Row, Column, value)
A[0].rows : number of rows of
the matrix
A[0].columns: number of
columns of the matrix
A[0].values: number of
nonzero entries
The triples are order by rows
and within rows by column Size of sparse Matrix is Size of sparse Matrix is
[5 x 6] [7 x 3]
Requires 5 x 6 x 4 = 120 bytes Requires 7 x 3 x 4 = 84 bytes
SPARSE MATRIX EXAMPLE
WRITE SPARSE MATRIX FOR THE FOLLOWING GIVEN MATRIX
#include<iostream>
using namespace std;
int main()
{
// sparse matrix of 5x6 with 6 non-zero values
TRIPLET REPRESENTATION
int sparseMatrix[5][6] =
{
{0 , 0 , 0 , 0 , 9, 0 },
{0 , 8 , 0 , 0 , 0, 0 },
{4 , 0 , 0 , 2 , 0, 0 },
{0 , 0 , 0 , 0 , 0, 5 },
{0 , 0 , 2 , 0 , 0, 0 }
};
// Finding total non-zero values in the sparse matrix
int size = 0;
for (int row = 0; row < 5; row++)
for (int column = 0; column < 6; column++)
if (sparseMatrix[row][column] != 0)
size++;
// Defining result Matrix
int resultMatrix[3][size];
// Generating result matrix
int k = 0;
for (int row = 0; row < 5; row++)
for (int column = 0; column < 6; column++)
if (sparseMatrix[row][column] != 0)
{
resultMatrix[0][k] = row;
resultMatrix[1][k] = column;
resultMatrix[2][k] = sparseMatrix[row][column];
k++;
}
// Displaying result matrix
cout<<"Triplet Representation : "<<endl;
for (int i=0; i<3; i++)
{
for (int j = 0; j<size; j++)
cout<<resultMatrix[i][j]<<" ";
cout<<endl;
}
return 0;
}
SPARSE MATRIX :REPRESENTATION
class Sparse_Matrix
{ private:
const int Max = 20;
int S_Mat[Max][3];
public:
Sparse_Matrix transpose ( );
Sparse_Matrix add_sparsematrix ( Sparse_Matrix B);
};
TRANSPOSE OF SPARSE MATRIX
Transpose of Sparse Matrix
B[i,2] = A[i,1]
6 9 10 9 6 10
0 0 10 0 0 10
0 7 20 7 0 20 B[i,1] = A[i,2]
1 6 40 6 1 40
2 5 90 5 2 90 B[i,3] = A[i,3]
3 3 40 3 3 40
3 8 30 8 3 30
4 2 60 2 4 60
4 7 50 7 4 50 Transpose of the
5 2 90 2 5 90 given Sparse
5 6 70 6 5 70 matrix
Place element (i, j, val) at (j, i, val)
TRANSPOSE OF SPARSE MATRIX
Sparse_Matrix Sparse_Matrix : : Transpose ( )
{ 6 9 10 9 6 10
Sparse_Matrix St; 0 0 10 0 0 10
0 7 20 2 5 60
int Row, Col, i, j, k, Val ;
1 6 40 2 6 90
Row = S_Mat[0][0]; 2 5 90 3 3 40
Col = S_Mat [0][1]; 3 3 40 5 2 90
4 8 30 6 1 40
Val = S_Mat[0][2];
5 2 60 6 5 70
if (Val != 0) return; 4 7 50 7 0 20
S_Mat[0][0] = Col ; 6 2 90 7 4 50
5 6 70 8 4 30
S_Mat [0][1] = Row;
S_Mat[0][2] = Val ;
Transposed Sparse
matrix
OPERATIONS ON SPARSE MATRICES
Addition Sparse Matrices
No of rows and No of columns of both the matrix is same.
result[0][0]= a[0][0]; & result[0][1] = a[0][1]
Traverse through both matrices element by element and insert the smaller
element (one with smaller row and col value) into the resultant matrix
For an element with the same row and column value, we simply add their
values and insert the added data into the resultant matrix.
ADDITION OF SPARSE MATRICES
Matrix 1: (4x4) Matrix 2: (4x4) Result Matrix: (4 X 4)
Row Column Value Row Column Value Row Column Value
1 2 10 1 3 8 1 2 10
1 4 12 2 4 23 1 3 8
3 3 5 3 3 9 1 4 12
4 1 15 4 1 20 2 4 23
4 2 12 4 2 25 3 3 14
4 1 35
4 2 37
THANK YOU !!!