Page 93 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Figure 6.9: Elements are Shifted Left

10 − 3 0 1 0 0 10 − 3 1
0 9 6 0 − 2 0 9 6 − 2
3 0 8 7 0 0 3 8 7
→
0 6 0 7 5 4 6 7 5 4
0 0 0 0 9 13 9 13
0 0 0 0 5 − 1 5 − 1

All rows are padded with zeros on the right to give them equal length. Corresponding to the
array of matrix elements val(:,:), an array of column indices,col_ind(:,:), is also stored:
Figure 6.10: An Array of column indices,col_ind(:,:)

val(:, 1) 10 9 3 6 9 5
val(:, 2) –3 6 8 7 13 –1
val(:, 3) 1 –2 7 5 0 0
val(:, 4) 0 0 0 4 0 0

col_ind(:, 1) 1 2 1 2 5 5
col_ind(:, 2) 2 3 3 4 6 6
col_ind(:, 3) 4 5 4 5 0 0
col_ind(:, 4) 0 0 0 6 0 0

It is clear that the padding zeros in this structure may be a disadvantage, especially if the
bandwidth of the matrix varies strongly. Therefore, in the CRS format, we reorder the rows of
the matrix decreasingly according to the number of non-zeros per row. The compressed and
permuted diagonals are then stored in a linear array. The new data structure is called jagged
diagonals.

Specifically, we store the (dense) vector of all the first elements in val, col_ind from each row,
together with an integer vector containing the column indices of the corresponding elements.
This is followed by the second jagged diagonal consisting of the elements in the second positions
from the left. We continue to construct more and more of these jagged diagonals (whose length
decreases).
The number of jagged diagonals is equal to the number of non-zeros in the first row, i.e.
the largest number of non-zeros in any row of A. The data structure to represent the n × n matrix
A therefore consists of a permutation array (perm(1:n)), which reorders the rows, a floating
point array (jdiag(:)) containing the jagged diagonals in succession, an integer array (col_ind(:))
containing the corresponding column indices, and finally a pointer array (jd_ptr(:)) whose elements
point to the beginning of each jagged diagonal.

The JDS format for the above matrix in using the linear arrays {perm, jdiag, col_ind, jd_ptr} is
given below (jagged diagonals are separated by semicolons):

86 LOVELY PROFESSIONAL UNIVERSITY