疎なCholesky分解における消去木の理解

数値線形代数の領域において、Cholesky分解は対称正定値系を解くための基礎となる手法です。しかし、要素の大部分がゼロである疎行列を扱う場合、密な分解アルゴリズムを適用することは計算資源の浪費であり、メモリも大量に消費します。課題となるのは「フィルイン（fill-in）」です。これは、元の行列 $A$ のゼロ要素が、結果として得られる下三角行列 $L$ において非ゼロ要素に変わってしまう現象を指します。

これを管理するために、エンジニアや数学者は**消去木（Elimination Tree）**を使用します。この構造を用いることで、フィルインが発生する場所を正確に予測し、操作の最適な順序を決定することができます。これにより、複雑なタスク依存関係グラフを扱いやすい木構造へと変換します。本記事では、右向き（right-looking）Choleskyアルゴリズムから直接消去木を導出する方法について探ります。

Choleskyの仕組みとフィルインの問題

消去木を理解するためには、まず密な右向きCholeskyアルゴリズムを見る必要があります。プロセスは、各ピボット $k$ に対して主に3つのステップで構成されます。

ピボット分解: 対角要素 $L[k][k] = ext{sqrt}(A[k][k])$ を計算する。
列のスケーリング: ピボットの下にある列をスケーリングする。
ランク1更新（Rank-1 Update）: 残りの行列を更新する: $L[i][j] -= L[i][k] * L[j][k]$。

フィルインを導入するのは、この3番目のステップ、すなわちランク1更新です。具体的には、$L[i][k]$ と $L[j][k]$ が非ゼロ（ここで $k < j ext{ } orall ext{ } i$）である場合、更新によって $L[i][j]$ に非ゼロ要素が必然的に生成または変更されます。

タスクDAGから消去木へ

疎行列に必要なすべての操作をマッピングすると、最初はタスク依存関係の有向非巡回グラフ（DAG）が得られます。このDAGは必要な情報をすべて伝えてくれますが、多くの場合、冗長です。

上述の構造的ルール（$L[i][k] eq 0$ かつ $L[j][k] eq 0 ext{ } orall ext{ } i ext{ } orall ext{ } j ext{ } orall ext{ } k$）により、依存関係グラフ内の多くのエッジは暗黙的に示されます。例えば、列0が列1に依存し、列1が列2に依存している場合、列0が列2に依存していることはすでに捉えられています。

これらの冗長なエッジを取り除くことで、DAGは**列消去木（Column Elimination Tree）**へと収束します。この木は $O(n)$ のデータ構造であり、以下の2つの重要な情報を提供します。

フィルインの予測: $L$ のどの要素が非ゼロになるかを正確に特定する。
タスクスケジューリング: 列を処理すべき正確な順序を決定する。

消去木の実装

記号分解（Symbolic Factorization）

数値計算を行う前に、「記号分解」を行います。このステップでは、消去木を使用して、実際に値を計算することなく $L$ のためのメモリを事前に確保します。アルゴリズムは $A$ の行を反復処理し、消去木を遡ってすべての祖先をマークすることで、L_col 構造体においてすべての潜在的なフィルイン箇所が考慮されるようにします。

数値分解（Numeric Factorization）

非ゼロパターンの事前計算が完了していれば、数値分解は事前確保されたインデックスを反復処理するだけの問題になります。ランク1更新は既知の非ゼロ要素に対してのみ実行されるため、計算の内部ループ中にゼロをチェックするオーバーヘッドを回避できます。

木の計算

消去木の定義は単純です。列 $k$ の親は、$L[j,k] eq 0$ となる最小のインデックス $j > k$ です。

$A$ の初期の非ゼロ要素のみを使用してこれを効率的に計算するには、増分アプローチ（incremental approach）を用いることができます。行 $r$ を昇順に処理し、ancestor 配列を維持することで、列 $c$ から現在の行 $r$ までのパスを跡付けることができます。もしパスが終了した場合、現在の行 $r$ はそのパスの最後のノードの親になります。これにより、親が、その列を祖先として必要とする最初の後の行であることが保証されます。

結論

消去木を抽象的なグラフ理論ではなく、右向きCholeskyアルゴリズムに基づかせることで、線形代数とソフトウェア実装の関係が明確になります。消去木は単なる理論的な構成物ではなく、密な分解の二次的な複雑さを、入力行列の疎性に合わせた非常に効率的なプロセスへと変換する実用的なツールです。