稀疏分解與填充

現實應用中的大多數大型矩陣都是稀疏的：幾乎所有元素都是零，因為每個變量只與少數其他變量耦合（網格中一個節點只接觸其鄰居，一個網頁只連結到少數其他網頁）。只儲存和計算非零元，正是百萬乘百萬級問題得以可解的關鍵。麻煩在於分解過程中那些零會發生什麼。

在高斯消元中消去某行時，減去主元列的倍數會把一個結構性的零變成非零。這個新產生的非零稱為填充。一個起初 99% 為零的矩陣，其因子 L 可能稠密得多，從而耗盡記憶體與時間。限制稀疏直接求解的不是原始的稀疏性，而是填充。

關鍵的洞見是：填充量極大地取決於你消元的順序。先對行與列作置換 M -> P M P^T，可能就是幾乎無填充與災難性填充之間的區別。經典的壞情形是第一列第一行稠密的矩陣（一支箭頭射入稀疏的主體）：先消去那個變量會填滿整個矩陣；最後消去它則幾乎不填充。

找到真正最優的排序是 NP 難的，因此實踐者使用啟發式方法：最小度（接下來消去連接最少的變量）與嵌套剖分（用小的分隔集遞迴地切分圖）。正是這些重排序，使稀疏 Cholesky 與稀疏 LU 能求解龐大的結構化系統——若當作稠密處理則毫無希望。