稀疏矩阵的三种存储方式：COO、CSR、CSC详解

稀疏矩阵的三种存储方式：COO、CSR、CSC详解

引用

CSDN

1.

https://blog.csdn.net/m0_57102661/article/details/140112320

稀疏矩阵是一种大部分元素为零的矩阵，因此使用特殊的数据结构来存储稀疏矩阵可以节省内存并提高计算效率。本文将介绍三种常见的稀疏矩阵存储方式：COO（Coordinate List，坐标列表）、CSR（Compressed Sparse Row，压缩稀疏行）和CSC（Compressed Sparse Column，压缩稀疏列）。

1. COO（Coordinate List，坐标列表）存储方式：

这种格式存储三个数组：行索引数组、列索引数组和值数组。

• 对于矩阵中的每一个非零元素，COO存储其行索引、列索引和对应的值。
• 优点是插入和删除非零元素方便，但不支持快速矩阵向量乘法。
• 缺点是空间复杂度较高，因为需要存储所有非零元素的索引。

2. CSR（Compressed Sparse Row，压缩稀疏行）存储方式：

这种格式使用三个数组：值数组、列索引数组和行指针数组。

• 值数组存储所有非零元素的值。
• 列索引数组存储每个非零元素的列索引。
• 行指针数组存储每行非零元素的起始位置和结束位置的索引（行指针数组的长度等于矩阵的行数加一）。
• 优点是支持快速的矩阵向量乘法，空间复杂度较低。
• 缺点是插入和删除元素不如COO格式方便。

3. CSC（Compressed Sparse Column，压缩稀疏列）存储方式：

这种格式与CSR类似，但针对列进行优化。

• 它使用三个数组：值数组、行索引数组和列指针数组。
• 值数组存储所有非零元素的值。
• 行索引数组存储每个非零元素的行索引。
• 列指针数组存储每列非零元素的起始位置和结束位置的索引（列指针数组的长度等于矩阵的列数加一）。
• 优点是支持快速的矩阵转置操作和列向量乘法。
• 缺点是行向量乘法不如CSR格式高效。

每种存储方式都有其适用的场景，选择哪种取决于具体的应用需求和操作类型。例如，如果一个应用需要频繁地进行矩阵向量乘法，CSR格式可能更合适；如果需要频繁地进行矩阵转置或列向量乘法，CSC格式可能更有优势。COO格式通常用于矩阵的构建阶段，因为插入和删除操作较为方便。

Coordinate Format (COO)

这种存储方式最直接，它使用3个数组来存储一个稀疏矩阵。通过row 和 col 数组指定元素的行索引和列索引，values中对应的值就是元素值。

• row indices: 存储每个元素的行索引
• col indices: 存储每个元素的列索引
• values: 存储每个元素的值

sp = SparseTensor(row=tensor([0, 0, 1, 1, 2, 2, 2, 3, 3]),
                  col=tensor([0, 1, 1, 2, 0, 2, 3, 1, 3]),
                  val=tensor([1, 7, 2, 8, 5, 3, 9, 6, 4]),
                  size=(4, 4), nnz=9, density=56.25%)

print(sp.to_dense())
# 输出：
# tensor([[1, 7, 0, 0],
#         [0, 2, 8, 0],
#         [5, 0, 3, 9],
#         [0, 6, 0, 4]])

print(sp.coo())
# 输出：
# (row = tensor([0, 0, 1, 1, 2, 2, 2, 3, 3]), 
#  col = tensor([0, 1, 1, 2, 0, 2, 3, 1, 3]), 
#  val = tensor([1, 7, 2, 8, 5, 3, 9, 6, 4]))

Compressed Sparse Row Format (CSR)

这种存储方式稍微复杂一些，它同样是使用3个数组来保存一个稀疏矩阵：row ptr、column indices和values。换个角度理解，我们可以认为CSR就是在COO的基础上，将row数组进行压缩，另外两个数组保持不变。在原来的COO中，相同行的元素会在row保存重复的行索引，所以我们在row中将重复的行索引删去，用row中的元素来指定当前行中所有非零元素在values中的范围。从而删去冗余的行索引。

1. row ptr指定每一行的第一个非零元素在values（或者是column indices）中对应的索引。例如row_ptr[1]的值表示为第二行的第一个非零元素在values中的索引。稀疏矩阵第n行中所有的非零元素在values中的索引范围为：[row_ptr[n], row_ptr[n+1])，意思是第n行中所有的非零元素按顺序保存在values[row_ptr[n]]至values[row_ptr[n+1]]中。
2. column indices指定values中对应元素的行索引。
3. values保存数值。

sp = SparseTensor(row=tensor([0, 0, 1, 1, 2, 2, 2, 3, 3]),
                  col=tensor([0, 1, 1, 2, 0, 2, 3, 1, 3]),
                  val=tensor([1, 7, 2, 8, 5, 3, 9, 6, 4]),
                  size=(4, 4), nnz=9, density=56.25%)

print(sp.to_dense())
# 输出：
# tensor([[1, 7, 0, 0],
#         [0, 2, 8, 0],
#         [5, 0, 3, 9],
#         [0, 6, 0, 4]])

print(sp.csr())
# 输出：
# (row_ptr = tensor([0, 2, 4, 7, 9]), 
#  col_ind = tensor([0, 1, 1, 2, 0, 2, 3, 1, 3]), 
#  values = tensor([1, 7, 2, 8, 5, 3, 9, 6, 4]))

Compressed Sparse Column Format (CSC)

这种存储方式稍微复杂一些，同样是使用3个数组来保存一个稀疏矩阵：col ptr、row indices和values。它的压缩方式与CSR相似，只不过CSR是按行压缩，而CSC是按列压缩：

1. col ptr指定每一列的第一个非零元素在values（或者是row indices）中对应的索引。例如col_ptr[1]的值表示为第二列的第一个非零元素在values中的索引。稀疏矩阵第n列中所有的非零元素在values中的索引范围为：[col_ptr[n], col_ptr[n+1])，意思是第n列中所有的非零元素按顺序保存在values[col_ptr[n]]至values[col_ptr[n+1]]中。
2. row indices指定values中对应元素的行索引。
3. values保存数值。

sp = SparseTensor(row=tensor([0, 0, 1, 1, 2, 2, 2, 3, 3]),
                  col=tensor([0, 1, 1, 2, 0, 2, 3, 1, 3]),
                  val=tensor([1, 7, 2, 8, 5, 3, 9, 6, 4]),
                  size=(4, 4), nnz=9, density=56.25%)

print(sp.to_dense())
# 输出：
# tensor([[1, 7, 0, 0],
#         [0, 2, 8, 0],
#         [5, 0, 3, 9],
#         [0, 6, 0, 4]])

print(sp.csc())
# 输出：
# (col_ptr = tensor([0, 2, 5, 7, 9]), 
#  row_ind = tensor([0, 2, 0, 1, 3, 1, 2, 2, 3]), 
#  values = tensor([1, 5, 7, 2, 6, 8, 3, 9, 4]))