MATLAB Function Reference    
dmperm

Dulmage-Mendelsohn分解

表示

詳細

Aが可約行列の場合、既約対角ブロックを使って A を上三角ブロック型に置換し、それから後退代入を行って、線形システム Ax = b を解くことができます。置換された行列の対角ブロックだけに対する因子分解が必要で、対角上部のブロックで計算されます。

p = dmperm(A) は、Aが列に対してフルランクの場合、A(p,:) が非ゼロの対角要素をもつ正方行列となるような、行の順列p を出力します。これは最大マッチングとも言われます。

正方行列 A に対して、[p,q,r] = dmperm(A) は、A(p,q)が上三角ブロック型になるような、行の順列 p と列の順列q を求めます。3番目の出力引数 r は、ブロックの境界を表す整数ベクトルです。A(p,q) の k番目のブロックはインデックス r(k):r(k+1)-1をもちます。

非正方行列 A に対して、[p,q,r,s] = dmperm(A) は、A(p,q) が上三角ブロックとなるような、順列 p,q とインデックスベクトル r,s を求めます。ブロックはインデックス (r(i):r(i+1)-1, s(i):s(i+1)-1) をもちます。

グラフ理論では、対角ブロックは A の隣接グラフの strong Hall成分に相当します。


 dlmwrite doc