The Jagged Diagonal Storage format can be useful for the implementation of iterative methods on parallel and vector processors (see Saad [185]). Like the Compressed Diagonal format, it gives a vector length essentially of the size of 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. In the matrix
from (
) all elements are shifted left:
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:
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.
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 
. The data structure to
represent the 
matrix 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 are discussed by Saad in [185].
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)
.