MATLAB Function Reference

symrcm

スパース逆 Cuthill-McKee での並べ替え

表示

r = symrcm(S)

詳細

r = symrcm(S) は、S の対称逆 Cuthill-McKee での並べ替えを出力します。これは、S(r,r) が、対角付近に非ゼロ要素をもつような置換ベクトル r です。これは、細長い問題から生じる行列の LU 分解、または、コレスキ分解に対して、良い並べ替えを行います。並べ替えは、S が、対称でも非対称でも行われます。

実数対称スパース行列 S に対して、S(r,r) の固有値は、S の固有値と同じですが、eig(S(r,r)) は、eig(S) よりも計算時間が短縮されます。

アルゴリズム

まず、行列のグラフの擬似外周頂点を求めます。それから、breadth-first 検索によってレベル構造を作成し、擬似外周頂点からの距離を小さくすることで頂点を並べ替えます。これは、George と Liu によって書かれた SPARSPAK に基づいて実行されます。

例題

ステートメント

B = bucky

は、切り捨て正 20 面体の隣接グラフを生成するために、demos Toolbox 内の M-ファイルを使います。これは、サッカーボール、Buckminster Fuller の測地線ドーム（このため bucky といいます）、また最近では、60-原子の炭素分子として知られています。これには、60 個の頂点があります。頂点は、半球面上に現れる頂点の半分の数を使って、5 角形毎に番号付けられ、それから別の半球面内に射影し、2つの半球面を張り合わせます。この番号付けに関しては、最初の spy プロットが示すように、特に幅の狭い行列ではありません。

subplot(1,2,1), spy(B), title('B')

逆 Cuthill-McKeeでの並べ替えは、つぎのようにして得られます。

p = symrcm(B);
R = B(p,p);

spy プロットは、非常に狭い対角幅を示します。

subplot(1,2,2), spy(R), title('B(p,p)')

この例題は、リファレンスページのsymmmd に続きます。

対角幅は、つぎのように計算することもできます。

[i,j] = find(B);
bw = max(i-j) + 1

B と R の対角幅は、それぞれ 35 と 12 です。

参考

colamd, colmmd, colperm, symamd, symmmd

参考文献

George, Alan and Joseph Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981.

Gilbert, John R., Cleve Moler, and Robert Schreiber, "Sparse Matrices in MATLAB: Design and Implementation," to appear in SIAM Journal on Matrix Analysis, 1992. A slightly expanded version is also available as a technical report from the Xerox Palo Alto Research Center.

symmmd

tan, tanh