Sparse Matrix Ordering

Seymour Parter が30年以上前に対称的ガウスの消去法のモデルのために無向グラフを 使った時、グラフ理論は疎行列の計算のための強力な道具として確認された [28]。 グラフは対称行列、 ガウスの消去法中で道を満たすこと、行列の既約性中で強連結成分、 二分マッチング、一次従属中で道を交替すること、そして構造特異性のような 非対称行列における因数分解やアルゴリズムをモデルとするために使うことができる。 グラフは疎行列のアルゴリズムを理解かつ解析することを容易にするだけでなく、 それらは存在するグラフのアルゴリズムと技法を用いて疎行列を処理する領域を も広げる [13]。 この章中で、順序付けアルゴリズムのような疎行列の計算中で BGL を使う方法に ついて説明するつもりである。疎行列のアルゴリズムにさらに深く入っていく前に、 数歩下がって二、三の事柄を再検討しよう。

Graphs and Sparse Matrices

グラフは本来オブジェクト間の二項関係を表現するための方法である。 疎行列の非 0 パターンは同様に未知数間の二項関係を表現する。それゆえ 線形系の疎行列の非 0 パターンはグラフ G(V,E) をモデルとして作る ことができ、その V 中の n 番目の頂点は n 番目の 未知数を表し、そしてここで A_ij が非 0 ならば 頂点 i から頂点 j への辺が存在する。それゆえに、行列が 対称的な非 0 パターンを持つなら、対応するグラフは無向グラフである。

Sparse Matrix Ordering Algorithms

疎の対称である正定符号の線形系を解く過程、Ax=b は、次のような 四つの段階に分割できる:

順序付け:

行列 A の順列 P を見つけ、

記号的因数分解:

PAP^T の Cholesky 係数 L のために データ構造を組み立て、

数値的因数分解:

PAP^T を LL^T に分解し、

三角系の解:

x のために LL^TPx=Pb を解く。

広く用いられているがかなり単純な順序付けアルゴリズムは Cuthill-McKee の 順序付けの亜種である、逆 Cuthill-McKee 順序付けアルゴリズムである。 このアルゴリズムは最小次数アルゴリズム [21] のようなより洗練された方法中で 順序付けを改良するための予備順序付け法として使うことができる。

Reverse Cuthill-McKee Ordering Algorithm

1. 始点を見つける: 始点 r を決定し、r を x₁ に割り当てる。
2. 主要な部分: i=1,...,N のために、頂点 x_i の 番号を付けていない全ての隣接を見つけ、それらに次数の昇順の番号を付ける。
3. 逆順序付け: 逆 Cuthill-McKee 順序付けは i = 1,...,N に対して y_i が x_N-i+1 である場合 y₁,...,y_N によって与えられる。

namespace boost {
  template <class Graph, class Vertex, class Color, class Degree>
  Vertex 
  pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,
                         Color color, Degree degree)
  {
    typename property_traits<Color>::value_type c = get(color, u);

    rcm_queue<Vertex, Degree> Q(degree);
    
    typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
    for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
      put(color, *ui, white(c));
    breadth_first_search(G, u, Q, bfs_visitor<>(), color);

    ecc = Q.eccentricity(); 
    return Q.spouse();
  }
  
  template <class Graph, class Vertex, class Color, class Degree> 
  Vertex find_starting_node(Graph& G, Vertex r, Color c, Degree d) {
    int eccen_r, eccen_x;
    Vertex x = pseudo_peripheral_pair(G, r, eccen_r, c, d);
    Vertex y = pseudo_peripheral_pair(G, x, eccen_x, c, d);

    while (eccen_x > eccen_r) {
      r = x;
      eccen_r = eccen_x;
      x = y;
      y = pseudo_peripheral_pair(G, x, eccen_x, c, d);
    }
    return x;
  }
} // namespace boost

  template < class Graph, class Vertex, class OutputIterator, 
             class Color, class Degree >
  inline void 
  cuthill_mckee_ordering(Graph& G, 
                         Vertex s,
                         OutputIterator inverse_permutation, 
                         Color color, Degree degree)
  {
    typedef typename property_traits<Degree>::value_type DS;
    typename property_traits<Color>::value_type c = get(color, s);
    typedef indirect_cmp<Degree, std::greater<DS> > Compare;
    Compare comp(degree);
    fenced_priority_queue<Vertex, Compare > Q(comp);

    typedef cuthill_mckee_visitor<OutputIterator>  CMVisitor;
    CMVisitor cm_visitor(inverse_permutation);
    
    typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
    for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
      put(color, *ui, white(c));
    breadth_first_search(G, s, Q, cm_visitor, color);
  }  

Minimum Degree Ordering Algorithm

広く使われている高い品質の順序付けアルゴリズムの別の種類の形態は、 対称的ガウスの消去法の過程の模擬の段階の各段階で量を最小にするために選択された 順序付けのような貪欲なアプローチに基づいている。そのようなアプローチを用いて いるアルゴリズムはそれらの貪欲な最小化基準によって通常優秀である [34]。

