如何避免在 scipy 稀疏矩阵中插入不必要的零
How to avoid inserting unnecessary zeroes in a scipy sparse matrix
我正在研究一个由线性系统建模的问题，它可以写成方块三对角矩阵。这些块的大小为 b = 4n+8，整个矩阵的大小为 Nb； N 可以任意大（当然是合理的），同时 n 保持相当小（通常小于 10）。
块本身是稀疏的，第一个对角线只有单位矩阵，第二个对角线每个块只有 n+1 个非零列（所以 3n+7 个零列）。这些列是连续的，要么是零，要么是非零，或者相反。
在内存中构建所有这些块会产生一个 3N-2 x b x b 数组，该数组可以用 scipy.sparse.bsr_matrix 转换为稀疏矩阵，然后转换为 CSR 格式并修剪掉多余的零。它工作得很好，但我宁愿跳过这个临时的大而稀疏的数组（对于 N = 1e4，n = 5，每个相关条目都是 5.6 个零！）。
- 我看过 scipy.sparse.dok_matrix，推荐用于切片和增量构建。创建我的条目适合一个整洁的循环，但这个过程比使用 bsr_matrix 和我不必要的密集数组长约 10 倍，这将对未来的用例不利。
- 似乎 bsr_matrix 不能直接使用 scipy 稀疏矩阵作为输入。
- 使用 bsr_matrix 不包括 包括对角线块，然后添加稀疏眼大大减少零的数量（我的测试配置中每个相关条目 3.5 个）[=与原始解决方案相比，27=]和 将过程加快了三分之一。得分！
关于我可以做些什么来进一步减少这个矩阵的原始印记的任何线索？明显的目标是让我在选择 N 时有更多的自由。
编辑
我通过分别构建三个块对角线设法改进了一点点。通过这样做，我的第二条对角线需要更少的填充（n+3 而不是 3n+7；每个相关条目 1.3 个零），将我的原始块分成两个垂直块（一个全是零）和 我一次只需要一个对角线，最重要的是将内存成本减半。主对角线仍然是用眼睛方法构造的。锦上添花：与我的第 3 个要点相比，速度提高了 25%，这可能是因为分离两条第 2 对角线节省了使用 bsr_matrix 之前所需的一些数组重塑操作。与原始方法相比，对于我的 (N, n) = (1e4, 5) 测试用例，它在修剪前比较矩阵时节省了约 2000 万个零。每个 128 位，已经是一个不错的增益了！
我现在能想到的唯一可能的改进是分别构建这些对角线，不进行任何填充，然后插入零列（可能通过具有块矩阵的乘积），最后将所有内容加在一起。
我还阅读了一些关于使用 dict 更新空 dok_matrix 的内容，但在我的情况下，我认为我需要扩展索引列表，使用它们的笛卡尔积来构造键，并且我的块的每个元素都需要是一个单独的值，因为显然不能将切片用作字典键。
我最终实施了我在上一段中提出的解决方案。
对于每个第二条对角线，我构建了一个没有任何填充的块稀疏矩阵，然后我通过 right-hand 副产品将其转换为适当形状的矩阵，块矩阵的块是相同的。我 do 需要在此处存储零以使用 bsr_matrix （我首先尝试了 scipy.sparse.block_diag 方法，但它非常慢），但它们很少与我的 semi-padding 解决方案相比：(4n+7)(n+1) vs (4n+8)(n+3)；它们可以用 8 位而不是 128 位表示。执行时间增加了约 40%，但我可以接受（与第一个解决方案相比，它仍然减少了 20%）。
我可能在这里遗漏了一些东西，但现在我对这个解决方案非常满意。
编辑
在影响乘积之前修剪 RHS 矩阵的零点时，与之前最有效的解决方案相比，执行时间减少 30%；一切皆大欢喜
我正在研究一个由线性系统建模的问题，它可以写成方块三对角矩阵。这些块的大小为 b = 4n+8，整个矩阵的大小为 Nb； N 可以任意大（当然是合理的），同时 n 保持相当小（通常小于 10）。
块本身是稀疏的，第一个对角线只有单位矩阵，第二个对角线每个块只有 n+1 个非零列（所以 3n+7 个零列）。这些列是连续的，要么是零，要么是非零，或者相反。
在内存中构建所有这些块会产生一个 3N-2 x b x b 数组，该数组可以用 scipy.sparse.bsr_matrix 转换为稀疏矩阵，然后转换为 CSR 格式并修剪掉多余的零。它工作得很好，但我宁愿跳过这个临时的大而稀疏的数组（对于 N = 1e4，n = 5，每个相关条目都是 5.6 个零！）。
- 我看过 scipy.sparse.dok_matrix，推荐用于切片和增量构建。创建我的条目适合一个整洁的循环，但这个过程比使用 bsr_matrix 和我不必要的密集数组长约 10 倍，这将对未来的用例不利。
- 似乎 bsr_matrix 不能直接使用 scipy 稀疏矩阵作为输入。
- 使用 bsr_matrix 不包括 包括对角线块，然后添加稀疏眼大大减少零的数量（我的测试配置中每个相关条目 3.5 个）[=与原始解决方案相比，27=]和 将过程加快了三分之一。得分！
关于我可以做些什么来进一步减少这个矩阵的原始印记的任何线索？明显的目标是让我在选择 N 时有更多的自由。
编辑
我通过分别构建三个块对角线设法改进了一点点。通过这样做，我的第二条对角线需要更少的填充（n+3 而不是 3n+7；每个相关条目 1.3 个零），将我的原始块分成两个垂直块（一个全是零）和 我一次只需要一个对角线，最重要的是将内存成本减半。主对角线仍然是用眼睛方法构造的。锦上添花：与我的第 3 个要点相比，速度提高了 25%，这可能是因为分离两条第 2 对角线节省了使用 bsr_matrix 之前所需的一些数组重塑操作。与原始方法相比，对于我的 (N, n) = (1e4, 5) 测试用例，它在修剪前比较矩阵时节省了约 2000 万个零。每个 128 位，已经是一个不错的增益了！
我现在能想到的唯一可能的改进是分别构建这些对角线，不进行任何填充，然后插入零列（可能通过具有块矩阵的乘积），最后将所有内容加在一起。 我还阅读了一些关于使用 dict 更新空 dok_matrix 的内容，但在我的情况下，我认为我需要扩展索引列表，使用它们的笛卡尔积来构造键，并且我的块的每个元素都需要是一个单独的值，因为显然不能将切片用作字典键。
我最终实施了我在上一段中提出的解决方案。 对于每个第二条对角线，我构建了一个没有任何填充的块稀疏矩阵，然后我通过 right-hand 副产品将其转换为适当形状的矩阵，块矩阵的块是相同的。我 do 需要在此处存储零以使用 bsr_matrix （我首先尝试了 scipy.sparse.block_diag 方法，但它非常慢），但它们很少与我的 semi-padding 解决方案相比：(4n+7)(n+1) vs (4n+8)(n+3)；它们可以用 8 位而不是 128 位表示。执行时间增加了约 40%，但我可以接受（与第一个解决方案相比，它仍然减少了 20%）。
我可能在这里遗漏了一些东西，但现在我对这个解决方案非常满意。
编辑
在影响乘积之前修剪 RHS 矩阵的零点时，与之前最有效的解决方案相比，执行时间减少 30%；一切皆大欢喜