SPARSE_CC
Sparse Compressed Column Matrix File Format

SPARSE_CC, the "sparse compressed column format", is a simple data structure for storing sparse matrices.

The sparse compressed column data structure involves:

• M and N, the number of rows and columns of the matrix (we'll often assume assume the matrix is square, in which case M=N);
• NZ_NUM, the number of nonzero entries in the matrix.
• COL(1:N+1), the location in ROW and A of the first entry associated with each column; the last entry of COL indicates where the first entry of column N+1 would go.
• ROW(1:NZ_NUM), the row indices of the nonzero entries; entries are grouped by column. Within each column, the entries are presumed to be ascending sorted by row;
• A(1:NZ_NUM), the nonzero entries;

The associated SPARSE_CC file format to store this information uses 3 separate files, containing the column, row, and entry information separately. The value of M can be inferred from the maximum value to occur in the row file. The value of N can be inferred from the length of the column file (minus 1), and the value of NZ_NUM from the length of the row or entry files.

Related Data and Programs:

DLAP is a set of sparse matrix data structures and file formats associated with the DLAP linear algebra package.

DSP is a sparse matrix data structure and file format that stores the row, column and value of every entry, and uses 1-based indexing.

HB is the Harwell-Boeing sparse matrix data structure and file format; one variant of the data structure format, the unsymmetric assembled matrix format, is equivalent to the sparse compressed column data structure.

LINPLUS is a library of linear algebra routines, which includes routines for the DCC format, which is the sparse compressed column format. LINPLUS is available in a C++ version, and a FORTRAN90 version, and a MATLAB version.

SPARSE is MATLAB's sparse matrix data structure, which is equivalent to the sparse compressed column data format.

SPARSE_CR is the sparse compressed row format for sparse matrices, in which the row information is compressed.

ST is a sparse matrix data structure and file format that stores the row, column and value of every entry, and uses 0-based indexing.

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
      

COL:

        1
        3
        4
        6
        9
       10
       14
      

ROW:

        1  (column 1 begins)
        4
        2  (column 2 begins)
        3  (column 3 begins)
        4
        1  (column 4 begins)
        3
        4
        2  (column 5 begins)
        1  (column 6 begins)
        2
        3
        4
      

ENTRY:

        11.0  (column 1 begins)
        41.0
        22.0  (column 2 begins)
        33.0  (column 3 begins)
        43.0
        14.0  (column 4 begins)
        34.0
        44.0
        25.0  (column 5 begins)
        16.0  (column 6 begins)
        26.0
        36.0
        46.0
      

SPARSE_CC File Characteristics:

• A matrix is described by three files.
• Each file is in the ASCII format;
• Each line contains a single value.
• depending on the programming language being used, the indices in the ROW and COLUMN arrays may be 0-based or 1-based.

Reference:

1. Timothy Davis,
   Direct Methods for Sparse Linear Systems,
   SIAM, 2006,
   ISBN: 0898716136,
   LC: QA188.D386.
2. Tim Kelley,
   Iterative Methods for Linear and Nonlinear Equations,
   SIAM, 2004,
   ISBN: 0898713528,
   LC: QA297.8.K45.
3. Yousef Saad,
   Iterative Methods for Sparse Linear Systems,
   Second Edition,
   SIAM, 20003,
   ISBN: 0898715342,
   LC: QA188.S17.

Sample SPARSE_CC Files:

X01 is a simple example for which M=N=5 and NZ_NUM=12.

• x01_a.txt, the matrix entries.
• x01_i.txt, the row indices.
• x01_j.txt, the column pointers.

X02 is related to a finite difference approximation (-1,2-1) of the second derivative at a set of 20 equally spaced points in 1D. Thus M=N=20 and NZ_NUM=58.

• x02_a.txt, the matrix entries.
• x02_i.txt, the row indices.
• x02_j.txt, the column pointers.
• x02_b.txt, a right hand side b.
• x02_x.txt, the solution of the linear system A*x=b.

X03 is related to a finite difference approximation (-1,-1,4,-1,-1) of the second derivative at a 5 by 5 grid of equally spaced points in 2D. Thus M=N=25 and NZ_NUM=105.

• x03_a.txt, the matrix entries.
• x03_i.txt, the row indices.
• x03_j.txt, the column pointers.
• x03_cc_setup.f90, a FORTRAN90 program which set up the arrays.
• x03_cc_setup.csh, commands to compile and run the program.
• x03_cc_setup.out, the printed output from a run of the program.

You can go up one level to the DATA page.