计算科学 - 求一个置换矩阵（使用 Matlab 的函数y _米_ _ _symrcm) 的矩阵A ( 2 : e n d, 2 : e n d)A(2:end,2:end) - 吾爱随笔录 - 问答

求一个置换矩阵（使用 Matlab 的函数y _米_ _ _symrcm) 的矩阵A ( 2 : e n d, 2 : e n d)A(2:end,2:end)

计算科学 matlab 稀疏矩阵向量带状矩阵

2021-11-29 10:10:57

我有以下 Matlab 代码：

r = symrcm(A(2:end, 2:end)); 
prcm = [1 r + 1]; 
spy(A(prcm, prcm));

哪里A应该是稀疏连接矩阵。

我明白它的作用：

找到r子矩阵的置换向量A A(2:end, 2:end)（由反向 Cuthill-McKee 算法产生）
创建一个向量prcm，它基本上是一个带有 $1$ 在第一个位置和所有其他元素r增加 $1$ .
这个prcm向量应用于逻辑A上A(prcm, prcm) 意味着我们将A根据反向 Cuthill-McKee 算法置换除第一行和第一列之外的所有行和列。所以得到的矩阵看起来像这样：

忽略您在图中看到的特定数字。

题

为什么要对矩阵的行和列进行这种排列？

从我一直在阅读和观察到的内容中，例如，在尝试删除第一行的所有条目后，对这个矩阵应用高斯消元会产生灾难性的填充（检查第 5.7 章，来自“A first course in数值方法”，Ascher 和 Greif）。所以，谁写了这段代码肯定不想找到一个排列 $A$ 应用高斯消去...

2个回答

从您的评论“情节强调节点 1 的连接”，我想也许这个想法表明节点 1 不仅连接到一组“一个靠近另一个”的节点，而且它的互连是分散的在图上有点均匀。

理论上，反向 Cuthill-McKee 对节点进行重新排序，以便将集群映射到附近的位置。或者至少是一些簇：包括起始顶点的簇。或者至少在道德上相似的东西。因此，第 1 行中的非零值不是几乎相邻的一组条目，（例如， $\{2,3,\dots,20\}$ )，但以某种方式均匀分布在矩阵中表明 1 是一个“连接良好的节点”。

如果这真的是答案，那么衡量“连通性”的方法似乎很奇怪。从Pagerank到Estrada index ，有很多关于图中顶点中心性度量的学术文献，我从未见过 RCM 用于此目的。

一个非常简单的假设是必须解决一个问题，其中节点 1 的“自由度”是“受约束的”。假设节点处的自由度 $i$ 是 $u_i$ 而要解决的问题是

K u = f,

$K\,u=f,$ 其中矩阵

K

$K$ 是对称和奇异的，我们现在

f

$f$ 属于范围

K

$K$ . 在这种情况下，一种常见的方法是，如果

K

$K$ 有维度 1，是强加

u_{1} = 0

$u_1 = 0$ 并简单地解决

K_{2 \dots N, 2 \dots N} u_{2 \dots N} = f_{2 \dots N}

$K_{{2\dots N},{2\dots N}} \; u_{2\dots N} = f_{2\dots N}$

其它你可能感兴趣的问题

上一篇软件可以消除使用 180 度镜头拍摄的图像中的所有失真吗？下一篇NVE分子动力学中如何控制温度