稀疏矩阵算法最小度数算法二之商图

本章节介绍 the minimum degree algorithm ,我个人将其翻译为最小度数算法。这里我们看如何用商图表示和转换消元图。

Computer Representation of Elimination Graphs

在这一章节汇总,我们研究如何在计算中表示和转换 elimination graphs

Explicit and Implicit Representations

让我们回顾一下消元的转换过程, 是从 消除节点 得到的图, 的相邻结构可以按照下面的方式获得:

  1. 获得 中的相邻集合

  2. 从相邻结构中移除节点 及其相邻列表

  3. 对于任何一个节点 中新的相邻列表通过合并两个子集得到

这里有两点需要注意,首先在相邻结构中用于存储 的空间可以在第二步之后重复使用;第二, 可能会比 占用更多的空间。

我们需要一种更加灵活的数据结构,用于存储在 elimination graphs 中结构的动态变化,比如之前提到的 adjacency linked list

Quotient Graph Model

让我们首先对下面的图进行消元,我们消除节点 之后得到右边的消元图。

1

,在 implicit model 中,为了发现 ,我们必须先找到路径 。相似地, 也是因为存在路径 。注意这两个路径的长度分别为 4 和 5 。

我们有两个观测结果:

  1. 如果未消元的节点间的 reachable path 的长度可以缩减,那么生成 reachable sets 的工作量会降低
  2. 如果上面的这些路径可以缩减到极端的情况,那么我们就可以得到 explicit elimination graphs

我们寻求一个妥协,通过聚集连接的消除的节点,我们获得了一个新的图结构。举个例子,在上面的图中,在图 中存在两个连通组分,分别为 。通过形成两个 “supernodes”,我们获得下面的图

1

为了方便,我们设 来表示 中的这两个连通组分。在这个新图中,我们注意到存在路径

这两条路径的长度为 2,一般来说,如果采用这种策略,那么所有这样的路径的长度均会小于等于 2 。

这种策略的另一个优势可以 implemented in-place ,也就是说,这种方式不会占用比原始的图结构更多的空间。

为了正式描述这种消元方式,我们引入商图 (quotient graphs) 。设 是一个给定的图,设 是一种基于节点集合 的分隔形式

,

我们定义 基于 的商图为图 ,其中当且仅当 。通常我们将这个图标记为

上面图 5.3.2 就是一个商图,其切分方式为

是一个给定的图,我们考虑消元的一个阶段,其中 是已经消除的节点集合。我们现在将其联系为一个基于 的商图,定义集合

的切分为

则可以唯一地定义商图

则可以视为对 中的聚集的连通集合得到的图,图 5.3.2 就是对 生成的商图。我们现在研究消元过程中的商图间的相关性。设 为给定图 消元的一系列节点,就像之前一样,设

对于每一个 ,子集 可以推导出分隔方式 ,而相应的商图为

用这种方式,我们可以得到一系列商图

下图就是上面例子中的这一系列商图。

1

下图的定理说明了上面商图其实就是 elimination graphs 的另一种表示。

定理 5.3.1:对于任意 ,我们有

证明略

确定在商图 reachable set 很直接,对于一个给定的节点 ,下面的算法会返回集合 ,注意这里应用了商图的 reachable path 长度最多为 2 的特性 。

1

实际上我们可以从商图中获得 elimination graph ,算法如下:

1

为了说明这个事先,我们考虑上例中从 生成 的过程(加粗表示商图,不加粗表示 elimination graph ),见下图

1

商图模型处于两种模型的中间

1

这三种模型的对应关系总结如下表

1

Implementation of the Quotient Graph Model

我们考虑由消除的节点集合 形成的商图 ,如果 ,我们采用符号 来表明在子图 中的包含 的连通组分。比如,在上面的例子中

换句话说,对于一个给定的连通组分 ,我们可以选择 中的任意一个节点 ,然后使用 来表示 ,即 。在我们讨论如何选择 之前,我们先证明商图模型可以 implemented in-place ,也就是说,只利用原始图的相邻结构的空间。

引理 5.3.2:设 , ,其中 是一个连通的子图,那么我们有

证明:因为 是一个连通子图,因此在 中至少有 条边,这些边在 中会计算两次,得证。

是节点序列, ,对于 ,我们有:

引理 5.3.3:设 ,那么

证明: 的相邻节点可以分为两类,属于 和 不属于 的节点。对于不属于 的节点,原图和商图均不受影响;对于属于 的节点,商图可能会合并成一个 “supernode”,因此数目会减少。因此得证

同时容易证明 ,如果 ,那么 无论 是否与其它节点进行合并,都不会影响 的相邻节点数目,因此 。如果 ,此时如果 是孤立的,那么 的相邻节点不变,如果 与其它节点进行合并,那么此时 的相邻节点数目要么不变,要么会减1。因此得证成立。

定理 5.3.4

证明:考虑商图 ,如果 在子图 中是孤立的,那么显然 ;否则 会合并到 的某个连通组分中,形成 ,那么消元节点内的边数目不变,而根据 ,说明不属于 的节点的边的数目最多和之前相等,再加上减少的 的边,因此得到 ,因此在所有的情况中均存在 ,因此得证

这个定理说明通过消元生成的商图占用的空间不会超过原始的图,而且通过引理 5.3.2,对于 ,会富裕出 个位置。

是节点序列, 。我们选择 作为 的代表,其中

也就是说, 中最后消除的节点。

到此为止,我们描述了商图的数据结构以及如何表示 supernodes ,另一个重要的部分就是在消元的过程中商图的转换。下面的算法展现了如何从 中剔除节点 得到

1

让我们用图 5.3.3 中从 的过程为例,在 ,我们对 采用第一步,得到

因此,新的 ”supernode“ 为

新的拆分方式为

最后,在第三步我们更新相邻集合,得到

商图转换的效果可以通过一个例子来说明,采用图 5.3.3 中的例子,其中我们其相邻结构如图 5.3.6 所示。图 5.3.7 展示生成商图的一些步骤,在 的形成过程中,相邻结构没有改变。而从 的转换过程中,节点 聚合到了一起,因此在 中,节点 的新的相邻结构包含了原图中 的相邻结构。这里 的相邻列表的最后位置采用了一个链表(貌似是其相邻节点排好序,先放到 的相邻列表中第1个到倒数第二个位置,还有多的再放到其它节点的相邻列表中。此时最后一个位置的链接采用负数,这里就是 -2 。将相邻节点最后一个位置之后的一个位置设为0,表示终止位置,对应下图中划线的方块 )。注意在 的相邻列表中,其相邻节点 中改为了 ,因此此时 已经变成了子集 的代表。

1

1

参考文献

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

请我喝杯茶吧~

支付宝
微信