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

RCM理论简介

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

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

如果 是不连通的，我们可以对其每一个连通组分采用上面的算法。对于一个给定的起始节点，这个算法很简单。举例见下图，假设我们将节点 “g” 选为起始节点，即 。

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

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

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

查找初始位点

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

回顾一下，一条长度为 ，从节点 到 的通路是由不同的节点组成的有序集合 ，其中 。两个节点 和 的距离 定义为二者最短通路的长度。我们进一步定义节点 的 eccentricity 为

diameter of 为

或者等价于

如果一个节点 的 eccentricity 等于 图的 diameter ，即 ，那么我们称其为一个 peripheral node 。

下图中的图有 8 个节点，其 diameter 等于 5，节点 为 peripheral node 。

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

在下面的章节中，我们称用这个算法找到的节点为 pseudo-peripheral nodes 。这个算法的关键是 rooted level structure ，给定一个节点 ，the level structure rooted at x 就是 partitioning ，满足：

其中

并且

eccentricity 称为 的长度 (length) 。 的宽度 (width) 定义为：

下图中我们展示了一个 rooted level structure at ，我们注意到 ， 。

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

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

参考文献

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