DSP
A Sparse Triplet Matrix File Format

DSP is a data directory which contains examples of the DSP sparse matrix data structure and file format.

The DSP format is used by CSPARSE ( "sparse triplet", except that there the indices are 0-based), by DLAP/SLAP (nonsymmetric SLAP triad format), by MATLAB, and by SPARSEKIT ("COO" or "coordinate" format).

The DSP data structure simply records, for each nonzero entry of the matrix, the row, column and value. Thus, the information in the data structure might be

• M and N, the number of rows and columns in the (original full) matrix;
• NZ_NUM, the number of nonzero elements in the matrix;
• ROW(1:NZ_NUM), the row indices of the nonzero elements;
• COL(1:NZ_NUM), the column indices of the nonzero elements;
• VAL(1:NZ_NUM), the values of the nonzero elements;

It is possible that a pair of indices (I,J) may occur more than once. Presumably, in this case, the intent is that the actual value of A(I,J) is the sum of all such entries. This is not a good thing to do, but I seem to have come across this in MATLAB.

The data structure does not require that the data be sorted. However, for efficient lookup and modification, it is very useful to be able to assume that the data is sorted. One natural sorting would be by ROW first, and then by COLUMN.

Another sorting convention might require that the first N entries of the data structure contain the information describing the diagonal entries of the matrix. If this is done, then diagonal preconditioning is easy to carry out.

The DSP file format is an ASCII file of NZ_NUM lines, with each line corresponding to a nonzero entry of the matrix, and containing the row index, column index and value of that entry, separated by spaces.

Note that MATLAB has the ability to read in a DSP file directly, via commands like:

        data = load ( 'mydata.dsp' );
        A = spconvert ( data );
      

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

CSPARSE, a C library which carries out the direct solution of sparse linear systems. It uses a 0-based indexing variant of the DSP format.

DLAP, a FORTRAN90 library which solves sparse systems of linear equations, and includes routines for handling matrices in the DLAP "Nonsymmetric Triad format" that is equivalent to the DSP format described here.

LINPLUS, a C++ library which carries out simple manipulations of matrices in a variety of formats.

MGMRES, a FORTRAN90 library which applies the restarted GMRES iterative technique to a sparse linear system stored in the DSP format.

SPARSEKIT, a FORTRAN90 library which includes routines for the conversion and manipulation of matrices in the "COO" format, which is equivalent to the DSP format described here.

ST, a data directory which describes a sparse matrix file format that is identical to the DSP format, except that it uses 0-based indexing, which is suitable for C and C++ programming.

Example:

The 4 by 6 matrix

        11   0   0  14   0  16
         0  22   0   0  25  26
         0   0  33  34   0  36
        41   0  43  44   0  46
      

       ROW  COL   VAL
       ---  ---  ----
        1    1   11.0
        1    4   14.0
        1    6   16.0
        2    3   22.0
        2    4   25.0
        2    6   26.0
        3    3   33.0
        3    4   34.0
        3    6   36.0
        4    1   41.0
        4    3   43.0
        4    4   44.0
        4    6   46.0
      

Note that the data for this matrix is SORTED in the natural way, that is, the ROW and COLUMN entries are lexically sorted.

If we specify that the diagonal elements must be listed first, we might instead have the following:

       ROW  COL   VAL
       ---  ---  ----
        1    1   11.0
        2    2    0.0
        3    3   33.0
        4    4   44.0
        1    4   14.0
        1    6   16.0
        2    3   22.0
        2    4   25.0
        2    6   26.0
        3    4   34.0
        3    6   36.0
        4    1   41.0
        4    3   43.0
        4    6   46.0
      

DSP File Characteristics:

• ASCII format;
• each line has the form I J A(I,J)
• the I and J indices are 1-based.

Reference:

1. Timothy Davis,
   Direct Methods for Sparse Linear Systems,
   SIAM, 2006,
   ISBN: 0898716136,
   LC: QA188.D386.

Sample Files:

• 5by5.dsp, a 5 by 5 matrix.
• ash219.dsp
• bcsstk01.dsp
• bcsstk16.dsp
• fs_183_1.dsp
• kershaw.dsp, the 4 by 4 Kershaw matrix.
• lp_afiro.dsp, a 27 by 51 matrix with 102 nonzero entries.
• mbeacxc.dsp
• t1.dsp, a 4 by 4 matrix.
• west0067.dsp

You can go up one level to the DATA page.