Data Structure and Algorithms
Sparse matrices
Puneet Kumar Jain
CSE Department
National Institute of Technology Rourkela
Reference
Most of the slides in this presentation belongs to : Douglas
Wilhelm Harder, M.Math, LEL, University of Waterloo
https://ece.uwaterloo.ca/~dwharder/aads/,
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Sparse Matrices
Sparse … many elements are zero
Dense … few elements are zero
(#nonzero elements/#elements) is small.
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
SPARSE MATRICES
lower triangular matrix: all elements above the main diagonal
have a zero value.
Only elements on or below diagonal may be nonzero
Ratio is n(n+1)/(2n2) ~ 0.5 [n: number of rows]
Lower-triangular matrix upper-triangular matrix
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
SPARSE MATRICES
Diagonal
Only elements along diagonal may be nonzero
n x n matrix ratio is n/n2 = 1/n
Tridiagonal
Only elements on 3 central diagonals may be nonzero
Ratio is (3n-2)/n2 = 3/n – 2/n2
tri-diagonal matrix
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Sparse Matrices representation
Using 2D array:
An n x n matrix may be stored as an n x n array.
This takes O(n2) space.
Using 1D array which stores only non-zero elements. The mapping
can be done in any one of the following ways:
Lower-triangular matrix
(a)Row-wise mapping—array A[] will be
{1, 5,3, 2, 7, –1, 3, 1, 4, 2, –9, 2, –8, 1, 7}
(b) Column-wise mapping—array A[] will be
{1, 5, 2, 3, –9, 3, 7, 1, 2, –1, 4, –8, 2, 1, 7}
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Unstructured Sparse Matrices
Airline flight matrix.
airports are numbered 1 through n
flight(i,j) = list of nonstop flights from airport i to airport j
n = 1000 (say)
n x n array of list references => 4 million bytes (1000x1000x4bytes)
total number of flights = 20,000 (say)
need at most 20,000 list references => at most 80,000 bytes
80000/(1000x1000x4)=0.02 = 2%
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Unstructured Sparse Matrices
Web page matrix.
web pages are numbered 1 through n
web(i,j) = number of links from page i to page j
Unstructured sparse matrix
Web analysis. 00304
authority page … page that has many links to it 00570
hub page … links to many authority pages 00000
02600
n = 2 billion (and growing by 1 million a day)
n x n array of ints => 16 * 1018 bytes (16 * 109 GB)
each page links to 10 (say) other pages on average
on average there are 10 nonzero entries per row
space needed for nonzero elements is approximately 20 billion x 4
bytes = 80 billion bytes (80 GB)
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Representation Of Unstructured Sparse Matrices
Single linear list in row-major order.
scan the nonzero elements of the sparse matrix in row-major order
each nonzero element is represented by a triple
(row, column, value)
the list of triples may be an array list or a linked list (chain)
list =
00304 row 1 1 2 2 4 4
00570
00000 column 3 5 3 4 2 3
02600
value 3 4 5 7 2 6
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Array Representation
row 1 1 2 2 4 4
list = column 3 5 3 4 2 3
value 3 4 5 7 2 6
element 0 1 2 3 4 5
row 1 1 2 2 4 4
column 3 5 3 4 2 3
value 3 4 5 7 2 6
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Chain Representation
row col
Node structure.
value next
row 1 1 2 2 4 4
list = column 3 5 3 4 2 3
value 3 4 5 7 2 6
1 3 1 5 2 3 2 4 4 2 4 3
3 4 5 7 2 6 null
firstNode
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
One Linear List Per Row
row1 = [(3, 3), (5,4)]
00304
00570 row2 = [(3,5), (4,7)]
00000 row3 = []
02600
row4 = [(2,2), (3,6)]
next
Node structure.
col value
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Array Of Row Chains
null
3 3 5 4
00304
null
00570
3 5 4 7
00000
02600
null
null
2 2 3 6
row[]
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Orthogonal List Representation
Both row and column lists.
Node structure.
row col value
down next
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Row Lists
1 3 3 1 5 4
n
00304
00570 2 3 5 2 4 7
n
00000
02600
null
4 2 2 4 3 6
n
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Column Lists
1 3 3 1 5 4
n
00304
00570 2 3 5 2 4 7
00000
02600
4 2 2 4 3 6
n n
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Orthogonal Lists
1 3 3 1 5 4
n n
00304
00570 2 3 5 2 4 7
n
00000
02600
null
4 2 2 4 3 6
n n n
row[]
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Approximate Memory Requirements
500 x 500 matrix with 1994 nonzero elements
2D array 500 x 500 x 4 = 1million bytes
Single Array List 3 x 1994 x 4 = 23,928 bytes
One Chain Per Row
4(entries) x 1994(element) x 4(bytes) +
500 x 4 =33904
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Matrix Transpose
0 0 3 0 4 0000
0 0 5 7 0 0002
0 0 0 0 0 3506
0 2 6 0 0 0700
4000
row 1 1 2 2 4 4 2 3 3 3 4 5
column 3 5 3 4 2 3 4 1 2 4 2 1
value 3 4 5 7 2 6 2 3 5 6 7 4
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Sparse Matrix transpose
Step 1: #nonzero in each row of transpose.
= #nonzero in each column of original matrix
0000
00304 = [0, 1, 3, 1, 1]
0002
00570 Step2: Start of each row of transpose
3506
00000 = sum of size of preceding rows of transpose
0700
02600 = [0, 0, 1, 4, 5] (assume array index)
4000
Step 3: Move elements from the original list to
transpose list. According to the col_val on or after the
index[col_val]+1
row 1 1 2 2 4 4 2 3 3 3 4 5
column 3 5 3 4 2 3 4 1 2 4 2 1
value 3 4 5 7 2 6 2 3 5 6 7 4
Starting index of array is 1 not 0
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Sparse matrix addition
Simply traverse through both matrices element by element
insert the smaller element (one with smaller row and col value) into
the resultant matrix.
If we come across an element with the same row and column value,
we simply add their values and insert the added data into the
resultant matrix.
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Example:
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Sparse matrix multiplication
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Sparse matrix multiplication
First calculate transpose of the second matrix to simplify our
comparisons and maintain the sorted order.
Transpose
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Ref: https://www.geeksforgeeks.org/operations-sparse-matrices/
Sparse matrix multiplication
The resultant matrix is obtained by traversing through the entire
length of both matrices and summing the appropriate multiplied
values.
Any row value equal to x in the first matrix and row value equal to
y in the second matrix (transposed one) will contribute towards
result[x][y].
This is obtained by multiplying all such elements having col value
in both matrices and adding only those with the row as x in first
matrix and row as y in the second transposed matrix to get the
result[x][y].
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Time complexity
Worst case time complexity:
Addition operation: traverses the matrices linearly, hence, has a
time complexity of O(n), where n is the number of non-zero
elements in the larger matrix amongst the two.
Transpose: has a time complexity of O(n+m), where n is the
number of columns and m is the number of non-zero elements in
the matrix.
Multiplication, O(x*n + y*m)
where (x, m) is number of columns and terms in the second matrix;
and (y, n) is number of rows and terms in the first matrix.
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
• End of chapter
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
