12

大きな疎行列のコレスキー分解に興味があります。私が抱えている問題は、コレスキー因子が必ずしもスパースではないということです (2 つのスパース行列の積が必ずしもスパースであるとは限らないように)。

たとえば、最初の行、最初の列、および対角線に沿ってのみ非ゼロの行列の場合、コレスキー因子は 100% 埋められます (下側および上側の三角形は 100% 密です)。下の画像では、グレーはゼロではなく、白はゼロです。

密集

私が知っている 1 つの解決策は、順列P行列を見つけてP T APのコレスキー分解を行うことです 。たとえば、最初の行を最後の行に移動し、最初の列を最後の列に移動する順列行列を適用することによる同じ行列では、コレスキー因子はまばらです。

まばらな

私の質問は、一般的にPを決定する方法ですか?

AP T APのコレスキー分解と、より現実的な行列との違いを理解するには、下の画像を参照してください。これらの画像はすべてhttp://www.seas.ucla.edu/~vandenbe/103/lectures/chol.pdfから取得しました

順列行列

講義ノートによると

適切な置換行列 P を選択するための多くのヒューリスティックな方法 (ここでは取り上げません) が存在します。

これらのメソッドのいくつかを知りたいです (C、C++、または Java のコードが理想的です)。

4

1 に答える 1

9

最小のフィルイン行列因数分解のための行列の行と列の最適な順列を見つける問題は、簡単な作業ではありません (コメントで指摘されているように)。したがって、実際にはヒューリスティックアルゴリズムが使用されます。

多くの場合、マトリックスの隣接グラフのグラフアルゴリズムに基づいて、ヒューリスティックな再番号付け/順序付け戦略を実装するライブラリがいくつかあります。対応する隣接行列の帯域幅を削減しようとします。簡単に実装できるアルゴリズムは、Cuthill-McKee AlgorithmまたはMinimum-Degree Orderingアルゴリズムです。この問題の詳細については、Yousef Saad: Iterative Methods for Sparse Linear Systems (2003)などの書籍を参照してください。

多くのライブラリはヒューリスティック アルゴリズムを実装しています。

  • Suitesparse 大規模なスパース線形システムの直接ソルバーのライブラリのコレクション。ライブラリ AMD、CAMD、COLAMD、および CCOLAMD に実装されている順序付けメソッド
  • (Par-)Metisグラフ分割用のライブラリですが、行列並べ替えアルゴリズムも提供します
  • Boost.Graph隣接グラフを直接処理し、前述の Cuthill-McKee や Minimum-Degree Ordering などの順序付けアルゴリズムを提供します。
  • (PT-)グラフ分割とスパース行列の並べ替えのためのScotch

これらのライブラリの一部は、スパース コレスキー分解法も提供しており、直接使用できます。

于 2015-04-18T10:42:03.320 に答える