大きな疎行列のコレスキー分解に興味があります。私が抱えている問題は、コレスキー因子が必ずしもスパースではないということです (2 つのスパース行列の積が必ずしもスパースであるとは限らないように)。
たとえば、最初の行、最初の列、および対角線に沿ってのみ非ゼロの行列の場合、コレスキー因子は 100% 埋められます (下側および上側の三角形は 100% 密です)。下の画像では、グレーはゼロではなく、白はゼロです。
私が知っている 1 つの解決策は、順列P行列を見つけてP T APのコレスキー分解を行うことです 。たとえば、最初の行を最後の行に移動し、最初の列を最後の列に移動する順列行列を適用することによる同じ行列では、コレスキー因子はまばらです。
私の質問は、一般的にPを決定する方法ですか?
AとP T APのコレスキー分解と、より現実的な行列との違いを理解するには、下の画像を参照してください。これらの画像はすべてhttp://www.seas.ucla.edu/~vandenbe/103/lectures/chol.pdfから取得しました
講義ノートによると
適切な置換行列 P を選択するための多くのヒューリスティックな方法 (ここでは取り上げません) が存在します。
これらのメソッドのいくつかを知りたいです (C、C++、または Java のコードが理想的です)。