dmperm

Dulmage-Mendelsohn 分解

構文

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

説明

p = dmperm(A) は、列 j が行 i と一致する場合に p(j) = i、列 j が一致しない場合に 0 となる、ベクトル p を求めます。A が構造化のフルランクをもつ正方行列の場合、p は最大一致の行の順列で、A(p,:) は、0 のない対角をもちます。A の構造化ランクは、sprank(A) = sum(p>0) です。

[p,q,r,s,cc,rr] = dmperm(A) は、A の Dulmage-Mendelsohn 分解を求めます。ここで、A は正方行列または構造化のフルランクである必要はありません。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 は、0 のない対角をもつ正方行列です。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 の数値的ランクの上限です。sprank(A) = rank(full(sprand(A))) は、正確な演算において確率が 1 になります。

C(r(i):r(i+1)-1,s(j):s(j+1)-1) は、細かい分解の (i,j) 番目のブロックです。(1,1) ブロックは、このブロックが 0 行 0 列でない場合、矩形ブロック [A11 A12] です。(b,b) ブロックは、このブロックが 0 行 0 列でない場合、矩形ブロック [A34 ; A44] です。ここで、b = length(r)-1 です。C(r(i):r(i+1)-1,s(i):s(i+1)-1) の形式の他のすべてのブロックは、A23 の対角ブロックで、0 のない対角成分をもつ正方行列です。

ヒント

A が可約行列の場合、既約対角ブロックを使用して A をブロック上三角型に置き換え、それからブロック後退代入を行って、線形システム Ax = b を解くことができます。置き換えられた行列の対角ブロックだけに対する因子分解が必要で、対角上部のブロックで計算されます。
グラフ理論で、dmperm は、A の 2 部グラフ内で最大サイズの一致とそのグラフの強い Hall 要素に対応する A(p,q) の対角ブロックを検出します。dmperm の出力は、方向性を示さないグラフと方向性を示すグラフの結合要素、または強い結合要素を検出するためにも使われます。詳細は、Pothen and 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.