我正在处理需要确定其零空间的大型、稀疏、有理矩阵。目前，我有一个大约 12000x12000（但不是正方形），其中每 2000 个元素中有一个是非零的。后续矩阵的大小和稀疏度都会增长。
大多数零空间算法依赖于将矩阵引入（某种形式）简化的行梯形形式，然后从该形式中读取零空间向量。由于这些算法需要大量的基本行操作，我认为使用压缩行存储是最好的选择，因为它可以轻松访问整行，这是行操作所需要的。
但是，作为这些操作的一部分，有时需要在稀疏矩阵中插入元素。现在，据我了解，当矩阵的大小增加时，在 CRS 矩阵中插入元素变得越来越昂贵。存储或零空间算法是否有其他选项可以避免此问题？
tl;dr ：使用列表格式，重新排序矩阵，使用 sympy。
您可以使用不同的稀疏矩阵存储方案，例如list-of-lists 格式，它允许快速插入新的矩阵条目，但缓存一致性较差。一旦找到矩阵的梯形形式，您就可以将低效的存储方案转换回 CRS。
通过减少您遇到的填充量，排列矩阵的条目可以产生巨大的差异。Cuthill -McKee 排序相当普遍，通过对底层稀疏图进行广度优先搜索，按照访问未知数的顺序重新排序矩阵。这倾向于将所有未知数聚集在靠近矩阵对角线的位置。或者，您可以使用近似最小度数算法，您可以在 MATLAB 中使用函数symamd. deal.II 库的文档对一堆不同的重新排序方案进行了非常棒的比较，但我似乎找不到它。
确定矩阵的简化梯队形式的连通性结构基本上是图论的一个问题，您不需要知道实际的矩阵条目（参见戴维斯关于稀疏直接方法的书）。因此，您可以首先在矩阵的梯形形式中找到哪些条目是非零的，然后才执行计算，内容是您不必添加任何新的非零条目。
据我所知，更常见的计算库不支持精确的有理算术，只支持浮点。如果你喜欢 Python，sympy包可以做精确的有理算术并且对稀疏矩阵有一些支持。