矩阵重新排序以阻止对角线形式

Question

给出一个稀疏矩阵，如何通过行和列排列对行和列重新排序，使其以块对角线的形式出现？

行和列排列不一定像反向 Cuthill-McKee 排序那样耦合：http://www.mathworks.com/help/matlab/ref/symrcm.html?refresh=true 简而言之，您可以独立执行任何行或列排列。

总体目标是将所有非零元素聚集到对角线。

Answer 1

这里有一种方法。

首先制作一个顶点为行和列的图形。 每个非零值都是该行和该列之间的一条边。

然后，您可以使用标准图论算法来检测此图的连接组件。 单元素 1 表示所有零行和列。 编号其他的。 这些组件的行数和列数可能不相等。 您可以将一些零行和列分配给它们以使它们呈正方形。

您的

方形组件将是您的块，从这些组件的编号中，您知道将它们放入什么顺序。 现在只需对行和列重新排序即可实现此结构，瞧！ （剩余的零行/列将在对角线的右下角产生一堆 0 块。

Answer 2

只是一个想法，但是如果您从包含A块稀疏结构的原始块矩阵A制作一个新的矩阵Ab。 例如：

A = [B 0 0; 0 0 C; 0 D 0]; % with matrices 0 (zero elements), B,C and D
Ab = [1 0 0; 0 0 2; 0 3 0]; % with identifiers 1, 2 and 3 (1-->B, 2-->C, 3-->D)

然后Ab是一个简单的稀疏矩阵（示例中的大小为 3x3）。然后，您可以使用反向 Cuthill-McKee 排序来获取所需的排列，并将这些排列应用于 Ab。

p = symrcm(Ab);
Abperm = Ab(p,p);

然后使用标识符从Abperm创建有序块矩阵Aperm，我相信你会得到想要的结果。

您需要聪明地将标识符分配给各个块等等，但这应该是可能的。