疎行列 フィル・イン ピボット選択 LU分解 コレスキー分解

疎行列のLU分解で生じるゼロ要素が非ゼロ要素に変わる部分（fill in）は、ピボット選択範囲の外側に非ゼロ要素を含む行と列の交差点のうち既存の非ゼロ要素がない部分となる。すなわち、一つの段でピボット選択を開始した時点でフィル・インが生じる部分は決まっており、ピボット確定した行と列についてはフィル・インの位置が確定（※ピボット確定した行と列のどちらかの外側に非ゼロ要素が無ければフィル・インは生じない。その意味で1行目と1列目にフィル・インは存在しない。）、残る範囲は次の段のピボット選択範囲でピボット確定した行と列の結果次第でフィル・インが生じる部分が変わる。全ての段でピボット選択が完了すればフィル・インが生じる部分が確定することとなり、LU分解の開始前にメモリ確保することも可能である。

疎行列をフィル・インが生じない不完全LU分解をする場合、係数行列 A = L _A+ D_A + U_A とすれば、不完全LU分解：
(L_AD_A^-1 + I)(D_A + U_A)（Doolittle法に対応）
(L_A+ D_A)(I + D_A^-1U_A)（Crout法に対応）
出典：反復法Templates、朝倉書店、pp.87-91（1996）

したがって、完全LU分解との関係は、不完全LU分解 = 完全LU分解 + L_AD_A^-1U_A となるから、－L_AD_A^-1U_A でフィル・インの発生が表される。ということで、結局フィル・インは“」”の形で決まっていくことになりので、ピボット選択完了の行と列でしか確定しない。－L_AD_A^-1U_A は完全LU分解の更新処理そのもので、完全LU分解が成立する前提で導出されるクラウト法のアルゴリズムに対応していると見ることができる。

前進代入では対角より下方向で、後退代入では対角より上方向で、LU分解列を辿ることができれば効率よく解を計算できる。この列方向のリンクを作成しながらLU分解の開始前にフィル・インの確定をしていくのには、1行ずつ更新する内積形式ガウス法をベースにすると記述しやすいかもしれない。

係数行列の非ゼロ構造を再利用して計算を反復するなら、ピボット選択後でしか必要にならないリンク作成とフィル・イン分メモリ追加は、ピボット選択と共にまとめておく必要がある。