Sparse BLAS CSR Matrix Storage Format

Developer Reference for Intel® oneAPI Math Kernel Library for C

Download PDF

ID 766684

Date 11/07/2023

Version

Public

A newer version of this document is available. Customers should click here to go to the newest version.

Visible to Intel only — GUID: GUID-3FD9A93D-CA65-4321-BED6-7593C6EEDB60

View Details

Sparse BLAS CSR Matrix Storage Format

The Intel® oneAPI Math Kernel Library (oneMKL) Sparse BLAS compressed sparse row (CSR) format is specified by four arrays:

values
columns
pointerB
pointerE

In addition, each sparse matrix has an associated variable ,indexing, which specifies if the matrix indices are 0-based (indexing=0) or 1-based (indexing=1). These are descriptions of the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrix A.

values: A real or complex array that contains the non-zero elements of A. Values of the non-zero elements of A are mapped into the values array using the row-major storage mapping described above.
columns: Element i of the integer array columns is the number of the column in A that contains the i-th value in the values array.
pointerB: Element j of this integer array gives the index of the element in the values array that is first non-zero element in a row j of A. Note that this index is equal to pointerB[j]-indexing .
pointerE: An integer array that contains row indices, such that pointerE[j]-1-indexing is the index of the element in the values array that is last non-zero element in a row j of A.

The length of the values and columns arrays is equal to the number of non-zero elements in A.The length of the pointerB and pointerE arrays is equal to the number of rows in A.

NOTE:

Note that the Intel® oneAPI Math Kernel Library (oneMKL) Sparse BLAS routines support the CSR format both with one-based indexing and zero-based indexing.

You can represent the matrix B

in the CSR format as:

Storage Arrays for a Matrix in CSR Format
one-based indexing
`values`	=	(1	-1	-3	-2	5	4	6	4	-4	2	7	8	-5)
`columns`	=	(1	2	4	1	2	3	4	5	1	3	4	2	5)
`pointerB`	=	(1	4	6	9	12)
`pointerE`	=	(4	6	9	12	14)
zero-based indexing
`values`	=	(1	-1	-3	-2	5	4	6	4	-4	2	7	8	-5)
`columns`	=	(0	1	3	0	1	2	3	4	0	2	3	1	4)
`pointerB`	=	(0	3	5	8	11)
`pointerE`	=	(3	5	8	11	13)

Additionally, you can define submatrices with different pointerB and pointerE arrays that share the same values and columns arrays of a CSR matrix. For example, you can represent the lower right 3x3 submatrix of B as:

Storage Arrays for a Matrix in CSR Format
one-based indexing
`subpointerB`	=	(6	10	13)
`subpointerE`	=	(9	12	14)
zero-based indexing
`subpointerB`	=	(5	9	12)
`subpointerE`	=	(8	11	13)

NOTE:

The CSR matrix must have a monotonically increasing row index. That is, pointerB[i] ≤ pointerB[j] and pointerE[i] ≤ pointerE[j] for all indices i <j.

This storage format is used in the NIST Sparse BLAS library [Rem05].

Three Array Variation of CSR Format

The storage format accepted for the direct sparse solvers is a variation of the CSR format. It also is used in the Intel® oneAPI Math Kernel Library (oneMKL) Sparse BLAS Level 2 both with one-based indexing and zero-based indexing. The above matrixB can be represented in this format (referred to as the 3-array variation of the CSR format or CSR3) as:

Storage Arrays for a Matrix in CSR Format (3-Array Variation)
one-based indexing
`values`	=	(1	-1	-3	-2	5	4	6	4	-4	2	7	8	-5)
`columns`	=	(1	2	4	1	2	3	4	5	1	3	4	2	5)
`rowIndex`	=	(1	4	6	9	12	14)
zero-based indexing
`values`	=	(1	-1	-3	-2	5	4	6	4	-4	2	7	8	-5)
`columns`	=	(0	1	3	0	1	2	3	4	0	2	3	1	4)
`rowIndex`	=	(0	3	5	8	11	13)

The 3-array variation of the CSR format has a restriction: all non-zero elements are stored continuously, that is the set of non-zero elements in the row J goes just after the set of non-zero elements in the row J-1.

There are no such restrictions in the general (NIST) CSR format. This may be useful, for example, if there is a need to operate with different submatrices of the matrix at the same time. In this case, it is enough to define the arrays pointerB and pointerE for each needed submatrix so that all these arrays are pointers to the same array values.

By definition, the array rowIndex from the Table "Storage Arrays for a Non-Symmetric Example Matrix" is related to the arrays pointerB and pointerE from the Table "Storage Arrays for an Example Matrix in CSR Format", and you can see that

				pointerB[i] = rowIndex[i] for i=0, ..4;
				pointerE[i] = rowIndex[i+1] for i=0, ..4.

This enables calling a routine that has values, columns, pointerB and pointerE as input parameters for a sparse matrix stored in the format accepted for the direct sparse solvers. For example, a routine with the interface:

   void name_routine(.... ,  double *values, MKL_INT *columns, MKL_INT *pointerB, MKL_INT *pointerE, ...)

can be called with parameters values, columns, rowIndex as follows:

   name_routine(.... ,  values, columns, rowIndex, rowIndex+1, ...).

Parent topic: Sparse Matrix Storage Formats

Select Your Language

Using Intel.com Search

Quick Links

Recent Searches

Advanced Search

Only search in

Developer Reference for Intel® oneAPI Math Kernel Library for C

Sparse BLAS CSR Matrix Storage Format

Three Array Variation of CSR Format