MATLAB中dmperm函数用法

目录

语法

说明

---

        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]。​

提示

• 如果 A 是可约矩阵，可以将 A 置换为带有不可约对角块的分块上三角矩阵，然后执行分块回代，进而对线性方程组 Ax = b 求解。仅需要对已置换矩阵的对角块进行分解，节省对角线上方块中的填充量和算术运算。

• 从图形理论方面看，dmperm 在 A 的偶图中计算最大大小匹配，并且 A(p,q) 的对角块对应于该图形的强 Hall 分量。dmperm 的输出还可用于计算无向图或有向图的连通或强连通分量。