对于直接分解，理想情况下，您希望最小化总填充。然而，这是一个 NP-Hard 组合优化问题，难以解决有趣大小的矩阵。减少带宽确实会减少填充的上限，这是您真正想要的替代品。

在迭代方法中，不完全 LU 因式分解 (ILU) 通常用作预处理策略——即近似 LU 因式分解$A \approx LU$被计算，然后$M^{-1}=U^{-1}L^{-1}$（实际上求解方程组涉及$U$和$L$) 用于对迭代方法进行预处理。

在最简单的 ILU 版本中，称为 ILU(0)，在近似分解中不允许填充 - 的稀疏模式$A$用来。在 ILU(0) 方案中，不需要为稀疏性重新排序。

还有更复杂的 ILU 方案。例如，ILU(k) 产生一个近似的 LU 分解，其稀疏模式为$A^{k}$. 另一种常见的方案是将填写条目放在某个大小公差以下。对于 ILU 上这些更复杂的变化，它可以帮助重新排序 A 以减少填充。

使用迭代方法时，您通常会使用加速收敛的预条件器。一个很好的例子是不完全 LU 分解 (ILU)。

当您对稀疏矩阵进行 LU 分解时，L 和 U 因子可能会失去一些稀疏性，额外的条目称为填充。ILU 将忽略其中的一些填充以形成近似分解。

当您对矩阵重新排序时，主要目标是减少填充量（带状矩阵几乎没有填充，但是，如果远离对角线，只有一个条目确实会导致大量填充）。这意味着 ILU 的近似值将更正确，并且您需要的存储空间更少。

编辑：这是（据我所知）在求解线性系统时最常见的重新排序用法。它当然也可以用于其他目的。如果内存访问模式更好，乘法通常也会更好。

您已经找到了 Cuthill McKee，但也有“最低学位”方法以及其他一些方法。以下是一些注意事项。

1. 您声明这些方法改进了缓存。好吧，这些东西早在缓存出现之前就已经发明了。Cuthill McKee 的实际动机是减少带宽。
2. 您询问迭代方法：这些方案最初旨在用于完全 LU 分解，这是一种直接方法。分析重新排序对 ILU 的影响要困难得多。
3. 最小度和“多重最小度”试图找到有利于矢量化和并行性的独立点。
4. 您错过了“光谱”重新排序方法，这些方法使用“Fiedler 向量”或“Perron 向量”将变量分成两个具有最小连接的集合。这样做是为了实现并行性，尤其是在递归执行的情况下。
5. 寻找可以独立处理的集合也是一个古老的想法。对于笛卡尔域，这是由 Alan George 在 1971 年左右完成的，后来 Tarjan 的论文为一般图做了这件事。这里的动机最初是填充减少，但后来这当然应用于并行：域分解。
6. 由于您要询问带宽和并行性：并行性的排序通常具有很大的带宽，或多或少等于整个矩阵。然而，这并不重要，因为基于带宽的填充估计只是上限。
7. 其他基于图的域分解/图拆分方法没有附加方法名称，但可以在 Metis、Zoltan、Chaco 等软件包中找到。
8. 在大多数情况下，并行性的重要性在于人们认为略微增加迭代次数是理所当然的，但是 Benzi 和 Szyld 的论文表明，重新排序有时可以减少迭代次数。
9. 您还可以通过按长度对行进行排序来对矩阵进行排序。这可以大大有利于矩阵向量乘积。D'Azevedo 为 Cray X1 矢量计算机展示了这一点，许多作者也将这一想法应用于 GPU 实现。英特尔甚至试图为这些 50 年前的想法申请专利。