理解稀疏 Cholesky 消去樹

在數值線性代數領域中，Cholesky 分解是求解對稱正定系統的基石。然而，當處理稀疏矩陣（即大部分元素為零）時，應用稠密分解演算法會造成計算浪費且耗費大量記憶體。挑戰在於「填入」（fill-in）現象：即原始矩陣 $A$ 中的零元素在生成的下三角矩陣 $L$ 中變成了非零元素。

為了管理這一點，工程師和數學家使用消去樹（Elimination Tree）。這種結構讓我們能夠精確預測填入會發生在哪裡，並決定最佳的操作順序，將複雜的任務依賴圖轉換為易於管理的樹狀結構。本文將探討如何直接從右向 Cholesky 演算法（right-looking Cholesky algorithm）推導出消去樹。

Cholesky 的機制與填入問題

要理解消去樹，我們必須首先觀察稠密右向 Cholesky 演算法。該過程對每個樞紐 $k$ 涉及三個主要步驟：

樞紐分解：計算對角元素 $L[k][k] = \sqrt{A[k][k]}$。
列縮放：縮放樞紐下方的列。
秩-1 更新（Rank-1 Update）：更新剩餘矩陣：$L[i][j] -= L[i][k] * L[j][k]$。

正是這第三步——秩-1 更新——引入了填入。具體來說，如果我們在 $L[i][k]$ 和 $L[j][k]$ 處有非零元素（其中 $k < j \le i$），則更新過程必然會在 $L[i][j]$ 處創建或修改一個非零元素。

從任務 DAG 到消去樹

如果我們繪製出稀疏矩陣所需的所有操作，最初會得到一個任務依賴的有向無環圖（DAG）。雖然這個 DAG 告訴了我們所需知道的一切，但它通常是冗餘的。

由於上述結構性規則（$L[i][k] \neq 0$ 且 $L[j][k] \neq 0 \implies L[i][j] \neq 0$），依賴圖中的許多邊是隱含的。例如，如果第 0 列依賴於第 1 列，且第 1 列依賴於第 2 列，那麼第 0 列對第 2 列的依賴關係已經被捕捉到了。

通過移除這些冗餘邊，DAG 會塌陷成一個列消去樹（Column Elimination Tree）。這棵樹是一個 $O(n)$ 的資料結構，提供了兩個關鍵資訊：

填入預測：精確地哪些 $L$ 中的元素將是非零的。
任務調度：必須處理列的精確順序。

實作消去樹

符號分解

在進行數值計算之前，我們會進行「符號分解」（symbolic factorization）。此步驟使用消去樹來為 $L$ 預先配置記憶體，而無需實際計算數值。演算法會遍歷 $A$ 的各行，並沿著消去樹向上走，以標記所有祖先節點，確保 L_col 結構中考慮到了每一個潛在的填入位置。

數值分解

有了預先計算好的非零模式，數值分解就變成了一個遍歷預先配置索引的過程。秩-1 更新僅在已知的非零元素上進行，從而避免了在計算的內層迴圈中檢查零元素的開銷。

計算樹結構

定義消去樹非常直觀：列 $k$ 的父節點是最小的索引 $j > k$ 使得 $L[j,k] \neq 0$。

為了僅使用 $A$ 的初始非零元素來高效地計算此結構，我們可以使用增量法。通過按遞增順序處理行 $r$，並維護一個 ancestor 陣列，我們可以追蹤從列 $c$ 到當前行 $r$ 的路徑。如果路徑終止，則當前行 $r$ 成為該路徑中最後一個節點的父節點。這確保了父節點是第一個在後續行中需要該列作為祖先的行。

結論

通過將消去樹建立在右向 Cholesky 演算法而非抽象圖論之上，線性代數與軟體實作之間的關係變得清晰。消去樹不僅僅是一個理論建構，而是一個實用的工具，它將稠密分解的二次複雜度轉換為針對輸入矩陣稀疏性量身定制的高效過程。