Main Content

本页对应的英文页面已更新,但尚未翻译。 若要查看最新内容,请点击此处访问英文页面。

symrcm

稀疏反向 Cuthill-McKee 排序

语法

r = symrcm(S)

说明

r = symrcm(S) 返回 S 的对称反向 Cuthill-McKee 排序。此置换向量 r 使得 S(r,r) 可能会使其非零元素更接近于对角线。对于源自长、瘦问题的矩阵的 LU 或 Cholesky 分解来说,这是一种很好的预排序方法。该排序方法对于对称和不对称 S 都有效。

对于实对称稀疏矩阵 SS(r,r) 的特征值与 S 的特征值相同,但 eig(S(r,r)) 可能比 eig(S) 花费的计算时间更短。

示例

全部折叠

语句

B = bucky;

使用 demos 工具箱中的函数生成截顶二十面体的邻接图。这更适合称为足球、Buckminster Fuller 多面穹顶(由此命名为 bucky),或者近来称为由 60 个原子组成的碳分子。顶点有 60 个。这些顶点已通过以下方式进行排序:逐五角形对一个半球中的半数顶点进行编号,然后映射到另一个半球并将两个半球粘合在一起。

通过这种编号,矩阵的带宽就不会特别窄,如第一个 spy 图所示:

figure();
subplot(1,2,1),spy(B),title('B')

反向 Cuthill-McKee 排序可通过以下命令获取:

p = symrcm(B);
R = B(p,p);

spy 图显示了更窄的带宽。

subplot(1,2,2),spy(R),title('B(p,p)')

symamd 的参考页中会继续对此示例进行说明。

带宽也可以通过以下命令进行计算:

[i,j] = find(B);
bw = max(i-j) + 1;

BR 的带宽分别为 35 和 12。

算法

该算法首先找到矩阵图的伪外部顶点。然后,进行广度优先搜索生成一个层次结构体,并通过减少与伪外部顶点的距离来对各顶点排序。该实现严密地基于 George 和 Liu 所述的 SPARSPAK 实现。

参考

[1] George, Alan and Joseph Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981.

[2] Gilbert, John R., Cleve Moler, and Robert Schreiber, “Sparse Matrices in MATLAB: Design and Implementation,” SIAM Journal on Matrix Analysis, 1992. A slightly expanded version is also available as a technical report from the Xerox Palo Alto Research Center.

另请参阅

| | |

在 R2006a 之前推出