Jagged Diagonal Storage (JDS)

Jagged Diagonal Storage (JDS)

The Jagged Diagonal Storage format can be useful for the implementation of iterative methods on parallel and vector processors (see Saad [181]). 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 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 [181].

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)