Intel® Math Kernel Library 2018 Developer Reference - C
The Intel MKL compressed sparse row (CSR) format is specified by four arrays: the values, columns, pointerB, and pointerE. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrix A.
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.
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.
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] - pointerB[0]+1 .
An integer array that contains row indices, such that pointerE[j]-pointerB[0] 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 that the Intel MKL Sparse BLAS routines support the CSR format both with one-based indexing and zero-based indexing.
The matrix B
can be represented in the CSR format as:
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) |
This storage format is used in the NIST Sparse BLAS library [Rem05].
The storage format accepted for the direct sparse solvers is a variation of the CSR format. It also is used in the Intel MKL Sparse BLAS Level 2 both with one-based indexing and zero-based indexing. The above matrix B can be represented in this format (referred to as the 3-array variation of the CSR format or CSR3) as:
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, ...).