Developer Reference

Contents

Sparse BLAS CSR Matrix Storage Format

The
Intel® MKL
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 that the
Intel® MKL
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)
 
 
 
 
 
 
 
 
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® 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:
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, ...).

Product and Performance Information

1

Intel's compilers may or may not optimize to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice.

Notice revision #20110804