Sparse Matrix is a special kind of matrix. In this matrix many of the elements are not important. They are equal to zero. Non- important elements do not require to be processed. Yes, Sparse Matrix is considered lightly. It is just given a passing reference. Empty operations are performed on Sparse Matrix elements because such elements are insignificant.
Criterion: I have assumed that if the number of zeros in a matrix are more than the 'result' obtained after dividing the total number of matrix elements by two, then the matrix is a Sparse Matrix.
______________________________
______________________________
Sparse Matrix Specifications:
_____________________________
_____________________________
1 ) No. of rows = m
2 ) No. of columns = n
3 ) No. of elements = m × n
4 ) Enter matrix elements one by one
5 ) Half No. of elements hn = (m × n)/2
6 ) No. of zeroes = nz
7 )if ( nz >= hn )
Display 'Sparse Matrix'
else
Display 'Not a Sparse Matrix'
8) Stop
______________________________
_________________________
_________________________
Sparse Matrix Algorithm:
________________________
________________________
1 ) Start
2 ) Enter rows, m
3 ) Enter columns, n
4 ) No. of elements, ne = m × n
5 ) Enter matrix elements, No. = ne
6 ) No. of zeroes, nz = 0
7 ) for( rowindx = 0; rowindx < m;
++rowindx ) {
for( colindx = 0; colindx < n;
++colindx ) {
if(
matrix[rowindx] [colindx] == 0 ) {
++nz;
} /* end: if */
} /* end for - colindx */
} /* end for - rowindx */
8 ) Half No. of elements, hn = ne / 2;
9 ) if( nz >= hn )
Display 'Matrix is a Sparse Matrix'
else
Display 'Not a Sparse Matrix'
10 ) Stop
__________________________________
Tracing the Algorithm:
__________________________________
Sample Case I:
1 ) Start
2 ) Rows: 3 ( m )
3 ) Columns: 3 ( n )
4 ) ne = m × n = 3 × 3 = 9
5 ) Matrix Elements:
___________________________________
colI col2 col3
rowI 4 0 0
row2 5 0 0
row3 0 9 0
____________________________________
6 ) No. of zeroes, nz = 0
7 )
1 /a/ * )
____________________________________
1st outer loop visit, with rowindx = 0:-
__________________________________________
for( rowindx = 0; ( rowindx < m ) --> ( (0 < 3) --> true ) ; ++rowindx → 1 )
{
_________________________________________
///////////////////////////////////////////////////////
2 /i/ * ) 1st time inner loop:
for( colindx = 0; ( colindx < n ) --> ( 0 < 3 → true ); ++colindx -->1 ) {
if( ( matrix[rowindx][colindx] == 0 )
--> ( matrix[0][0] == 0 ) --> ( 4 == 0 → false ) ) {
/* ++nz; not executed */
} /* end: if */
} /* end for - colindx */
/////////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition ( 4 == 0 ) → false. So, ++nz is not executed.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
______________________________________
1 /a/ * ) rowindx = 0, continued:-
______________________________________
///////////////////////////////////////////////////////
2 /ii/ * ) 2nd time inner loop:
for( ; colindx < n --> ( 1 < 3 → true ) ; ++colindx → 2 ) {
if( ( matrix[rowindx][colindx] == 0 ) → ( matrix[0][1] == 0 ) → ( 0 == 0 → true ) ) {
++nz; → 1
} /* end: if */
} /* end for - colindx */
///////////////////////////////////////////////////////
____________________________________
1 /a/ * ) rowindx = 0, continued :-
____________________________________
/////////////////////////////////////////////////////////
2 /iii/ *) 3rd time inner loop:
for( ; colindx < n → ( 2 < 3 --> true ); ++colindx → 3 ) {
if( ( matrix[0][2] == 0 ) --> ( 0 == 0 --> true ) ) {
++nz; --> 2
} /* end: if */
} /* end for - colindx */
///////////////////////////////////////////////////////
_______________________________
1 /a/ * ) rowindx = 0, continued:-
________________________________
///////////////////////////////////////////////////////
2 /iv/ * ) 4th time inner loop:
for( ; colindx < n → ( 3 < 3 → false ); )
} /* end for - colindx * /
////////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition checking ( 3 < 3 → false ) stops us from entering the inner loop for the 4th time. We move on to the next pass of the outer loop with rowindx = 1.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_________________________________________
2nd outer loop visit, with rowindex = 1:-
________________________________________
for(; rowindx < m --> ( 1 < 3 --> true ); ++rowindx → 2 ) {
__________________________________________
/////////////////////////////////////////////////////////
2 /i/ ^ ) 1st time inner loop:
for( colindx = 0; colindx < n --> ( 0 < 3 → true ); ++colindx --> 1 ) {
if( ( matrix[rowindx][colindx] == 0 ) ( matrix[1][0]== 0 ) --> ( 5 == 0 → false) ) {
/* ++nz; not executed */
} /* end: if */
} /* end for - colindx */
////////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition ( 5 == 0 ) → false. So, ++nz is not executed.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
______________________________________
1 /b/ ^ ) rowindx = 1, continued:-
______________________________________
///////////////////////////////////////////////////////
2 /ii/ ^ ) 2nd time inner loop:
for(; colindx < n → ( 1 < 3 → true ); ++colindx → 2 ) {
if( ( matrix[rowindx][colindx] == 0 ) → ( matrix[1][1] == 0 ) → ( 0 == 0 → true) ) {
++nz; → 3
} /* end: if */
} /* end for - colindx */
////////////////////////////////////////////////////////
_____________________________________
1 /b/ ^ ) rowindx = 1, continued:-
_____________________________________
///////////////////////////////////////////////////////
2 /iii/ ^ ) 3rd time inner loop:
for(; colindx < n → 2 < 3 → true; ++colindx -- > 3) {
if( matrix[1][2] = 0 --> ( 0 == 0 → true ) )
++nz; → 4
} /* end: if */
} /* end for - colindx */
////////////////////////////////////////////////////////
2 /iv/ ^ ) 4th time inner loop:
for(; colindx < 3 → 3 < 3 --> false; )
/////////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition checking ( 3 < 3 → false ) stops us from entering the inner loop for the 4th time. We move on to the next pass of the outer loop with rowindx = 2.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________
1 /c/ # )
3rd visit outer loop, with rowindx = 2:-
_____________________________________
for(;( rowindx < 3 ) = ( 2 < 3 -> true ); ++rowindx -> 3 ) {
///////////////////////////////////////////////////////
2 /i/ # ) 1st time inner loop:
for(colindx = 0; colindx < n → ( 0 < 3 → true ); ++colindx → 1) {
if( (matrix[rowindx][colindx] == 0 )--> ( matrix[2][0] == 0 ) → ( 0 == 0 --> true ) ) {
++nz; → 5
} /* end: if */
} /* end for - colindx */
/////////////////////////////////////////////////////////
_____________________________________
1 /c/ # ) rowindx = 2, continued:-
______________________________________
/////////////////////////////////////////////////////////
2 /ii/ # ) 2nd time inner loop:
for(;colindx < n → ( 1 < 3 → true ); ++colindx → 2) {
if( (matrix[rowidx][colindx] == 0 ) → ( matrix[2][1] == 0 ) → ( 9 == 0 --> false ) )
/* ++nz; not executed */
} /* end: if */
} /* end for - colindx */
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition ( 9 == 0 ) → false. So, ++nz is not executed.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________
1 /c/ # ) rowindx = 2, continued:-
___________________________________
/////////////////////////////////////////////////////////
2 /iii/ # ) 3rd time inner loop:
for(; colindx < m → ( 2 < 3 → true); ++colindx → 3) {
if( ( matrix[rowindx][colindx] ==0 ) --> ( matrix[2][2] == 0 ) → ( 0 == 0 → true) ) {
++nz; → 6
} /* end: if
} /* end for - colindx */
////////////////////////////////////////////////////////
______________________________________
1 /c/ # ) rowindx = 2, continued:-
______________________________________
/////////////////////////////////////////////////////////
2 /iv/ # ) 4th time inner loop:
for(; colindx < n → ( 3 < 3 ) --> false;) {
} /* end for - colindx */
///////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition checking ( 3 < 3 → false ) stops us from entering the inner loop for the 4th time. We move on to the next pass of the outer loop with rowindx = 3.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
__________________________________
1 /d/ % )
4th visit outer loop: Isn't possible as,
for(; ( rowindx < m ) -> ( ( 3 < 3 ) -> false ); )
} /* end for - rowindx */
______________________________________
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition ( 3 < 3 ) → false. Entering outer loop with loop index identifier 'rowindx' isn't possible.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
8 ) hn = ne / 2 = 9 / 2 = 4
9) if( nz > hn = ( 6 > 4 ) = true )
Display 'Sparse Matrix'
10) Stop
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
Conclusion: In the sample matrix six out of nine elements are zeros. After processing the matrix has been correctly characterised as a .Sparse Matrix.
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
__________________________________
__________________________________
Sample Case II:
1 ) Start
2 ) Rows: 2 ( m )
3 ) Columns: 2 ( n )
4 ) n = m × n = 2 × 2 = 4
5 ) Matrix Elements:
___________________________________
colI col2
rowI 4 5
row2 9 0
____________________________________
6 ) No. of zeroes, nz = 0
7 )
________________________________________
1 /a/ * )
1st outer loop visit, with rowindx = 0:-
_________________________________________
for( rowindx = 0; ( rowindx < m ) --> ( 0 < 2 --> true ) ; ++rowindx → 1 ) {
______________________________________///////////////////////////////////////////////////////
2 /i/ *) 1st time inner loop:
for( ; colindx < n --> ( 0 < 2 → true ) ; ++colindx → 1 ) {
if( ( matrix[rowindx][colindx] == 0 ) → ( matrix[0][1] == 0 ) → ( 4 == 0 → false ) ) {
/* ++nz; not executed */
} /* end: if */
} /* end for - colindx */
/////////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition ( 4 == 0 ) → false. So, ++nz, within 'if' statement is not executed.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
____________________________________
1 /a/ * ) rowindx = 0, continued :-
____________________________________
///////////////////////////////////////////////////////
2 /ii/ * ) 2nd time inner loop:
for( ; colindx < n → ( 1 < 2 → true ); ++colindx → 2; ) {
if( ( matrix[rowindx][colindx] == 0; ) → ( matrix[0][1] == 0 ) → ( 5 == 0 → false ) {
/* ++nz; not executed */
} /* end: if */
} /* end for - colindx */
/////////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition ( 5 == 0 → false ). So, ++nz, within 'if' statement, is not executed.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________
1 /a/ * ) rowindx = 0, continued:-
______________________________________
/////////////////////////////////////////////////////////
2 /iii/ * ) 3rd time inner loop:
for( ;colindx < n → ( 2 < 2 → false ); ) {
} /* end for - colindx */
/////////////////////////////////////////////////////////
Note: Condition checking ( 2 < 2 → false ) stops us from entering the inner loop for the 3rd time. We move on to the next pass of the outer loop with rowindx = 1.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________
1 /b/ ^ )
2nd outer loop visit, with rowindex = 1:-
for(; rowindx < m --> ( 1 < 2 --> true ); ++rowindx → 2 ) {
_________________________________,_____
////////////////////////////////////////////////////////
2 /i/ ^ ) 1st time inner loop:
for( colindx = 0; colindx < n --> ( 0 < 2 → true ); ++colindx --> 1 ) {
if( ( matrix[rowindx][colindx] == 0 ) ( matrix[1][0]== 0 ) --> ( 9 == 0 → false) ) {
/* ++nz; not executed */
} /* end: if */
} /* end for - colindx */
/////////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition ( 9 == 0 ) → false. So, ++nz, within 'if' statement, is not executed.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_________________________________
1 /b/ ^ ) rowindx = 1, continued:
_________________________________
/////////////////////////////////////////////////////////
2 /ii/ ^ ) 2nd time inner loop:
for(; colindx < n → ( 1 < 2 → true ); ++colindx → 2 ) {
if( ( matrix[rowindx][colindx] == 0 ) → ( matrix[1][1] == 0 ) → ( 0 == 0 → true) ) {
++nz; → 1
} /* end: if */
} /* end for - colindx */
/////////////////////////////////////////////////////////
_______________________________
1 /b/ ^ ) rowindx = 1,continued:
______________________________
///////////////////////////////////////////////////////
2 /iii/ ^ ) 3rd time inner loop:
for( ; colindx < n → 2 < 2 → false; ) {
} /* end for - colindx */
/////////////////////////////////////////////////////////
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition checking ( 2 < 2 → false ) stops us from entering the inner loop for the 3rd time. We move on to the next pass of the outer loop with rowindx = 2.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________
1 /c/ # )
3rd visit outer loop, with rowindx = 2:
for(;( rowindx < 2 ) = ( 2 < 2 -> false ); )
} /* end for - rowindx */
______________________________________
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Note: Condition ( 2 < 2 ) → false. Entering outer loop with loop index identifier 'rowindx' isn't possible.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
8 ) hn = ne / 2 = 4 / 2 = 2
9) if( nz > hn = ( 1 > 2 ) = false )
Display 'Not a Sparse Matrix'
10) Stop
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
Conclusion: In the sample matrix as three out of four elements are non-zero, hence the matrix is not a Sparse Matrix.
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
Comments
Post a Comment