dmperm

Dulmage-Mendelsohn 分解

语法

p = dmperm(A) [p,q,r,s,cc,rr] = dmperm(A)

说明

如果列 j 与行 i 匹配，p = dmperm(A) 得到的结果为向量 p，这样 p(j) = i，如果列 j 与其不匹配，得到的结果为零。如果 A 是具有完整结构秩的方阵，则 p 是最大匹配行置换并且 A(p,:) 包含非零对角线。A 的结构秩是 sprank(A) = sum(p>0)。

[p,q,r,s,cc,rr] = dmperm(A)（其中 A 无需是方阵或完整结构秩）计算 A 的 Dulmage-Mendelsohn 分解。p 和 q 分别是行和列置换向量，这样 A(p,q) 包含分块上三角。r 和 s 是索引向量，指示精细分解的块边界。cc 和 rr 是长度为 5 的向量，指示粗略分解的块边界。

C = A(p,q) 拆分为 4×4 组粗略块：

A11 A12 A13 A14
0    0  A23 A24
0    0   0  A34
0    0   0  A44

其中 A12、A23 和 A34 是具有非零对角线的方阵。A11 的列是不匹配的列，A44 的行是不匹配的行。这些块中的任何块都可以为空。在粗略分解中，(i,j)th 块是 C(rr(i):rr(i+1)-1,cc(j):cc(j+1)-1)。如果 A 为方阵并且是非奇异结构，则 A23 = C。也就是说，所有其他粗略块都为 0×0。

对于线性系统，

[A11 A12] 是方程组的欠定部分，它始终是列数多于行数的矩形或为 0×0。
A23 是方程组的确定部分，它始终为方形。A23 子矩阵通过精细分解（A23 的强连通分量）进一步细分为分块上三角矩形。
[A34; A44] 是方程组的超定部分，它始终是行数比列数多的矩形或为 0×0。

A 的结构秩是 sprank(A) = rr(4)-1，这是 A 数值秩的上限。在精确算术运算中，概率为 1 的情况下 sprank(A) = rank(full(sprand(A)))。

C(r(i):r(i+1)-1,s(j):s(j+1)-1) 是精细分解的第 (i,j) 块。(1,1) 块是矩形块 [A11 A12]，除非该块为 0×0。(b,b) 块是矩形块 [A34 ; A44]，除非该块为 0×0，其中 b = length(r)-1。C(r(i):r(i+1)-1,s(i):s(i+1)-1) 形式的其他所有块是 A23 的对角块，并且是具有非零对角线的方阵。

提示

如果 A 是可约矩阵，可以将 A 置换为带有不可约对角块的块上三角矩阵，然后执行块回代，进而对线性系统 Ax = b 求解。仅需要对已置换矩阵的对角块进行分解，节省对角线上方块中的填充量和算术运算。
从图形理论方面看，dmperm 在 A 的偶图中计算最大大小匹配，并且 A(p,q) 的对角块对应于该图形的强 Hall 分量。dmperm 的输出还可用于计算无向图或有向图的连通或强连通分量。有关详细信息，请参阅 Pothen-Fan [1]。

参考

[1] Pothen, Alex and Chin-Ju Fan “Computing the Block Triangular Form of a Sparse Matrix” ACM Transactions on Mathematical Software Vol 16, No. 4 Dec. 1990, pp. 303-324.

[2] Davis, Timothy A. Direct Methods for Sparse Linear Systems. SIAM Series on the Fundamentals of Algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 2006.