本文推導了（右視）稀疏Cholesky算法的消去樹，用於計算A=LL^T，其中L為下三角矩陣，A為稀疏矩陣。這棵樹是大多數稀疏分解軟體的基礎，即使Cholesky的對稱且正定假設不成立也適用。最終，這棵樹告訴我們兩件事：1. 即使原始矩陣A中不存在，矩陣L中非零元素的位置（即“填充”）；2. 因式分解結果的任務依賴圖。傳統上，這個概念通常在稀疏三角解的背景下呈現，並用作Cholesky分解的基石。本文則直接從Cholesky分解出發進行說明。
假設我們先從簡單的密集右視Cholesky算法的偽代碼開始：
隱含的順序和迴圈結構形成一個任務有向無環圖（DAG）。當A為稀疏矩陣時，該DAG以及步驟(3)中隱含的填充元素可完全由A的初始非零模式和一個簡單的樹狀結構（稱為列消去樹）決定。以下以一個簡單的5x5矩陣（僅顯示下三角部分以便閱讀）作示範。
對上述稀疏矩陣，我們得到：
如預期，因為A是稀疏的，有些操作根本不需要執行。若將這些操作剔除，得到的圖形大幅縮小。
此處的列分組尚無實際用途，但可將列分組解釋為「當完成所有該組列的操作後，未來不再參考該列」。
剔除所有不必要操作後，我們得到以下結果：
這個修剪後的圖告訴我們，為完全進行該稀疏矩陣的Cholesky分解所需執行的所有操作。但為了確定此圖，我必須先做密集分解，再剔除不必要計算。
然而，存在一個簡單的O(n)資料結構，結合A的初始非零模式，可以快速告訴我們最終的填充模式及修剪後的任務圖，這就是列消去樹。
回顧密集Cholesky分解的步驟(3)：
它告訴我們一個關鍵結構性事實：若k < j <= i，且L[i][k] != 0且L[j][k] != 0，則L[i][j] != 0。
觀察修剪後的任務圖，我們看到一些隱含的列依賴關係，如0->1和0->2。由於0有兩個“父節點”，這是DAG結構而非樹。但上述結構規則告訴我們0->2是冗餘邊，因為0->1意味著L[1,0] != 0，0->2意味著L[2,0] != 0，因此必有L[2,1] != 0，隱含邊1->2存在，且0->2是冗餘資訊，因為必須先從0->1進行。若移除所有冗餘邊，列DAG結果即為一棵樹。
消去樹告訴我們如何從A的初始非零模式及結構規則（k < j <= i，且L[i][k] != 0且L[j][k] != 0則L[i][j] != 0）生成L的填充模式。
本文將消去樹的計算延後至文末，先展示如何利用以父節點陣列編碼的消去樹：
一旦得到L的非零模式，數值因式分解可依密集算法框架，結合適當的稀疏矩陣資料結構直接進行。關鍵步驟是引入填充的步驟，以下以偽C語言展示：
由於我們已預先計算非零模式，無需檢查數值條目是否存在，因為它們已被預分配。
消去樹本質上是：
為了僅用A的起始非零元素計算消去樹而不做過多額外工作，我們需增量建立父節點陣列。對每個r，我們嘗試尋找通往r的路徑。
因此，若依序遍歷A的行，並查看列ID，會得到候選路徑c->...->r。我們將c->r存入ancestors[c]，並沿ancestors向上迭代，直到找到尚未匹配的列，該列的父節點即為r。因為行是依序遍歷，無法找到更小的r。
消去樹的介紹常涉及一些初步的圖論，這讓人感覺與線性代數稍顯脫節。本文目標並非取代圖論，而是使其更貼近底層演算法。我直接從右視Cholesky分解出發，建立任務DAG，修剪該DAG，並展示步驟(3)的結構規則如何導致任務DAG的壓縮表示，而該壓縮表示正是一棵樹。
