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.
扩展功能
版本历史记录
在 R2006a 之前推出
