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

本章节介绍 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 ,基本算法如下

1

1

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

1

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

1

Description of the Minimum Degree Algorithm Using Reachable Sets

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

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

1

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

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

引理 5.4.1:设 $y \notin S $ ,,那么

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

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

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

1

推论 5.4.2:对于 ,均有

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

An Enhancement

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

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

1

还有两组节点是不可区分的,分别为

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

定理 5.4.3:设 ,如果

那么对于所有的 ,存在

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

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

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

联合起来,因此我们得到:

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

推论 5.4.4:设 相对于 不可区分,那么对于 ,存在

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

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

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

那么我们得到

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

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

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

1

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

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

引理 5.4.6:设 。如果 ,并且 ,那么存在

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

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

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

推论 5.4.8: 对于 ,存在

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

1

思考题

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

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

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

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

    结合这两点,我们得证 y 是 中度数最小的一个节点。

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

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

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

总结一下,对于 中的节点,其在 中可能取到的度数的最小值为 ;对于其它节点,其在 中可能取到的度数的最小值为 。因此,在查找 中度数最小的节点时,可以先遍历 中的节点,只要存在度数小于等于 的节点,就可以在 中找到度数最小的节点,即下一次消元的节点。

参考文献

  1. George A, Liu J, Ng E. Computer solution of sparse linear systems[J]. Oak Ridge National Laboratory, 1994.
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2019-2022 Vincere Zhou
  • 访问人数: | 浏览次数:

请我喝杯茶吧~

支付宝
微信