MATLAB Function Reference | ![]() ![]() |
表示
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);
subplot(1,2,2), spy(R), title('B(p,p)')![]()
[i,j] = find(B); bw = max(i-j) + 1
参考
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 | ![]() |