Sparse BLAS BSR Matrix Storage Format

Developer Reference for Intel® oneAPI Math Kernel Library for Fortran

Download PDF

ID 766686

Date 3/31/2025

Version

Public

Sparse BLAS BSR Matrix Storage Format

The Intel® oneAPI Math Kernel Library (oneMKL) block compressed sparse row (BSR) format for sparse matrices is specified by four arrays:

values
columns
pointerB
pointerE

In addition, each sparse matrix has an associated variable, indexing, which specifies whether the matrix indices are 0-based (indexing=0) or 1-based (indexing=1). 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:

values: A real or complex array that contains the elements of the non-zero blocks of A. A non-zero block contains at least one non-zero element. The non-zero blocks are stored as dense matrices of dimension block size, even if some elements in the block are equal to zero. The blocks are stored in row-major order. Within a block, the elements are stored in column-major order in the case of the one-based indexing, and in row-major order in the case of the zero-based indexing.
columns: Element i of the integer array columns is the number of the column in the block matrix that contains the i-th non-zero block.
pointerB: Element j of this integer array gives the index of the block in the columns array that is the first non-zero block in row j of the block matrix A. Note that the 1-based position of this block in the array is equal to pointerB(j)-indexing+1.
pointerE: Element j of this integer array gives the index of the block in the columns array that contains the last non-zero block in a row j of the block matrix A, plus 1. Note that the 1-based position of this block in the arrays is equal to pointerE(j)-indexing.

The length of the values array is equal to the number of all elements in the non-zero blocks, the length of the columns array is equal to the number of non-zero blocks. The length of the pointerB and pointerE arrays is equal to the number of block rows in the block matrix.

NOTE:

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

For example, consider the sparse matrix D

If the size of the block equals 2, then the sparse matrix D can be represented as a 3x3 block matrix E with the following structure:

where

The matrix D can be represented in the BSR format as follows:

one-based indexing

				values  =  (1 2 0 1 6 8 7 2 1 5 4 1 4 0 3 0 7 0 2 0)
				columns  = (1   2   2   2   3)
				pointerB = (1   3   4)
				pointerE = (3   4   6)

zero-based indexing

				values  =  (1 0 2 1 6 7 8 2 1 4 5 1 4 3 0 0 7 2 0 0)
				columns  = (0   1   1   1   2)
				pointerB = (0   2   3)
				pointerE = (2   3   5)

This storage format is supported by the NIST Sparse BLAS library [Rem05].

Three-Array Variation of BSR Format

Intel® oneAPI Math Kernel Library (oneMKL) supports the variation of the BSR format that is specified by three arrays: values, columns, and rowIndex. The values and columns arrays remain the same as described above. The rowIndex array replaces both the pointerB and pointerE arrays and contains the block offsets along each block row. The length of the rowIndex array is equal to the number of block rows plus 1 and the number of non-zero blocks in the i-th row is equal to rowIndex(i+1) - rowIndex(i). Because of this, the three-array variation of the BSR format has a restriction: all non-zero blocks are stored contiguously; that is, the set of non-zero blocks in row j goes just after the set of non-zero blocks in row j-1.

The matrix D can be represented in this three-array variation of the BSR format as follows:

one-based indexing

				values  =  (1 2 0 1 6 8 7 2 1 5 4 2 4 0 3 0 7 0 2 0)
				columns  = (1   2   2   2   3)
				rowIndex = (1   3   4   6)

zero-based indexing

				values  =  (1 0 2 1 6 7 8 2 1 4 5 1 4 3 0 0 7 2 0 0)
				columns  = (0   1   1   1   2)
				rowIndex = (0   2   3 5)

When storing symmetric matrices, it is necessary to store only the upper or the lower triangular part of the matrix.

For example, consider the symmetric sparse matrix F:

If the size of the block equals 2, then the sparse matrix F can be represented as a 3x3 block matrix G with the following structure:

where

, and

The symmetric matrix F can be represented in this 3-array variation of the BSR format (storing only the upper triangular part) as follows:

one-based indexing

				values  =  (1 2 0 1 6 8 7 2 1 5 4 2 7 0 2 0)
				columns  = (1   2   2   3)
				rowIndex = (1   3   4 5)

zero-based indexing

				values  =  (1 0 2 1 6 7 8 2 1 4 5 2 7 2 0 0)
				columns  = (0   1   1   2)
				rowIndex = (0   2   3 4)

Variable BSR Format

A variation of BSR3 is variable block compressed sparse row format. For a trust level t, 0 ≤t≤ 100, rows similar up to t percent are placed in one supernode.

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 Fortran

Sparse BLAS BSR Matrix Storage Format

Three-Array Variation of BSR Format

Variable BSR Format