| MATLAB Function Reference | |
表示
p = colmmd(S)
詳細
p = colmmd(S)
は、スパース行列 S について列の最小度合いでの並べ替えのベクトルを出力します。非対称行列 S に対しては、これは、S(:,p) が S よりもスパースな LU 因子をもつような列の並べ替え p です。
colmmd の並べ替えは、非対称や対称な不定スパース線形システムの解を求めるために、\ と / によって自動的に使われます。
アルゴリズム内のいくつかの新しい方法に関連するオプションやパラメータを変更するためには、spparms を使ってください。
アルゴリズム
対称行列に対する最小度合いのアルゴリズムは、George と Liu による論文[1]に記述されています。非対称行列に対しては、MATLAB の最小度合いアルゴリズムは新しく、Gilbert, Moler, Schreiber の論文 [2]で記述されています。A'*Aに対する対称最小度合いとほぼ似ていますが、実際には、A'*Aの形式ではありません。
アルゴリズムの各段階は、最小度合いの A'*A のグラフの頂点(すなわち、A の列は他のいくつかの列と共通な非ゼロ要素をもちます)を選択し、その頂点を消去し、充填(行のマージ)してグラフの残りを更新します。入力行列 SS が m行n列ならば、列はすべて消去され、n 段階後に置換が完了します。このプロセスを高速化するためには、heuristic を使って複数の段階を同時に行います。
例題
Harwell-Boeing が所有するスパース行列で、MATLABのデモディレクトリに用意されているテスト行列 WEST0479 があります。これは、8ステージの化学蒸留層である Westerberg によるモデルからの結果の479次の行列です。Spyプロットは、8ステージであることを示しています。列の並べ替えは、この構造を壊すことになります。
load west0479 A = west0479; p = colmmd(A); spy(A) spy(A(:,p))
オリジナル行列のLU分解のspyプロットと並べ替えを行った行列のLU分解のspyプロットの比較は、最小度合いが、時間と必要なストレージを約 2.8 倍少なくしていることを示しています。ゼロでない要素は、それぞれ、16777個と5904個です。
spy(lu(A)) spy(lu(A(:,p)))
参考
colamd, colperm, lu, spparms, symamd, symmmd, symrcm
代数演算子 \
参考文献
[1] George, Alan and Liu, Joseph, "The Evolution of the Minimum Degree Ordering アルゴリズム," SIAM Review, 1989, 31:1-19,.
[2] Gilbert, John R., Cleve Moler, and Robert Schreiber, "Sparse Matrices in MATLAB: Design and Implementation," SIAM Journal on Matrix Analysis and Applications 13, 1992, pp. 333-356.
| | colamd | colorbar | |