グラフの表現で、最も貪欲なアルゴリズムによって使われる基本的な順序付け過程 は次のようである:

1. 開始: 行列 A に相当する無向グラフ G⁰ を 構築する。
2. 反復: k = 1, 2, ... に対して G^k = { } となるまで行う:
   • ある基準に従って G^k から頂点 v^k を 選ぶ。
   • G^k+1 を作るために G^k から v^k を除去する。

そのようなアルゴリズムの最も重要な例の一つは最小次数アルゴリズム である。最小次数の各段階においてアルゴリズムは相当するグラフ中で最小次数を 伴う頂点を v^k として選ぶ。 商グラフ表現の使用、全体消去、不完全な次数の更新、多重消去、そして外部次数 のような基本的な最小次数アルゴリズムの若干の改良が開発されてきた。 最小次数のアルゴリズムの歴史の概括のために [35] を見なさい。

最小次数のアルゴリズムの BGL 実装は [21] 中の一つのアルゴリズムの記述に 密接に従っている。実装は現在全体消去、不完全な次数の更新、多重消去、 そして外部次数のための改良を含む。

特別に、アルゴリズムの性能を改善するためにグラフ表現を作成した。 それはテンプレート化された“vector の vector”に基づく。使われている vector コンテナは STL std::vector クラスの上方を足場とするアダプタ・ クラスである。このアダプタ・クラス特有の特徴は以下を含む:

• 要素の消去は結びついたメモリを縮少させない。 消去後の新しい要素の追加は付加されたメモリの割り当てを必要としないだろう。
• 付加されたメモリは新しい要素が追加された際に要求に応じで効率的に 割り当てられる (容量は拡大される時毎に倍増しながら)。この特性は STL vector から来る。

この表現は Liu の実装で使われているそれに似ているが、動的なメモリ割り当ての ためにいくつかの重要な違いがあることに注意しよう。動的なメモリ割り当てに よれば、より効率的なグラフの巡回を考慮している削除されてきたグラフの 部分の上書きを必要としない。もっと重要なことだが、消去グラフについての情報は 些細な記号の因数分解を考慮していることが保たれている。記号の因数分解は 解答過程全体の高価な部分である傾向があるので、その性能を改善することは 著しい計算の節約に帰着できる。

動的なメモリ割り当てのオーバヘッドはいくつかの場合においておそらく効率を 落とす。しかしながら実際にはメモリ割り当てのオーバヘッドは、 メモリ割り当てはさほどなされず、代価は償却されるため、[] 内で示された 実装のために実行時に著しくは寄与しない。

Proper Self-Avoiding Walk

有限要素法 (FEM) は幾何学的に複雑な領域を扱うことが容易なので、偏微分方程式 を解くための柔軟で興味のある数値的アプローチである。しかしながら、 FEM によって生成される体系化されていない網の目 (メッシュ) は、基礎にある 代数学の方程式の行列-ベクタ表記法のために不可欠だけれども、 未知数の理解しやすいラベル付け (番号付け) を提供しない。 特別な番号付けの技法がそのようなアルゴリズムのメモリの使用と局所性を最適化 するために開発されてきた。一つの新しい種類の技法が自己回避ウォークである []。

もしメッシュをグラフであると考えるなら、任意の体系化されていない 二次元のメッシュを横切る自己回避ウォーク (SAW) は二つの連続する三角形が 辺または頂点を共有するようなメッシュの全ての三角形の列挙体である。 好ましい SAW は、歩行 (ウォーク) 中に三つの連続した三角形のために同じ頂点 の上を二回飛び越えることが禁止されている SAW である。 いくつかの正式でないアルゴリズムの多重効率を改善するためにこれは使えるが、 特に実行時のメモリ・アクセス (局所性の改善) とプロセス間通信のを減らすことに 関連した問題がある。参考文献 [] は、任意の三角形のメッシュのために 存在している PSAW を一つの小さなメッシュに拡げてより大きな部分に差し出す PSAW の存在を立証している。立証は事実上　PSAW を構築する規則の集合を 提供する。

メッシュの上に PSAW を構築するアルゴリズムの一群はメッシュのどれか任意の三角形 から始めて、現時点の副メッシュを伴う辺を共有する新しい三角形を選択し、 存在している部分的な PSAW を新しい三角形に拡げる。

二重のグラフをメッシュであると定義しよう。メッシュ中の三角形は頂点で、 メッシュ中の辺を共有している二つの三角形は二重グラフ中で二つの頂点の間に 辺が存在することを意味するとしよう。メッシュの二重グラフを用いることによって、 PSAW を構築するアルゴリズムの一群を実装する一つの方法は、巡回の間の操作を 提供するあつらえのビジタを伴う BFS と DFS のような BGL アルゴリズムを再利用 することである。あつらえのビジタは部分的な PSAW を一件一件展開するための関数 tree_edge() と、始点のために PSAW を組み立てるための関数 start_vertex() を持つ。

Japanese Translation Copyright © 2003 Takashi Itou
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)