这是稀疏直接求解器领域中一个经过充分研究的问题。我强烈建议阅读 Joseph Liu对多前额方法的概述，以便更好地了解重新排序和超级节点如何影响填充和求解时间。

嵌套剖析是一种非常常见的生成重新排序的方法，本质上由递归图分区组成。MeTiS是图形分区的事实标准，您可以在此处阅读有关它背后的一些想法。另一个常用的包是SCOTCH，Chaco也很重要，因为它的作者介绍了多级图分区，这也是MeTiS 背后的基本思想。

George 和 Liu在他们的经典著作中表明 ，2d sparse-direct 解决方案只需要 $O(n^{3/2})$ 工作和 $O(n \log n)$ 内存，而 3d sparse-direct 需要 $O( n^2)$ 工作和 $O(n^{4/3})$ 内存。$O(n^{3/2})$ work and $O(n \log n)$ memory, while 3d sparse-direct requires $O(n^2)$ work and $O(n^{4/3})$ memory.

Cuthill-McKee是您想做的事情的事实上的标准。如果您想使用此方法， Boost Graph Library (BGL)中有一个易于使用的算法实现（及其反向），文档包含如何使用它的示例。

说到多前沿方法，从事 LU 分解的多前沿方法 ( UMFPACK ) 的Tim Davis有许多例程，这些例程将重新排序矩阵以最小化填充。作为SuiteSparse的一部分，您可以在此处找到它们。SuiteSparse 使用 MeTiS。

另一件需要注意的事情：在某些问题中，您可以巧妙地对变量进行排序，以便获得带状或接近带状的模式，这可以为您节省调用这些算法的麻烦（和 CPU 时间）。但是，这种巧妙的重新排序需要您的洞察力，并且远不如人们在此处的答案中提到的基于图论的重新排序算法那么普遍。

在应用数学界有一种称为 ADI（隐式交替方向）的算法，在物理界有一种称为拆分运算符的算法，基本上可以满足您的描述。这是一种迭代方法，它遵循以下基本过程：

1. 对于 $y$ 的每个值，在 $x$ 方向上放松。该矩阵应该是三对角矩阵，因此可以在相对较短的时间内直接求解。$y$ , relax in the $x$-direction. This matrix should be tridiagonal, so it can be solved directly in relatively little time.

2. 对于 $x$ 的每个值，在 $y$ 方向上放松。同样，这应该很快。$x$ , relax in the $y$-direction. Again, this should be pretty quick.

3. 重复 1 和 2，直到误差尽可能小。

我不知道这个算法的形式复杂性，但我发现它每次使用它时收敛的迭代次数都比 Jacobi 和 Gauss-Seidel 少。