1. 稀疏矩阵到底在解决什么问题第一次接触稀疏矩阵很多人会误以为它只是一种“特殊矩阵”的数学分类。其实不是。它本质上是一个工程问题催生出来的数据结构方案。当你用程序去处理一个10000×10000的矩阵时如果老老实实开一个二维数组那就是一亿个浮点数按双精度8字节算光内存就要吃掉约800MB。但实际情况是这个矩阵里可能只有不到1%的位置有非零值剩下99%全是零。你花了800MB内存结果存的全是“什么都没有”。这就是稀疏矩阵要解决的核心矛盾矩阵的数学维度很大但有效信息密度极低。在有限元分析、图计算、推荐系统、自然语言处理、计算流体力学这些领域这种“大而空”的矩阵几乎是标配。比如一个社交网络的邻接矩阵用户数量可能上千万但每个用户平均只关注几百人邻接矩阵的稀疏度通常在99.99%以上。所以稀疏矩阵的核心思路就一句话只存非零元素零元素不存但通过索引结构保证你还能找到每个非零元素在原始矩阵中的位置。听起来简单但真正落地的时候索引怎么组织、按行还是按列、排序怎么处理、矩阵乘法怎么加速每一个选择都会直接影响性能和内存占用。这篇文章我会从存储格式的底层设计讲起把CSR、CSC、COO、ELL、DIA这些常见格式的来龙去脉拆开配合实际的参数计算、代码示例和踩坑经验让你看完之后能根据自己手头的场景直接选型而不是对着文档照抄。注意网上搜“csr是什么简写”的时候会看到两个完全不同的答案。一个是Compressed Sparse Row压缩稀疏行另一个是Cloudflare的Certificate Signing Request证书签名请求。这两个东西没有任何关系只是缩写撞车了。本文只讨论前者后者属于网络安全领域的证书管理话题不在本文范围内。2. 稀疏矩阵存储格式的整体设计思路2.1 为什么不能直接用哈希表存有人可能会想既然只存非零元素那我用一个哈希表key是(row, col)value是数值不就行了吗小规模确实可以但一旦上规模就会出问题。哈希表的问题在于第一内存开销大每个键值对都有额外的哈希桶、指针、负载因子预留空间实际内存占用可能是原始数据的3到5倍第二遍历顺序不可控做矩阵乘法的时候需要按行或按列有序访问哈希表做不到第三缓存局部性差每次访问都是一次随机内存跳转CPU缓存命中率极低。所以工业级的稀疏矩阵库比如SuiteSparse、Eigen、SciPy的sparse模块都不会用哈希表作为底层存储。它们用的是压缩索引结构核心思想是把二维坐标拆成“主索引偏移量”的形式用连续数组存储保证内存紧凑和遍历有序。2.2 三种基础设计维度所有稀疏矩阵存储格式本质上都是在三个维度上做取舍第一个维度是索引的压缩程度。最原始的方式是坐标格式COO每个非零元素存一个(row, col, value)三元组。这种方式最直观但索引占用的空间可能比数值本身还大。压缩格式CSR/CSC则通过行指针数组把行索引压缩掉只保留列索引和数值。第二个维度是访问模式。按行压缩CSR适合行遍历和SpMV稀疏矩阵乘向量按列压缩CSC适合列遍历和求解线性方程组时的列操作。选错了方向性能可能差好几倍。第三个维度是规则性。如果每行的非零元素数量差不多可以用ELL格式把索引和数值排成固定宽度的二维数组GPU上特别友好。如果非零元素沿对角线分布DIA格式最省空间。但现实中的矩阵往往是不规则的所以CSR/CSC成了通用性最强的选择。2.3 选型决策的核心逻辑我在实际项目里选存储格式的时候会按下面这个顺序问自己几个问题这个矩阵是只读的还是需要频繁修改如果频繁插入新元素COO或LILList of Lists更合适CSR/CSC的插入代价很高。主要做什么运算SpMV选CSR求解器选CSC矩阵乘法看情况可能需要混合。是否跑在GPU上GPU上ELL或HYB混合格式往往比纯CSR更快。矩阵规模多大小规模非零元素少于10万其实用什么都差不多大规模才需要精细选型。这个决策逻辑贯穿全文后面讲每种格式的时候我都会回到这几个问题上。3. CSR格式深度拆解与实操3.1 CSR的三个核心数组CSR全称Compressed Sparse Row翻译过来就是压缩稀疏行。它的核心是用三个一维数组来表示整个矩阵values数组按行优先顺序存储所有非零元素的值长度等于非零元素总数nnz。col_indices数组存储每个非零元素对应的列号长度也是nnz。row_ptr数组存储每一行第一个非零元素在values中的起始位置长度是行数1。row_ptr的设计是整个CSR的精髓。它的第i个元素表示第i行的起始偏移第i1个元素表示第i行的结束偏移同时也是第i1行的起始偏移。所以第i行的非零元素就是values[row_ptr[i]]到values[row_ptr[i1]-1]这一段。最后一个元素row_ptr[n]恒等于nnz这样设计是为了方便计算最后一行的范围不用做特殊判断。举个例子假设有这样一个4×5的矩阵A [ [1, 0, 0, 2, 0], [0, 0, 3, 0, 0], [0, 4, 0, 0, 5], [0, 0, 0, 0, 0] ]按CSR存储就是values [1, 2, 3, 4, 5] col_indices [0, 3, 2, 1, 4] row_ptr [0, 2, 3, 5, 5]注意row_ptr的最后两个值都是5因为第4行索引3没有非零元素所以它的起始和结束偏移相同。这个细节在写遍历代码的时候特别重要如果不判断row_ptr[i] row_ptr[i1]就会把空行当成有元素处理。3.2 从COO转换到CSR的完整过程实际工作中我们通常先以COO格式收集数据因为插入方便然后再转换成CSR。这个转换过程是CSR构建的关键环节我详细拆一下步骤。假设我们已经有了COO格式的三元组列表按行号排序后的结果如下row [0, 0, 1, 2, 2] col [0, 3, 2, 1, 4] val [1, 2, 3, 4, 5]第一步统计每一行的非零元素个数。遍历row数组用计数器累加行0: 2个 行1: 1个 行2: 2个 行3: 0个第二步对计数做前缀和exclusive prefix sum得到row_ptrrow_ptr[0] 0 row_ptr[1] row_ptr[0] count[0] 0 2 2 row_ptr[2] row_ptr[1] count[1] 2 1 3 row_ptr[3] row_ptr[2] count[2] 3 2 5 row_ptr[4] row_ptr[3] count[3] 5 0 5第三步把col和val数组直接搬过来前提是COO已经按行排序。如果没有排序需要先按行号做稳定排序再按列号排序。这个转换过程的时间复杂度是O(nnz n)空间复杂度是O(nnz n 1)。在SciPy里一行代码就能完成from scipy.sparse import coo_matrix coo coo_matrix((val, (row, col)), shape(4, 5)) csr coo.tocsr()但如果你是自己实现一定要注意排序的稳定性。如果同一行内有多个元素列号必须是有序的否则后续的查找操作比如按列查找某个元素就没法用二分查找加速。3.3 CSR的SpMV运算为什么快SpMVSparse Matrix-Vector multiplication是稀疏矩阵最核心的运算之一CSR在这个运算上的表现非常出色。原因在于它的内存访问模式。用CSR做y A * x的伪代码是这样的for i in range(n): sum 0 for j in range(row_ptr[i], row_ptr[i1]): sum values[j] * x[col_indices[j]] y[i] sum外层循环按行遍历内层循环遍历该行的非零元素。values和col_indices都是连续访问的row_ptr也是顺序读取。唯一的不规则访问是x[col_indices[j]]这是一个gather操作但x通常比较小能放进缓存。相比之下如果用COO做SpMV你需要遍历所有三元组然后做y[row[k]] val[k] * x[col[k]]。这个操作是scatter-add存在写冲突的风险而且row数组的访问是跳跃的缓存不友好。实测数据在一个nnz约为100万的稀疏矩阵上CSR的SpMV比COO快大约2到3倍。矩阵越稀疏、行长度越不均匀差距越明显。3.4 CSR的实操注意事项第一个坑是空行的处理。前面提到过row_ptr[i] row_ptr[i1]表示第i行全为零。在写遍历代码的时候如果不做判断直接进入内层循环循环体会执行零次结果是对的但如果你在循环外做了什么假设比如假设每行至少有一个元素就会出错。第二个坑是索引类型的选择。当nnz超过2^31-1约21亿时32位整数会溢出。大型稀疏矩阵一定要用64位整数存索引。SciPy默认用int32超过20亿非零元素的时候需要手动指定int64。这个问题在中小规模测试时不会暴露一上生产环境就炸。第三个坑是重复元素的处理。COO转CSR的时候如果同一个位置有多个值SciPy默认会把它们加起来。这个行为在有限元分析里是正确的多个单元贡献叠加但如果你本意是覆盖就会得到错误结果。转换前一定要确认是否需要去重。实操心得构建CSR之前先用coo.sum_duplicates()或手动去重避免意外的数值叠加。这个坑我在一个图神经网络项目里踩过当时邻接矩阵的边权重被重复累加导致训练loss一直不收敛排查了整整一天才发现是重复元素的问题。4. CSC格式与CSR的对称设计4.1 CSC的本质就是转置的CSRCSC全称Compressed Sparse Column压缩稀疏列。它的结构和CSR完全对称只是把行和列的角色互换了values数组按列优先顺序存储非零元素的值。row_indices数组存储每个非零元素的行号。col_ptr数组存储每一列第一个非零元素的起始偏移长度为列数1。用一句话概括CSC(A) CSR(A的转置)。这个关系非常重要因为很多库在实现CSC的时候直接复用CSR的代码只是传入转置后的矩阵。还是用前面那个4×5的矩阵举例CSC存储是values [1, 4, 3, 2, 5] row_indices [0, 2, 1, 0, 2] col_ptr [0, 1, 2, 3, 5, 5]注意col_ptr的长度是列数16。第4列索引3有两个非零元素2和5第5列索引4没有非零元素所以col_ptr[4] col_ptr[5] 5。4.2 什么时候必须用CSCCSR适合按行操作的场景CSC适合按列操作的场景。具体来说下面这些情况必须用CSC场景一求解稀疏线性方程组。高斯消元、LU分解、Cholesky分解这些算法核心操作是按列消元。用CSC可以直接访问每一列的元素不用做转置。场景二列切片和列统计。如果你需要频繁提取某一列或者计算每列的和、均值、最大值CSC的效率远高于CSR。CSR提取一列需要遍历所有行时间复杂度O(nnz)而CSC只需要O(该列非零元素数)。场景三某些图算法。比如PageRank的反向传播需要按入边聚合这时候图的邻接矩阵用CSC存储更自然。4.3 CSR和CSC的转换代价CSR转CSC的代价不低本质上是一次矩阵转置操作。朴素实现的时间复杂度是O(nnz n m)需要额外的临时空间。SciPy的csr.tocsc()内部用的是计数排序的思路效率还可以但如果你在热循环里反复转换性能会急剧下降。我的建议是在数据预处理阶段就确定好需要哪种格式一次性转换到位不要在运行时反复转。如果确实需要同时支持行操作和列操作可以考虑同时存两份内存换时间或者用支持双向遍历的格式比如DCSC但实现复杂度高。注意CSR和CSC的转换不是免费的。在一个nnz为5000万的矩阵上一次tocsc()调用大约需要2到3秒。如果你的算法需要迭代1000次每次迭代都转一次那就是将近一个小时白白浪费在格式转换上。5. 其他存储格式的适用场景5.1 COO构建阶段的最佳选择COOCoordinate Format是最简单的稀疏矩阵格式就是三元组列表。它的优点是插入极其方便你只需要往数组末尾追加就行不需要维护任何索引结构。缺点是内存占用大每个元素要存row、col、val三个值而且不支持高效的算术运算。COO的典型用法是作为中间格式从文件读取数据、从网络接收数据、从用户输入收集数据的时候用COO收集完了再转成CSR或CSC。几乎所有稀疏矩阵库都支持COO到CSR/CSC的一键转换。5.2 ELLGPU上的规则化存储ELL格式的核心思想是如果每行的非零元素数量差不多那就用一个固定宽度的二维数组来存。假设最大行长度是max_nnz_per_rowELL就用两个n×max_nnz_per_row的数组一个存列号一个存数值。不足的部分用填充值补齐。ELL在GPU上的优势非常明显内存访问完全规则没有分支预测失败SIMD指令利用率高。但它的缺点也很致命如果矩阵的行长度差异很大比如有些行有1000个非零元素有些行只有1个填充造成的浪费会非常严重。实际使用中纯ELL很少见更多是HYBHybrid格式前K个对角线用ELL存剩下的用COO存。这样既利用了GPU的规则性优势又避免了极端情况下的空间浪费。5.3 DIA对角矩阵的专属方案DIADiagonal Format专门针对非零元素沿对角线分布的矩阵。它用两个二维数组一个存对角线上的数值一个存每条对角线的偏移量。对于三对角矩阵、带状矩阵这类结构DIA的空间效率极高而且SpMV可以用向量化指令加速。但DIA的适用范围很窄。一旦矩阵的非零元素偏离对角线DIA就会产生大量填充。所以它通常只用在特定领域比如求解偏微分方程时的差分格式。5.4 格式选型速查表格式内存效率插入效率SpMV效率GPU友好度适用场景COO低极高低低数据收集阶段CSR高低高中行遍历、SpMVCSC高低中中列遍历、线性求解ELL中低高极高行长度均匀的GPU计算DIA高低高高带状/对角矩阵HYB高低高极高不规则GPU计算这张表是我自己在多个项目里总结出来的不一定适用于所有情况但作为一个快速筛选的工具还是很好用的。6. 常见问题与排查技巧实录6.1 内存溢出但明明nnz不大这个问题我遇到过好几次。原因通常不是nnz本身大而是索引类型选错了。比如nnz只有500万但矩阵维度是100万×100万row_ptr数组就需要100万1个元素。如果用的是int64光row_ptr就占8MB加上col_indices和values总内存可能超过预期。排查方法先算一下理论内存占用。CSR的总内存大约是nnz * (sizeof(val) sizeof(idx)) (n1) * sizeof(idx)。如果实际占用远大于这个值检查是不是用了COO或LIL格式或者是不是有重复元素没去重。6.2 SpMV结果不对但矩阵看起来没问题最常见的原因是列索引没有排序。CSR格式要求每一行内的列索引是有序的但有些库在转换的时候不保证这一点。如果你的算法依赖有序性比如做二分查找就会得到错误结果。排查方法转换后检查np.all(np.diff(csr.indices) 0)但这个检查只对单行有效需要按行分段检查。更简单的方法是直接用csr.has_sorted_indices属性SciPy提供。6.3 矩阵乘法比预期慢很多稀疏矩阵乘法的性能高度依赖于稀疏结构。如果两个矩阵的稀疏模式不匹配结果矩阵可能会变得很稠密计算量暴增。比如两个对角矩阵相乘结果还是对角矩阵很快但两个随机稀疏矩阵相乘结果可能50%以上都是非零元素。排查方法先估算结果矩阵的nnz。如果结果nnz远大于输入nnz说明稀疏结构在乘法中丢失了这时候需要考虑用其他算法比如分块计算或者接受稠密化的事实。6.4 从文件读取稀疏矩阵时格式解析错误Matrix Market格式.mtx是最常见的稀疏矩阵交换格式但它的头部注释和维度行很容易解析错。常见问题包括把注释行当成数据行、维度顺序搞反是先行后列还是先列后行、索引从0开始还是从1开始。排查方法用SciPy的scipy.io.mmread()读取不要自己写解析器。如果必须自己写先打印前10行看看格式确认注释以%开头维度行的两个数字分别是行数和列数。实操心得处理Matrix Market文件时先用head -20 file.mtx看一眼文件头。我见过有的文件在维度行后面还有一行空的如果不跳过就会把空行当成第一个元素解析导致整个矩阵偏移一位。6.5 常见问题速查表问题现象可能原因排查方法解决方案内存溢出索引类型过大计算理论内存改用int32或压缩格式SpMV结果错误列索引未排序检查has_sorted_indices调用sort_indices()乘法极慢稀疏结构丢失估算结果nnz分块计算或换算法文件读取失败格式解析错误打印文件头用标准库读取转换耗时过长反复格式转换加计时器预处理阶段一次转换7. 实际项目中的性能调优经验7.1 分块CSR提升缓存命中率标准CSR在SpMV时x[col_indices[j]]是随机访问。如果矩阵很大x无法全部放进缓存每次访问都是一次内存读取。分块CSRBlocked CSR的思路是把矩阵按行分成若干块每块单独处理这样x的访问范围就限制在块内缓存命中率大幅提升。具体做法把行分成大小为B的块B通常取64到256对每个块先收集该块涉及的所有列号去重后加载对应的x值到临时数组然后再做乘加。这个优化在矩阵维度超过10万时效果明显实测SpMV可以提速30%到50%。7.2 选择合适的索引类型前面提过索引类型的问题这里展开说一下选择逻辑nnz 2^31-1 且 矩阵维度 2^31-1用int32省一半内存。nnz 2^31-1 或 矩阵维度 2^31-1必须用int64。不确定的时候先用int64开发性能测试后再决定是否降级到int32。SciPy的默认行为是尽量用int32但你可以通过csr_matrix((data, indices, indptr), dtypenp.float64, shape(m, n))显式指定。注意indices和indptr的类型要一致混用会导致隐式转换反而更慢。7.3 预分配和原地操作稀疏矩阵的很多操作比如加法、乘法会创建新矩阵。如果你的算法需要反复做这些操作内存分配和垃圾回收的开销会累积起来。解决办法是预分配结果矩阵用原地操作in-place operation填充。比如SpMV不要每次y A.dot(x)而是预分配y然后调用A.dot(x, outy)。SciPy的很多函数都支持out参数用好了能减少大量内存分配。7.4 对称矩阵的特殊处理如果矩阵是对称的只需要存上三角或下三角内存直接减半。SpMV的时候对每个非零元素(i, j, v)同时计算y[i] v * x[j]和y[j] v * x[i]。这个优化在有限元分析里特别常见因为刚度矩阵通常是对称的。但要注意对称存储只适用于对称矩阵。如果矩阵只是近似对称或者你只关心其中一个三角就不要用这个优化否则结果会错。8. 从零实现一个CSR构建器8.1 需求分析和接口设计为了把前面的理论串起来我带你从零实现一个CSR构建器。需求是输入COO格式的row、col、val三个数组输出CSR格式的values、col_indices、row_ptr三个数组。要求支持重复元素累加支持指定矩阵维度。接口设计def coo_to_csr(row, col, val, n_rows, n_cols): 将COO格式转换为CSR格式 参数: row: 行索引数组 col: 列索引数组 val: 数值数组 n_rows: 矩阵行数 n_cols: 矩阵列数 返回: values, col_indices, row_ptr 8.2 核心实现步骤第一步统计每行的非零元素个数row_counts np.zeros(n_rows, dtypenp.int64) for r in row: row_counts[r] 1第二步计算row_ptr前缀和row_ptr np.zeros(n_rows 1, dtypenp.int64) for i in range(n_rows): row_ptr[i1] row_ptr[i] row_counts[i]第三步填充values和col_indices。这里需要一个临时的位置数组记录每一行当前填充到哪个位置values np.zeros(len(val), dtypeval.dtype) col_indices np.zeros(len(col), dtypenp.int64) pos row_ptr[:-1].copy() for k in range(len(val)): r row[k] idx pos[r] values[idx] val[k] col_indices[idx] col[k] pos[r] 1第四步对每一行内的列索引排序。如果COO输入已经按行和列排序这一步可以跳过for i in range(n_rows): start, end row_ptr[i], row_ptr[i1] if end - start 1: order np.argsort(col_indices[start:end]) col_indices[start:end] col_indices[start:end][order] values[start:end] values[start:end][order]8.3 处理重复元素如果同一个位置有多个值上面的实现会保留所有值不会自动累加。要支持累加需要在排序后做一次合并def merge_duplicates(values, col_indices, row_ptr): new_values [] new_col_indices [] new_row_ptr [0] for i in range(len(row_ptr) - 1): start, end row_ptr[i], row_ptr[i1] if start end: new_row_ptr.append(len(new_values)) continue prev_col col_indices[start] prev_val values[start] for j in range(start 1, end): if col_indices[j] prev_col: prev_val values[j] else: new_values.append(prev_val) new_col_indices.append(prev_col) prev_col col_indices[j] prev_val values[j] new_values.append(prev_val) new_col_indices.append(prev_col) new_row_ptr.append(len(new_values)) return np.array(new_values), np.array(new_col_indices), np.array(new_row_ptr)8.4 性能测试和优化上面的实现在Python层面用了循环对于大规模数据会很慢。优化方向有两个方向一用NumPy向量化操作替代循环。统计行数可以用np.bincount(row, minlengthn_rows)前缀和可以用np.cumsum填充可以用np.argsort配合花式索引。方向二用Cython或Numba加速。如果必须用循环用Numba的jit装饰器可以把性能提升几十倍。我实测过一个nnz为1000万的矩阵纯Python实现需要约30秒Numba加速后只需要0.5秒。from numba import jit jit(nopythonTrue) def coo_to_csr_numba(row, col, val, n_rows): row_counts np.zeros(n_rows, dtypenp.int64) for r in row: row_counts[r] 1 row_ptr np.zeros(n_rows 1, dtypenp.int64) for i in range(n_rows): row_ptr[i1] row_ptr[i] row_counts[i] values np.zeros(len(val), dtypeval.dtype) col_indices np.zeros(len(col), dtypenp.int64) pos row_ptr[:-1].copy() for k in range(len(val)): r row[k] idx pos[r] values[idx] val[k] col_indices[idx] col[k] pos[r] 1 return values, col_indices, row_ptr实操心得Numba的jit第一次调用会有编译开销大约1到2秒。如果你的函数只调用一次编译开销可能比计算本身还大。解决办法是用jit(cacheTrue)把编译结果缓存到磁盘第二次启动就不用重新编译了。9. 稀疏矩阵在真实场景中的应用9.1 图计算中的邻接矩阵图计算是稀疏矩阵最典型的应用场景。一个包含N个节点的图邻接矩阵是N×N的但每个节点的平均度数通常远小于N。用CSR存储邻接矩阵SpMV就对应图上的消息传递操作。比如PageRank算法核心迭代就是r alpha * A * r (1-alpha) * e其中A是转移矩阵。用CSR做SpMV每次迭代的时间复杂度是O(nnz)而不是O(N^2)。在一个包含1000万节点、平均度数100的图上nnz约为10亿用CSR做一次迭代大约需要几秒钟而稠密矩阵根本存不下。9.2 推荐系统中的用户-物品矩阵推荐系统的用户-物品交互矩阵通常是极度稀疏的。比如一个电商平台有1亿用户和1000万商品但每个用户平均只交互过几十个商品稀疏度超过99.999%。用CSR存储这个矩阵内存占用从PB级别降到GB级别。矩阵分解如ALS、SGD是推荐系统的核心算法它的每一步迭代都涉及稀疏矩阵的乘法。CSR和CSC的选型在这里很关键计算用户向量时按行访问用CSR计算物品向量时按列访问用CSC。很多推荐系统框架会同时维护两份存储用内存换速度。9.3 有限元分析中的刚度矩阵有限元分析里的刚度矩阵是对称正定的而且非零元素集中在对角线附近。用CSC存储配合Cholesky分解可以高效求解大规模线性方程组。一个典型的汽车碰撞仿真模型刚度矩阵的维度可能达到千万级别nnz在亿级别用稀疏求解器可以在几分钟内完成求解而稠密求解器需要几天。9.4 自然语言处理中的词共现矩阵词共现矩阵是NLP里的经典数据结构行和列都是词表元素是两个词在语料中共同出现的次数。这个矩阵的维度可能达到百万级别但每个词平均只和几百个词共现。用CSR存储后可以做LSA、GloVe等词向量训练效率比稠密矩阵高几个数量级。10. 稀疏矩阵存储格式的未来演进10.1 异构计算带来的新挑战GPU和TPU的普及对稀疏矩阵存储提出了新要求。传统CSR在GPU上的表现不如CPU因为GPU的SIMT架构要求线程束内的线程执行相同的指令而CSR的行长度不规则导致线程束分化。解决方案包括按行长度排序后再计算、用ELL格式做规则化、用HYB格式混合存储。10.2 压缩感知与稀疏表示压缩感知理论告诉我们如果信号在某个变换域是稀疏的就可以用远少于奈奎斯特采样定理要求的样本数恢复信号。这个理论对稀疏矩阵存储的启发是稀疏性不仅是一种存储优化更是一种信息表示方式。未来的稀疏矩阵库可能会集成更多的压缩感知算法把存储和计算更紧密地结合起来。10.3 自动格式选择现在选存储格式还需要人工判断未来可能会出现自动格式选择系统根据矩阵的稀疏模式、运算类型、硬件平台自动选择最优格式。实际上一些研究项目已经在做这件事比如用机器学习模型预测不同格式的性能然后自动切换。这个方向我觉得很有前景但离工业级落地还有距离。我在实际项目里的体会是稀疏矩阵的选型和调优没有银弹。同一个矩阵在不同的硬件、不同的运算、不同的数据分布下最优格式可能完全不同。唯一可靠的办法是理解每种格式的底层原理在自己的场景里做基准测试用数据说话。踩过的坑多了自然就有直觉了。 稀疏矩阵存储格式详解：CSR、CSC、COO、ELL、DIA选型指南
1. 稀疏矩阵到底在解决什么问题第一次接触稀疏矩阵很多人会误以为它只是一种“特殊矩阵”的数学分类。其实不是。它本质上是一个工程问题催生出来的数据结构方案。当你用程序去处理一个10000×10000的矩阵时如果老老实实开一个二维数组那就是一亿个浮点数按双精度8字节算光内存就要吃掉约800MB。但实际情况是这个矩阵里可能只有不到1%的位置有非零值剩下99%全是零。你花了800MB内存结果存的全是“什么都没有”。这就是稀疏矩阵要解决的核心矛盾矩阵的数学维度很大但有效信息密度极低。在有限元分析、图计算、推荐系统、自然语言处理、计算流体力学这些领域这种“大而空”的矩阵几乎是标配。比如一个社交网络的邻接矩阵用户数量可能上千万但每个用户平均只关注几百人邻接矩阵的稀疏度通常在99.99%以上。所以稀疏矩阵的核心思路就一句话只存非零元素零元素不存但通过索引结构保证你还能找到每个非零元素在原始矩阵中的位置。听起来简单但真正落地的时候索引怎么组织、按行还是按列、排序怎么处理、矩阵乘法怎么加速每一个选择都会直接影响性能和内存占用。这篇文章我会从存储格式的底层设计讲起把CSR、CSC、COO、ELL、DIA这些常见格式的来龙去脉拆开配合实际的参数计算、代码示例和踩坑经验让你看完之后能根据自己手头的场景直接选型而不是对着文档照抄。注意网上搜“csr是什么简写”的时候会看到两个完全不同的答案。一个是Compressed Sparse Row压缩稀疏行另一个是Cloudflare的Certificate Signing Request证书签名请求。这两个东西没有任何关系只是缩写撞车了。本文只讨论前者后者属于网络安全领域的证书管理话题不在本文范围内。2. 稀疏矩阵存储格式的整体设计思路2.1 为什么不能直接用哈希表存有人可能会想既然只存非零元素那我用一个哈希表key是(row, col)value是数值不就行了吗小规模确实可以但一旦上规模就会出问题。哈希表的问题在于第一内存开销大每个键值对都有额外的哈希桶、指针、负载因子预留空间实际内存占用可能是原始数据的3到5倍第二遍历顺序不可控做矩阵乘法的时候需要按行或按列有序访问哈希表做不到第三缓存局部性差每次访问都是一次随机内存跳转CPU缓存命中率极低。所以工业级的稀疏矩阵库比如SuiteSparse、Eigen、SciPy的sparse模块都不会用哈希表作为底层存储。它们用的是压缩索引结构核心思想是把二维坐标拆成“主索引偏移量”的形式用连续数组存储保证内存紧凑和遍历有序。2.2 三种基础设计维度所有稀疏矩阵存储格式本质上都是在三个维度上做取舍第一个维度是索引的压缩程度。最原始的方式是坐标格式COO每个非零元素存一个(row, col, value)三元组。这种方式最直观但索引占用的空间可能比数值本身还大。压缩格式CSR/CSC则通过行指针数组把行索引压缩掉只保留列索引和数值。第二个维度是访问模式。按行压缩CSR适合行遍历和SpMV稀疏矩阵乘向量按列压缩CSC适合列遍历和求解线性方程组时的列操作。选错了方向性能可能差好几倍。第三个维度是规则性。如果每行的非零元素数量差不多可以用ELL格式把索引和数值排成固定宽度的二维数组GPU上特别友好。如果非零元素沿对角线分布DIA格式最省空间。但现实中的矩阵往往是不规则的所以CSR/CSC成了通用性最强的选择。2.3 选型决策的核心逻辑我在实际项目里选存储格式的时候会按下面这个顺序问自己几个问题这个矩阵是只读的还是需要频繁修改如果频繁插入新元素COO或LILList of Lists更合适CSR/CSC的插入代价很高。主要做什么运算SpMV选CSR求解器选CSC矩阵乘法看情况可能需要混合。是否跑在GPU上GPU上ELL或HYB混合格式往往比纯CSR更快。矩阵规模多大小规模非零元素少于10万其实用什么都差不多大规模才需要精细选型。这个决策逻辑贯穿全文后面讲每种格式的时候我都会回到这几个问题上。3. CSR格式深度拆解与实操3.1 CSR的三个核心数组CSR全称Compressed Sparse Row翻译过来就是压缩稀疏行。它的核心是用三个一维数组来表示整个矩阵values数组按行优先顺序存储所有非零元素的值长度等于非零元素总数nnz。col_indices数组存储每个非零元素对应的列号长度也是nnz。row_ptr数组存储每一行第一个非零元素在values中的起始位置长度是行数1。row_ptr的设计是整个CSR的精髓。它的第i个元素表示第i行的起始偏移第i1个元素表示第i行的结束偏移同时也是第i1行的起始偏移。所以第i行的非零元素就是values[row_ptr[i]]到values[row_ptr[i1]-1]这一段。最后一个元素row_ptr[n]恒等于nnz这样设计是为了方便计算最后一行的范围不用做特殊判断。举个例子假设有这样一个4×5的矩阵A [ [1, 0, 0, 2, 0], [0, 0, 3, 0, 0], [0, 4, 0, 0, 5], [0, 0, 0, 0, 0] ]按CSR存储就是values [1, 2, 3, 4, 5] col_indices [0, 3, 2, 1, 4] row_ptr [0, 2, 3, 5, 5]注意row_ptr的最后两个值都是5因为第4行索引3没有非零元素所以它的起始和结束偏移相同。这个细节在写遍历代码的时候特别重要如果不判断row_ptr[i] row_ptr[i1]就会把空行当成有元素处理。3.2 从COO转换到CSR的完整过程实际工作中我们通常先以COO格式收集数据因为插入方便然后再转换成CSR。这个转换过程是CSR构建的关键环节我详细拆一下步骤。假设我们已经有了COO格式的三元组列表按行号排序后的结果如下row [0, 0, 1, 2, 2] col [0, 3, 2, 1, 4] val [1, 2, 3, 4, 5]第一步统计每一行的非零元素个数。遍历row数组用计数器累加行0: 2个 行1: 1个 行2: 2个 行3: 0个第二步对计数做前缀和exclusive prefix sum得到row_ptrrow_ptr[0] 0 row_ptr[1] row_ptr[0] count[0] 0 2 2 row_ptr[2] row_ptr[1] count[1] 2 1 3 row_ptr[3] row_ptr[2] count[2] 3 2 5 row_ptr[4] row_ptr[3] count[3] 5 0 5第三步把col和val数组直接搬过来前提是COO已经按行排序。如果没有排序需要先按行号做稳定排序再按列号排序。这个转换过程的时间复杂度是O(nnz n)空间复杂度是O(nnz n 1)。在SciPy里一行代码就能完成from scipy.sparse import coo_matrix coo coo_matrix((val, (row, col)), shape(4, 5)) csr coo.tocsr()但如果你是自己实现一定要注意排序的稳定性。如果同一行内有多个元素列号必须是有序的否则后续的查找操作比如按列查找某个元素就没法用二分查找加速。3.3 CSR的SpMV运算为什么快SpMVSparse Matrix-Vector multiplication是稀疏矩阵最核心的运算之一CSR在这个运算上的表现非常出色。原因在于它的内存访问模式。用CSR做y A * x的伪代码是这样的for i in range(n): sum 0 for j in range(row_ptr[i], row_ptr[i1]): sum values[j] * x[col_indices[j]] y[i] sum外层循环按行遍历内层循环遍历该行的非零元素。values和col_indices都是连续访问的row_ptr也是顺序读取。唯一的不规则访问是x[col_indices[j]]这是一个gather操作但x通常比较小能放进缓存。相比之下如果用COO做SpMV你需要遍历所有三元组然后做y[row[k]] val[k] * x[col[k]]。这个操作是scatter-add存在写冲突的风险而且row数组的访问是跳跃的缓存不友好。实测数据在一个nnz约为100万的稀疏矩阵上CSR的SpMV比COO快大约2到3倍。矩阵越稀疏、行长度越不均匀差距越明显。3.4 CSR的实操注意事项第一个坑是空行的处理。前面提到过row_ptr[i] row_ptr[i1]表示第i行全为零。在写遍历代码的时候如果不做判断直接进入内层循环循环体会执行零次结果是对的但如果你在循环外做了什么假设比如假设每行至少有一个元素就会出错。第二个坑是索引类型的选择。当nnz超过2^31-1约21亿时32位整数会溢出。大型稀疏矩阵一定要用64位整数存索引。SciPy默认用int32超过20亿非零元素的时候需要手动指定int64。这个问题在中小规模测试时不会暴露一上生产环境就炸。第三个坑是重复元素的处理。COO转CSR的时候如果同一个位置有多个值SciPy默认会把它们加起来。这个行为在有限元分析里是正确的多个单元贡献叠加但如果你本意是覆盖就会得到错误结果。转换前一定要确认是否需要去重。实操心得构建CSR之前先用coo.sum_duplicates()或手动去重避免意外的数值叠加。这个坑我在一个图神经网络项目里踩过当时邻接矩阵的边权重被重复累加导致训练loss一直不收敛排查了整整一天才发现是重复元素的问题。4. CSC格式与CSR的对称设计4.1 CSC的本质就是转置的CSRCSC全称Compressed Sparse Column压缩稀疏列。它的结构和CSR完全对称只是把行和列的角色互换了values数组按列优先顺序存储非零元素的值。row_indices数组存储每个非零元素的行号。col_ptr数组存储每一列第一个非零元素的起始偏移长度为列数1。用一句话概括CSC(A) CSR(A的转置)。这个关系非常重要因为很多库在实现CSC的时候直接复用CSR的代码只是传入转置后的矩阵。还是用前面那个4×5的矩阵举例CSC存储是values [1, 4, 3, 2, 5] row_indices [0, 2, 1, 0, 2] col_ptr [0, 1, 2, 3, 5, 5]注意col_ptr的长度是列数16。第4列索引3有两个非零元素2和5第5列索引4没有非零元素所以col_ptr[4] col_ptr[5] 5。4.2 什么时候必须用CSCCSR适合按行操作的场景CSC适合按列操作的场景。具体来说下面这些情况必须用CSC场景一求解稀疏线性方程组。高斯消元、LU分解、Cholesky分解这些算法核心操作是按列消元。用CSC可以直接访问每一列的元素不用做转置。场景二列切片和列统计。如果你需要频繁提取某一列或者计算每列的和、均值、最大值CSC的效率远高于CSR。CSR提取一列需要遍历所有行时间复杂度O(nnz)而CSC只需要O(该列非零元素数)。场景三某些图算法。比如PageRank的反向传播需要按入边聚合这时候图的邻接矩阵用CSC存储更自然。4.3 CSR和CSC的转换代价CSR转CSC的代价不低本质上是一次矩阵转置操作。朴素实现的时间复杂度是O(nnz n m)需要额外的临时空间。SciPy的csr.tocsc()内部用的是计数排序的思路效率还可以但如果你在热循环里反复转换性能会急剧下降。我的建议是在数据预处理阶段就确定好需要哪种格式一次性转换到位不要在运行时反复转。如果确实需要同时支持行操作和列操作可以考虑同时存两份内存换时间或者用支持双向遍历的格式比如DCSC但实现复杂度高。注意CSR和CSC的转换不是免费的。在一个nnz为5000万的矩阵上一次tocsc()调用大约需要2到3秒。如果你的算法需要迭代1000次每次迭代都转一次那就是将近一个小时白白浪费在格式转换上。5. 其他存储格式的适用场景5.1 COO构建阶段的最佳选择COOCoordinate Format是最简单的稀疏矩阵格式就是三元组列表。它的优点是插入极其方便你只需要往数组末尾追加就行不需要维护任何索引结构。缺点是内存占用大每个元素要存row、col、val三个值而且不支持高效的算术运算。COO的典型用法是作为中间格式从文件读取数据、从网络接收数据、从用户输入收集数据的时候用COO收集完了再转成CSR或CSC。几乎所有稀疏矩阵库都支持COO到CSR/CSC的一键转换。5.2 ELLGPU上的规则化存储ELL格式的核心思想是如果每行的非零元素数量差不多那就用一个固定宽度的二维数组来存。假设最大行长度是max_nnz_per_rowELL就用两个n×max_nnz_per_row的数组一个存列号一个存数值。不足的部分用填充值补齐。ELL在GPU上的优势非常明显内存访问完全规则没有分支预测失败SIMD指令利用率高。但它的缺点也很致命如果矩阵的行长度差异很大比如有些行有1000个非零元素有些行只有1个填充造成的浪费会非常严重。实际使用中纯ELL很少见更多是HYBHybrid格式前K个对角线用ELL存剩下的用COO存。这样既利用了GPU的规则性优势又避免了极端情况下的空间浪费。5.3 DIA对角矩阵的专属方案DIADiagonal Format专门针对非零元素沿对角线分布的矩阵。它用两个二维数组一个存对角线上的数值一个存每条对角线的偏移量。对于三对角矩阵、带状矩阵这类结构DIA的空间效率极高而且SpMV可以用向量化指令加速。但DIA的适用范围很窄。一旦矩阵的非零元素偏离对角线DIA就会产生大量填充。所以它通常只用在特定领域比如求解偏微分方程时的差分格式。5.4 格式选型速查表格式内存效率插入效率SpMV效率GPU友好度适用场景COO低极高低低数据收集阶段CSR高低高中行遍历、SpMVCSC高低中中列遍历、线性求解ELL中低高极高行长度均匀的GPU计算DIA高低高高带状/对角矩阵HYB高低高极高不规则GPU计算这张表是我自己在多个项目里总结出来的不一定适用于所有情况但作为一个快速筛选的工具还是很好用的。6. 常见问题与排查技巧实录6.1 内存溢出但明明nnz不大这个问题我遇到过好几次。原因通常不是nnz本身大而是索引类型选错了。比如nnz只有500万但矩阵维度是100万×100万row_ptr数组就需要100万1个元素。如果用的是int64光row_ptr就占8MB加上col_indices和values总内存可能超过预期。排查方法先算一下理论内存占用。CSR的总内存大约是nnz * (sizeof(val) sizeof(idx)) (n1) * sizeof(idx)。如果实际占用远大于这个值检查是不是用了COO或LIL格式或者是不是有重复元素没去重。6.2 SpMV结果不对但矩阵看起来没问题最常见的原因是列索引没有排序。CSR格式要求每一行内的列索引是有序的但有些库在转换的时候不保证这一点。如果你的算法依赖有序性比如做二分查找就会得到错误结果。排查方法转换后检查np.all(np.diff(csr.indices) 0)但这个检查只对单行有效需要按行分段检查。更简单的方法是直接用csr.has_sorted_indices属性SciPy提供。6.3 矩阵乘法比预期慢很多稀疏矩阵乘法的性能高度依赖于稀疏结构。如果两个矩阵的稀疏模式不匹配结果矩阵可能会变得很稠密计算量暴增。比如两个对角矩阵相乘结果还是对角矩阵很快但两个随机稀疏矩阵相乘结果可能50%以上都是非零元素。排查方法先估算结果矩阵的nnz。如果结果nnz远大于输入nnz说明稀疏结构在乘法中丢失了这时候需要考虑用其他算法比如分块计算或者接受稠密化的事实。6.4 从文件读取稀疏矩阵时格式解析错误Matrix Market格式.mtx是最常见的稀疏矩阵交换格式但它的头部注释和维度行很容易解析错。常见问题包括把注释行当成数据行、维度顺序搞反是先行后列还是先列后行、索引从0开始还是从1开始。排查方法用SciPy的scipy.io.mmread()读取不要自己写解析器。如果必须自己写先打印前10行看看格式确认注释以%开头维度行的两个数字分别是行数和列数。实操心得处理Matrix Market文件时先用head -20 file.mtx看一眼文件头。我见过有的文件在维度行后面还有一行空的如果不跳过就会把空行当成第一个元素解析导致整个矩阵偏移一位。6.5 常见问题速查表问题现象可能原因排查方法解决方案内存溢出索引类型过大计算理论内存改用int32或压缩格式SpMV结果错误列索引未排序检查has_sorted_indices调用sort_indices()乘法极慢稀疏结构丢失估算结果nnz分块计算或换算法文件读取失败格式解析错误打印文件头用标准库读取转换耗时过长反复格式转换加计时器预处理阶段一次转换7. 实际项目中的性能调优经验7.1 分块CSR提升缓存命中率标准CSR在SpMV时x[col_indices[j]]是随机访问。如果矩阵很大x无法全部放进缓存每次访问都是一次内存读取。分块CSRBlocked CSR的思路是把矩阵按行分成若干块每块单独处理这样x的访问范围就限制在块内缓存命中率大幅提升。具体做法把行分成大小为B的块B通常取64到256对每个块先收集该块涉及的所有列号去重后加载对应的x值到临时数组然后再做乘加。这个优化在矩阵维度超过10万时效果明显实测SpMV可以提速30%到50%。7.2 选择合适的索引类型前面提过索引类型的问题这里展开说一下选择逻辑nnz 2^31-1 且 矩阵维度 2^31-1用int32省一半内存。nnz 2^31-1 或 矩阵维度 2^31-1必须用int64。不确定的时候先用int64开发性能测试后再决定是否降级到int32。SciPy的默认行为是尽量用int32但你可以通过csr_matrix((data, indices, indptr), dtypenp.float64, shape(m, n))显式指定。注意indices和indptr的类型要一致混用会导致隐式转换反而更慢。7.3 预分配和原地操作稀疏矩阵的很多操作比如加法、乘法会创建新矩阵。如果你的算法需要反复做这些操作内存分配和垃圾回收的开销会累积起来。解决办法是预分配结果矩阵用原地操作in-place operation填充。比如SpMV不要每次y A.dot(x)而是预分配y然后调用A.dot(x, outy)。SciPy的很多函数都支持out参数用好了能减少大量内存分配。7.4 对称矩阵的特殊处理如果矩阵是对称的只需要存上三角或下三角内存直接减半。SpMV的时候对每个非零元素(i, j, v)同时计算y[i] v * x[j]和y[j] v * x[i]。这个优化在有限元分析里特别常见因为刚度矩阵通常是对称的。但要注意对称存储只适用于对称矩阵。如果矩阵只是近似对称或者你只关心其中一个三角就不要用这个优化否则结果会错。8. 从零实现一个CSR构建器8.1 需求分析和接口设计为了把前面的理论串起来我带你从零实现一个CSR构建器。需求是输入COO格式的row、col、val三个数组输出CSR格式的values、col_indices、row_ptr三个数组。要求支持重复元素累加支持指定矩阵维度。接口设计def coo_to_csr(row, col, val, n_rows, n_cols): 将COO格式转换为CSR格式 参数: row: 行索引数组 col: 列索引数组 val: 数值数组 n_rows: 矩阵行数 n_cols: 矩阵列数 返回: values, col_indices, row_ptr 8.2 核心实现步骤第一步统计每行的非零元素个数row_counts np.zeros(n_rows, dtypenp.int64) for r in row: row_counts[r] 1第二步计算row_ptr前缀和row_ptr np.zeros(n_rows 1, dtypenp.int64) for i in range(n_rows): row_ptr[i1] row_ptr[i] row_counts[i]第三步填充values和col_indices。这里需要一个临时的位置数组记录每一行当前填充到哪个位置values np.zeros(len(val), dtypeval.dtype) col_indices np.zeros(len(col), dtypenp.int64) pos row_ptr[:-1].copy() for k in range(len(val)): r row[k] idx pos[r] values[idx] val[k] col_indices[idx] col[k] pos[r] 1第四步对每一行内的列索引排序。如果COO输入已经按行和列排序这一步可以跳过for i in range(n_rows): start, end row_ptr[i], row_ptr[i1] if end - start 1: order np.argsort(col_indices[start:end]) col_indices[start:end] col_indices[start:end][order] values[start:end] values[start:end][order]8.3 处理重复元素如果同一个位置有多个值上面的实现会保留所有值不会自动累加。要支持累加需要在排序后做一次合并def merge_duplicates(values, col_indices, row_ptr): new_values [] new_col_indices [] new_row_ptr [0] for i in range(len(row_ptr) - 1): start, end row_ptr[i], row_ptr[i1] if start end: new_row_ptr.append(len(new_values)) continue prev_col col_indices[start] prev_val values[start] for j in range(start 1, end): if col_indices[j] prev_col: prev_val values[j] else: new_values.append(prev_val) new_col_indices.append(prev_col) prev_col col_indices[j] prev_val values[j] new_values.append(prev_val) new_col_indices.append(prev_col) new_row_ptr.append(len(new_values)) return np.array(new_values), np.array(new_col_indices), np.array(new_row_ptr)8.4 性能测试和优化上面的实现在Python层面用了循环对于大规模数据会很慢。优化方向有两个方向一用NumPy向量化操作替代循环。统计行数可以用np.bincount(row, minlengthn_rows)前缀和可以用np.cumsum填充可以用np.argsort配合花式索引。方向二用Cython或Numba加速。如果必须用循环用Numba的jit装饰器可以把性能提升几十倍。我实测过一个nnz为1000万的矩阵纯Python实现需要约30秒Numba加速后只需要0.5秒。from numba import jit jit(nopythonTrue) def coo_to_csr_numba(row, col, val, n_rows): row_counts np.zeros(n_rows, dtypenp.int64) for r in row: row_counts[r] 1 row_ptr np.zeros(n_rows 1, dtypenp.int64) for i in range(n_rows): row_ptr[i1] row_ptr[i] row_counts[i] values np.zeros(len(val), dtypeval.dtype) col_indices np.zeros(len(col), dtypenp.int64) pos row_ptr[:-1].copy() for k in range(len(val)): r row[k] idx pos[r] values[idx] val[k] col_indices[idx] col[k] pos[r] 1 return values, col_indices, row_ptr实操心得Numba的jit第一次调用会有编译开销大约1到2秒。如果你的函数只调用一次编译开销可能比计算本身还大。解决办法是用jit(cacheTrue)把编译结果缓存到磁盘第二次启动就不用重新编译了。9. 稀疏矩阵在真实场景中的应用9.1 图计算中的邻接矩阵图计算是稀疏矩阵最典型的应用场景。一个包含N个节点的图邻接矩阵是N×N的但每个节点的平均度数通常远小于N。用CSR存储邻接矩阵SpMV就对应图上的消息传递操作。比如PageRank算法核心迭代就是r alpha * A * r (1-alpha) * e其中A是转移矩阵。用CSR做SpMV每次迭代的时间复杂度是O(nnz)而不是O(N^2)。在一个包含1000万节点、平均度数100的图上nnz约为10亿用CSR做一次迭代大约需要几秒钟而稠密矩阵根本存不下。9.2 推荐系统中的用户-物品矩阵推荐系统的用户-物品交互矩阵通常是极度稀疏的。比如一个电商平台有1亿用户和1000万商品但每个用户平均只交互过几十个商品稀疏度超过99.999%。用CSR存储这个矩阵内存占用从PB级别降到GB级别。矩阵分解如ALS、SGD是推荐系统的核心算法它的每一步迭代都涉及稀疏矩阵的乘法。CSR和CSC的选型在这里很关键计算用户向量时按行访问用CSR计算物品向量时按列访问用CSC。很多推荐系统框架会同时维护两份存储用内存换速度。9.3 有限元分析中的刚度矩阵有限元分析里的刚度矩阵是对称正定的而且非零元素集中在对角线附近。用CSC存储配合Cholesky分解可以高效求解大规模线性方程组。一个典型的汽车碰撞仿真模型刚度矩阵的维度可能达到千万级别nnz在亿级别用稀疏求解器可以在几分钟内完成求解而稠密求解器需要几天。9.4 自然语言处理中的词共现矩阵词共现矩阵是NLP里的经典数据结构行和列都是词表元素是两个词在语料中共同出现的次数。这个矩阵的维度可能达到百万级别但每个词平均只和几百个词共现。用CSR存储后可以做LSA、GloVe等词向量训练效率比稠密矩阵高几个数量级。10. 稀疏矩阵存储格式的未来演进10.1 异构计算带来的新挑战GPU和TPU的普及对稀疏矩阵存储提出了新要求。传统CSR在GPU上的表现不如CPU因为GPU的SIMT架构要求线程束内的线程执行相同的指令而CSR的行长度不规则导致线程束分化。解决方案包括按行长度排序后再计算、用ELL格式做规则化、用HYB格式混合存储。10.2 压缩感知与稀疏表示压缩感知理论告诉我们如果信号在某个变换域是稀疏的就可以用远少于奈奎斯特采样定理要求的样本数恢复信号。这个理论对稀疏矩阵存储的启发是稀疏性不仅是一种存储优化更是一种信息表示方式。未来的稀疏矩阵库可能会集成更多的压缩感知算法把存储和计算更紧密地结合起来。10.3 自动格式选择现在选存储格式还需要人工判断未来可能会出现自动格式选择系统根据矩阵的稀疏模式、运算类型、硬件平台自动选择最优格式。实际上一些研究项目已经在做这件事比如用机器学习模型预测不同格式的性能然后自动切换。这个方向我觉得很有前景但离工业级落地还有距离。我在实际项目里的体会是稀疏矩阵的选型和调优没有银弹。同一个矩阵在不同的硬件、不同的运算、不同的数据分布下最优格式可能完全不同。唯一可靠的办法是理解每种格式的底层原理在自己的场景里做基准测试用数据说话。踩过的坑多了自然就有直觉了。