稀疏矩阵算法最小度数算法一之消元图

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

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

Cholesky 分解

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

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

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

这个假设立刻推导出

矩阵 fill 可以定义为

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

1

Elimation Graph Model

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

其中

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

1

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

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

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

1

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

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

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

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

引理:当且仅当 ,或者 and for some ,才满足

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

1

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 的概念,以下图为例,如果 ,我们有

因为存在以下路径

1

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

定理

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

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

证明完毕。

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

1

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

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

1

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

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

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

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

证明完毕。

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

1

,我们易得:

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

我们采用 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.
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2019-2022 Vincere Zhou
  • 访问人数: | 浏览次数:

请我喝杯茶吧~

支付宝
微信