Sparse Matrices
Shalini Singh Jaspal, Lecturer, BVICAM
Concept
Considerations while designing algorithms:
An application needs to choose an algorithm for solving a
problem
The choice is based upon the fact that what needs to be saved in
the target environment
Time; or
Space
Time-space complexity says that in order to save one an
algorithm, generally, needs to compromise on other; an example
storage of sparse-matrices,
Shalini Singh Jaspal, Lecturer, BVICAM
Sparse Matrices
Matrices that are sparsely (<=30%) populated.
i.e. most of whose elements are blank.
Storing these matrices in regular form implies most of the space is
wasted.
Solution: Use an alternate storage scheme in order to save space.
Cost Paid: Time complexity for accessing elements randomly
increases.
Shalini Singh Jaspal, Lecturer, BVICAM
Regular Storage Scheme
5
6
Cells Occupied: 5
Available: 5*5= 25
% Used= 5/25*100
= 20%
% Wasted= 80%
Significant as the
size of the matrix
grows
70
30
Shalini Singh Jaspal, Lecturer, BVICAM
Compressed Storage I
Row Count
Column Count
1
Actual Row Number
Actual Col Number
5
Count of
occupied cells
70
30
Shalini Singh Jaspal, Lecturer, BVICAM
Data Stored
Space Saved
Space used in original storage scheme= R*C
Space used in 3-Column notation= (N+1)*3
If N=30% of R*C =>
Space used = 90% (Approximately)
Space Saved = 10%
Shalini Singh Jaspal, Lecturer, BVICAM
Accessing Elements Sequentially
For I Between 0 To N- 1
For J Between 0 To N- 1
Get Arr[I][J]
End For
End For
Shalini Singh Jaspal, Lecturer, BVICAM
Accessing Elements Sequentially
RowCount=
ColCount=
Ctr=0
For I Between 0 To RowCount
For J Between 0 to ColCount
If <element found in Sparse> Then
Result [I][J]= Get Sparse [----][----]
Ctr++
Break <when>
Else
Result [I][J]= 0
End If
End For
End For
Shalini Singh Jaspal, Lecturer, BVICAM
Accessing Elements Randomly
Count= <Count of populated items>
For I Between 1 To Count
If <Required Row- Col is the same as Row- Col of I th
element> Then
Result= Sparse[---][---]
Break <when>
End If
End For
Shalini Singh Jaspal, Lecturer, BVICAM
Compressed Storage II
Row Count
5
0
Column Count
Problem!!!
Logical Position
5
5
10
70
23
30
Data Stored
Shalini Singh Jaspal, Lecturer, BVICAM
10
Compressed Storage II
Row Count
5
0
Column Count
Logical Position
End of Storage
Marker
5
5
10
70
23
30
-1
-1
Data Stored
Shalini Singh Jaspal, Lecturer, BVICAM
11
Space Saved
Space used in original storage scheme= R*C
Space used in 2-Column notation= (N+2)*2
If N=30% of R*C =>
Space used = 60% (Approximately)
Space Saved = 40%
Shalini Singh Jaspal, Lecturer, BVICAM
12
Accessing Elements Sequentially
Do it Yourself
Shalini Singh Jaspal, Lecturer, BVICAM
13
Accessing Elements Randomly
Do it Yourself
Shalini Singh Jaspal, Lecturer, BVICAM
14
Further Discussions
Adding two sparse matrices
Generating Transpose of a Sparse Matrix
Multiplying two Sparse Matrices
Shalini Singh Jaspal, Lecturer, BVICAM
15
This document was created with Win2PDF available at [Link]
The unregistered version of Win2PDF is for evaluation or non-commercial use only.