Developer Reference for Intel® oneAPI Math Kernel Library for Fortran

ID 766686
Date 11/07/2023
Public

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

Document Table of Contents

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)-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=1, ..5;
				pointerE(i) = rowIndex(i+1) for i=1, ..5.

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:

   Subroutine name_routine(.... ,  values, columns, pointerB, pointerE, ...)

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

   call name_routine(.... ,  values, columns, rowIndex, rowIndex(2), ...).