Page 92 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 6: Operations on Arrays and Sparse Matrices

We say that the matrix A = (a ) is banded if there are nonnegative constants p, q, called the left Notes
i, j
+
p
j
and right halfbandwidth, such that a , ij ≠ 0 only if i −≤ ≤ i q . In this case, we can allocate for
the matrix an array val(1:n,-p:q). The declaration with reversed dimensions (-p:q,n) corresponds
to the LINPACK band format, which, unlike compressed diagonal storage (CDS), does not allow
for an efficiently vectorisable matrix-vector multiplication if p + q is small.
Usually, band formats involve storing some zeros. The CDS format may even contain some
array elements that do not correspond to matrix elements at all.

Example: Consider the non-symmetric matrix A defined by

Figure 6.7: Non-symmetric Matrix

10 − 3 000 0
3 9 600 0
0 7 8 7 0 0
A =
0 0 8 7 5 0
0 0 099 13
0 0 002 − 1

Using the CDS format, we store this matrix A in an array of dimension (6,-1:1) using the mapping
val (i, j) = ai, i+j
Hence, the rows of the val(:,:) array are

Figure 6.8: Rows of the val(:,:) Array

val(:,-1) 0 3 7 8 9 2

val(:, 0) 10 9 8 7 9 -1

val(:,+1) -3 6 7 5 13 0

Notice the two zeros corresponding to nonexisting matrix elements.

Jagged Diagonal Storage

The jagged diagonal storage (JDS) format can be useful for the implementation of iterative
methods on parallel and vector processors. Like the CDS format, it gives a vector length of
essentially the same size as the matrix.

Did u know? It is more space-efficient than CDS at the cost of a gather/scatter operation.
A simplified form of JDS, called ITPACK storage or Purdue storage, can be described as follows.

Example: For the following non-symmetric matrix, all elements are shifted left after
which the columns are stored consecutively.

LOVELY PROFESSIONAL UNIVERSITY 85