Page 94 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 6: Operations on Arrays and Sparse Matrices

Notes
Figure 6.11: JDS Format for the Matrix A given in Figure 6.7

jdiag 1 3 7 8 10 2; 9 9 8 -1; 9 6 7 5; 13

col_ind 1 1 2 3 1 5; 4 2 3 6; 5 3 4 5; 6

perm 5 2 3 4 1 6

jd_ptr 1 7 13 17

Skyline Storage

The final storage scheme we consider is for skyline matrices, which are also called variable band
or profile matrices. It is mostly of importance in direct solution methods, but it can be used for
handling the diagonal blocks in block matrix factorization methods.

Notes A major advantage of solving linear systems having skyline coefficient matrices is
that when pivoting is not necessary, the skyline structure is preserved during Gaussian
elimination.
If the matrix is symmetric, we only store its lower triangular part. A straightforward approach
in storing the elements of a skyline matrix is to place all the rows (in order) into a floating point
array (val(:)), and then keep an integer array (row_ptr(:)) whose elements point to the beginning
of each row. The column indices of the non-zeros stored in val(:) are easily derived and are not
stored.
For a non-symmetric skyline matrix such as the one illustrated in Figure 6.12, we store the lower
triangular elements in skyline storage (SKS) format and store the upper triangular elements in
a column-oriented SKS format (transpose stored in row-wise SKS format). These two separated
substructures can be linked in a variety of ways. One approach is to store each row of the lower
triangular part and each column of the upper triangular part contiguously into the floating
point array (val(:)). An additional pointer is then needed to determine where the diagonal
elements, which separate the lower triangular elements from the upper triangular elements, are
located.
Figure 6.12: Profile of a Non-symmetric Skyline or Variable-band Matrix.

LOVELY PROFESSIONAL UNIVERSITY 87