本章节是介绍 George and Liu 书中 RCM 算法脚本的第一篇。

RCM理论简介

The Reverse Cuthill-McKee Algorithm，简称 RCM 算法，是对于稀疏矩阵进行排序的算法，其目的是希望将所有非零元素聚集在对角线附近，这样之后进行 Cholesky 分解得到的 \(\mathbf{L}\) 矩阵也会有类似性质

其对于一个连通图的步骤如下：

如果 \(\mathcal{G}^{\mathbf{A}}\) 是不连通的，我们可以对其每一个连通组分采用上面的算法。对于一个给定的起始节点，这个算法很简单。举例见下图，假设我们将节点 “g” 选为起始节点，即 \(x_{1} = g\) 。

下图说明了算法第二步中所有节点是如何排序的

下图说明了第三步的结果（翻转顺序），最终 envelope size (右图框起来的元素数目)等于 22

起始节点的选择会显著影响这个排序算法的效果，在这个例子中，如果我们选择 “a” 作为起始节点，效果会更好， envelope size 等于 18。

查找初始位点

我们现在看如何查找 RCM 算法的起始节点。

回顾一下，一条长度为 \(k\) ，从节点 \(x_{0}\) 到 \(x_{k}\) 的通路是由不同的节点组成的有序集合 \((x_{0},x_{1},\cdots,x_{k})\) ，其中 \(x_{i} \in Adj(x_{i+1})\) 。两个节点 \(x\) 和 \(y\) 的距离 \(d(x,y)\) 定义为二者最短通路的长度。我们进一步定义节点 \(x\) 的 eccentricity 为 \[ \ell(x)=\max \{d(x, y) \mid y \in X\} \] diameter of \(\mathcal{G}\) 为 \[ \delta(\mathcal{G})=\max \{\ell(x) \mid x \in X\} \] 或者等价于 \[ \delta(\mathcal{G})=\max \{d(x, y) \mid x,y \in X\} \] 如果一个节点 \(x\) 的 eccentricity 等于 图的 diameter ，即 \(\ell(x) = \delta(\mathcal{G})\) ，那么我们称其为一个 peripheral node 。

下图中的图有 8 个节点，其 diameter 等于 5，节点 \(x_{2},x_{5},x_{7}\) 为 peripheral node 。

我们这一小节的目标就是得到一个有效的启发式算法，来找到 eccentricity 很高的节点。注意，我们的算法不一定能找到 peripheral node ，但是我们找到的节点往往具有很高的 eccentricity ，适合作为初始节点。进一步地说，在实际应用中， peripheral node 貌似也没有比算法找到的初始节点有任何优势。最后查找 peripheral node 可能是非常耗时的。

在下面的章节中，我们称用这个算法找到的节点为 pseudo-peripheral nodes 。这个算法的关键是 rooted level structure ，给定一个节点 \(x \in X\) ，the level structure rooted at x 就是 partitioning \(\mathcal{L}(x)\) ，满足： \[ \mathcal{L}(x) = \{ L_{0}(x), L_{1}(x),\cdots,L_{\ell(x)}(x)\} \] 其中 \[ L_{0}(x) = \{ x \}, L_{1}(x) = Adj(L_{0}(x)) \] 并且 \[ L_{i}(x) = Adj(L_{i-1}(x)) - L_{i-2}(x), \quad i=2,3,\cdots,\ell(x) \] eccentricity \(\ell(x)\) 称为 \(\mathcal{L}(x)\) 的长度 (length) 。 \(\mathcal{L}(x)\) 的宽度 (width) 定义为： \[ w(x)=\max \left\{\left|L_{i}(x)\right| \mid 0 \leq i \leq \ell(x)\right\} \] 下图中我们展示了一个 rooted level structure at \(x_{6}\) ，我们注意到 \(\ell(x_{6}) = 3\) ，\(w(x_{6}) = 3\) 。

我们现在可以描述 pseudo-peripheral nodes finding algorithm 了，如下

下图是其中的一个例子，the level structures 的第 \(i\) 层标记为 \(i\) 。

参考文献

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