稀疏矩阵算法最小度数算法三之最小度数算法理论

2022-09-25

字数统计: 2.4k | 阅读时长≈ 8 分钟

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

The Minimum Degree

虽然和的非零元素结构不同，但是其非零元素数目相同，即。然而对于某些，和可能有很大的差别。

我们希望找到一个置换矩阵，能够最大限度地减少 fill-in ，即

然而至今为止，我们没有一个有效的算法可以得到这个最佳的。实际上这个问题是一个 NP-complete problem (Yannakakis[56]) 。因此我们不得不采用一些启发式的算法来得到一个可以接受的。

到目前位置，最流行的算法就是最小度数算法 (the minimum degree algorithm) (Tinney [53]) 。假设已经打上了标签，此时这些列在 filled graph 中的非零元素数目已经确定了。为了减少第列中的非零元素数目，很明显在剩下的需要分解的子矩阵中，拥有最少的非零元素的列应该选为列。

The Basic Algorithm

the minimum degree algorithm 可以简单地描述为对一个图节点地排序。设是一个没有排序的图，采用 elimination graph model ，基本算法如下

举个例子，下图是我们考虑的图

最小度数算法的执行过程如下图。注意在某一步中可能存在多个度数最小的节点，这里我们是随机选择了一个。然而在不同的版本中，这个节点的选择可能有着不同的方法。

Description of the Minimum Degree Algorithm Using Reachable Sets

在最小度数算法中，每一步均包含了图的转换，这是这个算法实施起来最费时的步骤。如果我们可以提供一种替代方法来计算 elimination graph 中节点的度数，我们就可以跳过这些图的转换过程。

定理 5.2.3 可以通过利用 reachable sets 来实现这一点，因此我们可以对算法做一些修改如下：

此时在整个过程中我们均只采用原始的图结构。实际上，这个算法可以只通过相邻结构得到实现。

需要指出的是，在 Degree update 这一步中，我们没有必要对每一个中的节点均计算度数，因为其中的绝大部分均会保持不变，存在引理如下

引理 5.4.1：设 $y \notin S $ ，，那么

说明在剔除的消元图中，和是相邻的，此时剔除，的度数可能会发生改变，反之的度数不会发生改变。也就是说，剔除只有在消元图中的相邻位点的度数会发生改变。

在图 5.4.3 中，考虑节点被消除的步骤中，此时，因此，因此消除影响节点和的度数。

因此上面算法的步骤 3 可以重新表达为

推论 5.4.2：对于，均有

根据引理 5.4.1 ，对于，自然成立。否则，在剔除的消元图中，和是相邻的。剔除节点，首先剔除了这条边，然后的相邻节点互相连接，因此至少为。

An Enhancement

上面提到的算法每次循环只会对一个节点进行编号，但是当我们在步骤 2 中找到了一个度数最小的节点，我们通常可能会发现可能是下一个节点的候选节点集合。当我们考虑一次消元的过程，其中是已经消除的节点的集合，如果满足下式，那么节点称为不可区分的 (indistinguishable with respect to elimination) 。

以下图为例，子集包含 36 个阴影的节点。我们注意到此时是不可区分的，因为，，是一样的，均为

还有两组节点是不可区分的，分别为和。

不可区分的节点可以加速最小度数算法。

定理 5.4.3：设，如果

那么对于所有的，存在

首先我们想要证明。因为，所以，而，因此。由于，而中不包含，因此我们得到。

其次我们想要证明。考虑，肯定存在一条路径，其中。如果所有，由于，那么要么，自然成立；要么，由于，因此同样有。如果不是所有，设是中第一个不在中的节点，即

这说明，也就是说，也可以通过中的节点连接到 , 进而进一步通过连接到 , 因此有。得证。

联合起来，因此我们得到：

我们可以从反方向证明得到，因此我们得证。

推论 5.4.4：设相对于不可区分，那么对于，存在

换句话说，如果在消元的某一步中，如果两个节点不可区分，那么除非其中一个节点被消除，不然它们会一直保持不可区分的状态。进一步地说，这些不可区分的节点可以同时消除。

定理 5.4.5：如果两个节点在最小度数算法中的某一步中不可区分，那么它们可以在算法中同时被消除。

证明：设相对于不可区分，假设在集合已经被消除之后，变成了度数最小的一个节点，即

那么我们得到

因此，对于所有的，通过推论 5.4.2 ，存在

换句话说，当消除了之后，节点就会变成度数最小的节点。

因此不可区分的节点可以聚集在一块，视为一个 supernode 。举个例子，下图展示了两步中不可区分的节点形成 supernode 的过程，当 {a,b,c} 被消元之后，剩下的所有节点均有相同的 reachable sets ，因此均可以聚集成一个节点。

一般来说，我们不会试图找出所有可能的不可区分的节点，我们会查找一个简单但是证明非常有效的条件，在绝大多数情况下，这个条件会找出所有不可区分的节点。

设，是已经消元的节点，设和是子图的两个连通组分，即

引理 5.4.6：设，。如果，并且，那么存在

证明：如果。假设，因为是的一个连通组分，同样，即均是的相邻节点，因此我们可以通过找到一条从到的路径，因此；同样地，假设，同理可证。因此可得。

反过来，如果，那么肯定存在一条路径。如果，那么。如果，。如果，由于是 S 中的一个连通组分，这说明是的子集，否则，则是的子集。因此，因此，因此我们证明。

定理 5.4.7：在下面的集合中的节点相对于是不可区分的。

推论 5.4.8：对于，存在

更新后的最小度数算法如下：

思考题

设是从最小度数算法中消元图中选中的度数最小的节点，设，并且满足

尝试证明 y 是中度数最小的一个节点。

证明：我们把中的节点分为两类，第一类是，第二类是其他节点。根据之前的推导，第二类的节点从到的过程中度数不变，因此对于其中任意一个节点，均满足，因此这些节点在中的自由度均大于。

我们再看第一类节点，我们看在什么情况下才能满足上面的条件，首先从到的过程中，的度数先减去 1（消除），再加上 n (新增的 fill-in ) ，因此我们有，因此是第一类节点在中可能取到的最小度数。

结合这两点，我们得证 y 是中度数最小的一个节点。
设是从最小度数算法中消元图中选中的度数最小的节点，设，并且满足

证明：这里我们证明这个条件和第一题的条件是等价的。首先我们证明如果满足第一题中的条件，那么同样满足第二题的条件。第一题中我们证明得到。由于首尾相等，因此其中的两个不等式均为等式。因此我们得到和，也就是说在中也是度数最小的节点，并且消除 x 之后 y 没有新增的 fill-in 。没有新增的 fill-in 说明中除之外的相邻节点均与相邻，设在的相邻节点数为，其除之外的相邻节点数为，这个节点也是的相邻节点。由于，因此在的相邻节点数也为，除了上面的个节点就还有节点，正好是个节点，因此说明 和是不可区分的，因此满足。

反过来，如果，实际这个条件为，需要减去其自身。因此，由于在中度数最小，因此我们得到，这说明，因此说明 和是不可区分的，易得，得证。