GraphUtilities`
GraphUtilities`

MinimumBandwidthOrdering

バージョン10で，GraphUtilitiesパッケージの機能すべてがWolframシステムに組み込まれた． »

MinimumBandwidthOrdering[g]

無向グラフ g のバンド幅を最小にする頂点順序を見付けようと試みる．

MinimumBandwidthOrdering[m]

行列 m のバンド幅を最小にする行と列の順列を見付けようと試みる．

詳細とオプション

  • MinimumBandwidthOrderingを使うためには，まずグラフユーティリティパッケージをロードしなくてはならない．それにはNeeds["GraphUtilities`"]を実行する必要がある．
  • 頂点順序 f のグラフ{V,E}では，グラフのバンド幅はMax{u, v}∈E |f[u]-f[v]|のように定義される．
  • 行列 m=(aij)では，バンド幅はMaxaij≠0 |i-j|と定義される．
  • 対称行列の場合，エンベロープの大きさは∑i Max(0,Maxaij≠0i-j)と定義される．これは各行の最初の要素から対角要素の位置までの距離の和である．
  • MinimumBandwidthOrderingは入力を無向グラフとして扱う．
  • 次のオプションを与えることができる：
  • Method Automatic使用されるメソッド
    RefinementMethodAutomatic順序を改善するために使用されるメソッド
    RecursionMethodNone使用する反復メソッド

例題

すべて開くすべて閉じる

例  (2)

小さいグラフを定義する：

VertexListの順序を使い，頂点に番号を付ける：

以下で上の順序のグラフのバンド幅を見付ける：

バンド幅を最小にしようとする頂点順序を見付ける：

最小バンド幅順を使って，頂点の番号を付け替える：

MinimumBandwidthOrderingで与えられる頂点順序を使い，バンド幅を見付ける：

矩形行列を定義する：

行列のバンド幅を最小にしようとする行および列の順序を見付ける：

その順序の前後での行列のプロットでは，バンド幅の減少が見られる：

オプション  (1)

Method  (1)

メソッド"RCMD"と"Sloan"を使った行列の順序を見付ける：

"RCMD"を使った最大バンド幅の方が小さくなり，"Sloan"により与えられるエンベロープサイズの方が小さくなる：

アプリケーション  (1)

最小バンド幅順序の応用方法のひとつに，数値計算のキャッシュ性能の最適化がある．例えば，疎行列にベクトルを掛ける場合，行列がバンド幅を最小化するようすでに順序付けられているならば，ベクトルの要素はランダムにアクセスされないので，キャッシュ性能が向上するのである．順序付け自体に時間がかかるため，行列とベクトルの積の操作が何度も繰り返し実行される場合のみ，キャッシュ性能の向上は有益である．

以下でバンド化された行列を生成し，ランダムに置換する：

以下で行列とベクトルの積を50回実行する：

以下でバンド幅を最小にするため行列を置換し，対応するベクトルの置換を行う：

これで行列とベクトルの積にかかる時間が少なくなった：

置換を対象として，答が同じであることをチェックする：

Wolfram Research (2007), MinimumBandwidthOrdering, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html.

テキスト

Wolfram Research (2007), MinimumBandwidthOrdering, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html.

CMS

Wolfram Language. 2007. "MinimumBandwidthOrdering." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html.

APA

Wolfram Language. (2007). MinimumBandwidthOrdering. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html

BibTeX

@misc{reference.wolfram_2024_minimumbandwidthordering, author="Wolfram Research", title="{MinimumBandwidthOrdering}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_minimumbandwidthordering, organization={Wolfram Research}, title={MinimumBandwidthOrdering}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html}, note=[Accessed: 18-November-2024 ]}