稀疏矩阵格式#

坐标 (COO)#

以 COO 格式存储的稀疏矩阵由以下参数表示。

  • 矩阵中的行数。

  • 矩阵中的列数。

  • 矩阵中非零元素的数量 (nnz)。

  • 指向长度为 nnz 的行索引数组的指针，该数组包含 values 数组中对应元素的行索引。

  • 指向长度为 nnz 的列索引数组的指针，该数组包含 values 数组中对应元素的列索引。

  • 指向长度为 nnz 的 values 数组的指针，该数组以行优先顺序保存矩阵的所有非零值。

  • COO 表示法的每个条目都包含一个 <行, 列> 对。

  • COO 格式假定按行排序。

以下示例显示了以 COO 格式表示的 \(5 \times 4\) 矩阵。

../_images/coo.png
../_images/coo_one_base.png

注意

NVPL Sparse 支持给定行内已排序和未排序的列索引。

注意

如果给定行内的列索引不唯一，则计算的正确性并不总是能保证。

给定 COO 格式（零基）中的条目，则密集矩阵中的对应位置计算为

// row-major
rows_indices[i] * leading_dimension + column_indices[i]

// column-major
column_indices[i] * leading_dimension + rows_indices[i]

压缩稀疏行 (CSR)#

CSR 格式类似于 COO，其中行索引被压缩并替换为偏移量数组。

以 CSR 格式存储的稀疏矩阵由以下参数表示。

  • 矩阵中的行数。

  • 矩阵中的列数。

  • 矩阵中非零元素的数量 (nnz)。

  • 指向长度为行数 + 1的行偏移量数组的指针，该数组表示 columns 和 values 数组中每一行的起始位置。

  • 指向长度为 nnz 的列索引数组的指针，该数组包含 values 数组中对应元素的列索引。

  • 指向长度为 nnz 的 values 数组的指针，该数组以行优先顺序保存矩阵的所有非零值。

以下示例显示了以 CSR 格式表示的 \(5 \times 4\) 矩阵。

../_images/csr.png
../_images/csr_one_base.png

注意

NVPL Sparse 支持给定行内已排序和未排序的列索引。

注意

如果给定行内的列索引不唯一，则计算的正确性并不总是能保证。

给定 CSR 格式（零基）中的条目，则密集矩阵中的对应位置计算为

// row-major
row * leading_dimension + column_indices[row_offsets[row] + k]

// column-major
column_indices[row_offsets[row] + k] * leading_dimension + row

压缩稀疏列 (CSC)#

CSC 格式类似于 COO，其中列索引被压缩并替换为偏移量数组。

以 CSC 格式存储的稀疏矩阵由以下参数表示。

  • 矩阵中的行数。

  • 矩阵中的列数。

  • 矩阵中非零元素的数量 (nnz)。

  • 指向长度为列数 + 1的列偏移量数组的指针，该数组表示 columns 和 values 数组中每一列的起始位置。

  • 指向长度为 nnz 的行索引数组的指针，该数组包含 values 数组中对应元素的行索引。

  • 指向长度为 nnz 的 values 数组的指针，该数组以列优先顺序保存矩阵的所有非零值。

以下示例显示了以 CSC 格式表示的 \(5 \times 4\) 矩阵。

../_images/csc.png
../_images/csc_one_base.png

注意

CSR 格式与其 CSC 格式的转置（反之亦然）具有完全相同的内存布局。

注意

NVPL Sparse 支持给定列内已排序和未排序的行索引。

注意

如果给定列内的行索引不唯一，则计算的正确性并不总是能保证。

给定 CSC 格式（零基）中的条目，则密集矩阵中的对应位置计算为

// row-major
column * leading_dimension + row_indices[column_offsets[column] + k]

// column-major
row_indices[column_offsets[column] + k] * leading_dimension + column

切片 Ellpack (SELL)#

切片 Ellpack 格式是标准化的且广为人知的最先进格式。这种格式可以显著提高每行非零元素数量变化较小的所有问题的性能。

SELL 格式的矩阵被划分为切片，每个切片包含确切的行数 (\(sliceSize\))，由用户定义。为每个切片找到最大行长度（即，每行的最大非零元素数），并且切片中的每一行都填充到最大行长度。值 -1 用于填充。

一个 \(m \times n\) 稀疏矩阵 \(A\) 等效于一个切片稀疏矩阵 \(A_{s}\)，具有 \(nslices = \left \lceil{\frac{m}{sliceSize}}\right \rceil\) 个切片行和 \(n\) 列。为了提高内存合并和内存利用率，每个切片都以列优先顺序存储。

以 SELL 格式存储的稀疏矩阵由以下参数表示。

  • 切片数量。

  • 矩阵中的行数。

  • 矩阵中的列数。

  • 矩阵中非零元素的数量 (nnz)。

  • 元素总数 (sellValuesSize)，包括非零值和填充元素。

  • 指向长度为 \(nslices + 1\) 的切片偏移量的指针，该偏移量保存与 columns 和 values 数组对应的切片的偏移量。

  • 指向长度为 sellValuesSize 的列索引数组的指针，该数组包含 values 数组中对应元素的列索引。列索引以列优先布局存储。值 -1 表示填充。

  • 指向长度为 sellValuesSize 的 values 数组的指针，该数组以列优先布局保存所有非零值和填充。

以下示例显示了以 SELL 格式表示的 \(5 \times 4\) 矩阵。

../_images/sell.png
../_images/sell_one_base.png