DSS Symmetric Matrix Storage

Developer Reference for Intel® oneAPI Math Kernel Library for C

Download PDF

ID 766684

Date 7/13/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-13352348-D6FE-4BC6-B675-A4860AF0C1A7

View Details

DSS Symmetric Matrix Storage

For symmetric matrices, it is necessary to store only the upper triangular half of the matrix (upper triangular format) or the lower triangular half of the matrix (lower triangular format).

The Intel® oneAPI Math Kernel Library (oneMKL) direct sparse solvers use a row-major upper triangular storage format: the matrix is compressed row-by-row and for symmetric matrices only non-zero elements in the upper triangular half of the matrix are stored.

The Intel® oneAPI Math Kernel Library (oneMKL) sparse matrix storage format for direct sparse solvers is specified by three arrays:values, columns, and rowIndex. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrix.

values: A real or complex array that contains the non-zero elements of a sparse matrix. The non-zero elements are mapped into the values array using the row-major upper triangular storage mapping described above.
columns: Element i of the integer array columns is the number of the column that contains the i-th element in the values array.
rowIndex: Element j of the integer array rowIndex gives the index of the element in the values array that is first non-zero element in a row j.

The length of the values and columns arrays is equal to the number of non-zero elements in the matrix.

As the rowIndex array gives the location of the first non-zero element within a row, and the non-zero elements are stored consecutively, the number of non-zero elements in the i-th row is equal to the difference of rowIndex[i] and rowIndex[i+1].

To have this relationship hold for the last row of the matrix, an additional entry (dummy entry) is added to the end of rowIndex. Its value is equal to the number of non-zero elements plus one. This makes the total length of the rowIndex array one larger than the number of rows in the matrix.

NOTE:

The Intel® oneAPI Math Kernel Library (oneMKL) sparse storage scheme for the direct sparse solvers supports both one-based indexing and zero-based indexing.

Consider the symmetric matrix A:

Only elements from the upper triangle are stored. The actual arrays for the matrix A are as follows:

Storage Arrays for a Symmetric Matrix
one-based indexing
`values`	=	(1	-1	-3	5	4	6	4	7	-5)
`columns`	=	(1	2	4	2	3	4	5	4	5)
`rowIndex`	=	(1	4	5	8	9	10)
zero-based indexing
`values`	=	(1	-1	-3	5	4	6	4	7	-5)
`columns`	=	(0	1	3	1	2	3	4	3	4)
`rowIndex`	=	(0	3	4	7	8	9)

Storage Format Restrictions

The storage format for the sparse solver must conform to two important restrictions:

the non-zero values in a given row must be placed into the values array in the order in which they occur in the row (from left to right);
no diagonal element can be omitted from the values array for any symmetric or structurally symmetric matrix.

The second restriction implies that if symmetric or structurally symmetric matrices have zero diagonal elements, then they must be explicitly represented in the values array.

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

DSS Symmetric Matrix Storage

Storage Format Restrictions