本章节介绍 the minimum degree algorithm ，我个人将其翻译为最小度数算法，我们这里看消元图的理论基础。

在这一章节中我们研究的排序算法称为 minimum degree algorithm (Rose) ，这是一个启发式算法，用于对 排序减少其分解时产生的 fill-in 数目。

Cholesky 分解

设 是一个对称稀疏矩阵，其中的非零结构 (nonzero structure) 定义为

假设 分解为 ，而 filled matrix ，下文中我们用 替换 ，其相应的非零结构为

在本文中，我们假设精确的数值消除并不存在（就是说任意两个浮点数相减不能得到0），因此对于一个给定的非零结构 ，其相应的 的结构就能完全确定。

这个假设立刻推导出

矩阵 的 fill 可以定义为

举个例子，假设存在下图中的矩阵，其中的 fill-in 用加号表示，其相应的集合为

Elimation Graph Model

我们现在联系 的高斯消元，与相应的图 的变化。我们回顾一下分解的 outer product form ，第一步为

其中

这一步会递归地应用于 ， 等。由于我们假设不存在精准的消除，因此根据上面的公式，如果 中的 元素不为0，或者 ， 矩阵的 元素才不为0。当第一个条件不成立，而第二个条件成立时，便产生了 fill-in 。下图中展示了这个情况

当第一步分解完成之后，我们对 矩阵继续进行分解。

现在我们看从 到 的转变过程中，其相应的图从 到 的变化，下图是一个例子。生成图 的过程如下

1. 删除节点 及其相应的边
2. 添加边，使得图 中的 彼此之间相邻

因此，就像 Rose 观察到的，对称矩阵的高斯消元（上面的 ， 等其实也一样就是高斯消元的结果 ）可以理解为生成一系列 elimination graphs

其中 是从 中得到的，过程就和上面描述的一样。这里 是所有节点的标签，当我们已知所有节点的标签时，我们用标记 替换 。在上图的消元过程，比如从 消除 的过程中，产生了三个 fill-in 的边 。

设 是 的分解因子，定义 的 filled graph 为 ，其中 。这里所有边的集合 包含了 中的所有边，加上分解过程中新增的边。

和 的关系存在以下引理 (Parter)

引理：当且仅当 ，或者 and for some ，才满足

根据这个引理，上图中得到的 如下。发现了 ，我们就可以得到 矩阵的结构。

Modelling Elimination By Reachable Sets

上面的章节中定义了 elimination graphs 的序列

然后提供了一种递归的方式来确认 ，我们这一章节的目标是采用 reachable sets 的概念来确认这些步骤。

让我们首先研究在上图中 fill edge 的形成过程。在 ，存在路径：

因此当 被消除，被创建了 这条边。然而， 并不在原始的图中，这条边是由于路径 中的 从 中消除而创建得到的。

联合这两个，我们得到 中的路径 才是生成 fill edge 的真正原因，因此我们引入 reachable sets 的概念。

设 是节点集合的一个真子集， 。如果存在一个从 y 到 x 的路径 ，其中 ，则我们称节点 是 be reachable from a node through ，注意由于 可以为 0，因此 的任何不在 中的相邻节点均 be reachable from through

这些节点的集合就是 reachable set of y through S ，标记为 ，定义为

为了说明 reachable set 的概念，以下图为例，如果 ，我们有

因为存在以下路径 ，，

下面的定理说明通过 reachable set 来创建的 filled graph

定理：

证明：假设 ，根据定义，在 中存在一条路径 ，其中 。如果 或者 ，根据上面的引理就可以直接得到 。如果 ，我们可以从 中逐渐消除节点，使得 ，从而得到 。

反过来，假设 ，并且 。根据前面的推理，则 ，或者 and for some 。如果是满足第一个条件 ，则 成立；如果是满足第二个条件，即 and for some ，这说明在 中 和 ， 和 均存在一条路径连接，二者可以连通起来，说明 存在某条通过 连接 和 的路径 ，因此 成立。

证明完毕。

采用矩阵的术语， 就是在列向量 中的非零元素的行号。举个例子，假设上图 5.2.5 中的图排序如下

如果 ，根据上面的定理，我们可以轻松得到下面的 reachable set

因此我们可以得到下面的 矩阵

因此我们可以通过 的结构而直接得到 矩阵的结构（这种方式比 envelope region 的方式更加精确，fill-in 更少）。更重要的是，我们可以更方便的得到 elimination graphs 。设 为一组 elimination graphs ，我们有：

定理：设 是一个 elimination graph 中的一个节点，邻近于 中的节点 的节点集合为：

其中，这里的 操作符是用于原始的图 。

证明：证明可以通过对 采用归纳法证明得到，设 ，易证明成立；假设 时成立，即邻近于 中的节点 的节点集合为 ；当 时， 进一步剔除了 ，我们需要证明邻近于 中的节点 的节点集合为 。此时如果 , 也就是说在 中 和 不相邻，此时 中的节点 的相邻列表不变，仍为 ，也等于 。如果 ，此时 的相邻节点会减去 , 新增 在 中 除 之外的相邻节点，即此时 中的节点 的相邻列表为 ，易得其中第一部分为 中路径中不包含 的部分 ，对于第二部分，设 , 由于 ，易得 ，因此第二部分为 路径中包含 的部分 ，因此第一部分和第二部分的并集就正好为 ，因此得证 邻近于 中的节点 的节点集合为 。

证明完毕。

我们用图 5.2.3 来重新举一个例子，我们考虑 图 和 图 如下：

设 ，我们易得：

因此我们就得到 图 的结构。

我们采用 reachable sets 得到的 图 称为 implicit model for elimation；而上一节中消除节点 及其相应的边 添加边，使得图 中的 彼此之间相邻，这种方式称为 explicit model for elimation。

参考文献

1. George A, Liu J, Ng E. Computer solution of sparse linear systems[J]. Oak Ridge National Laboratory, 1994.