Main Content

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 分解。pq 分别是行和列置换向量,这样 A(p,q) 包含分块上三角。rs 是索引向量,指示精细分解的块边界。ccrr 是长度为 5 的向量,指示粗略分解的块边界。

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

A11 A12 A13 A14
0    0  A23 A24
0    0   0  A34
0    0   0  A44
其中 A12A23A34 是具有非零对角线的方阵。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)-1C(r(i):r(i+1)-1,s(i):s(i+1)-1) 形式的其他所有块是 A23 的对角线块,并且是具有非零对角线的方阵。

提示

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

  • 从图形理论方面看,dmpermA 的偶图中计算最大大小匹配,并且 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 之前推出

另请参阅

|