Jagged Diagonal Storage

The jagged diagonal storage (JDS) format can be useful for the implementation of iterative methods on parallel and vector processors (see Saad [385]). Like the CDS format, it gives a vector length of essentially the same size as the matrix. 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. For the following nonsymmetric matrix, all elements are shifted left:

$$\left[\begin{array}{rrrrrr} 10 & -3 & 0 & 1 & 0 & 0 \\ 0 ... ...\\ 6 & 7 & 5 & 4 \\ 9 & 13 \\ 5 & -1 \end{array}\right]$$

after which the columns are stored consecutively. 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:

$$\begin{array}{\vert r\vert r\vert r\vert r\vert r\vert r\ver... ... {\tt val}(:,4) & 0 & 0 & 0 & 4 & 0 & 0 \\ \hline \end{array},$$

$$\begin{array}{\vert r\vert r\vert r\vert r\vert r\vert r\ver... ... col\_ind}(:,4) & 0 & 0 & 0 & 6 & 0 & 0 \\ \hline \end{array}.$$

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 nonzeros 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 nonzeros in the first row, i.e., the largest number of nonzeros in any row of $A$. The data structure to represent the $n \times 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 advantages of JDS for matrix multiplications were discussed by Saad in [385].

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

jdiag	1	3	7	8	10	2;	9	9	8 $\cdots$ -1;	9	6	7	5;	13
col_ind	1	1	2	3	1	5;	4	2	3 $\cdots$ 6;	5	3	4	5;	6

perm

5

2

3

4

1

6

jd_ptr

1

7

13

17

 .