填入與重排序

如果消去能讓矩陣保持稀疏，稀疏直接法將會很美妙——但它本身做不到。當你把某列減去另一列的若干倍以消去某元素時，可能把原本為零的位置變成非零。這些新產生的非零稱為填入，它們使因子 L 與 U 比原本的 A 更稠密。重排序是門藝術：在消去之前重排各列與各行，使填入盡量少發生。

為何順序重要，直覺如下。想像一個「星形」矩陣，其中一個變數與其餘所有變數耦合。若你先消去這個樞紐變數，清除它那一行會在它從前所有鄰居的每一對之間建立連結——因子完全填滿，一場災難。若改成最後才消去樞紐，那些輻條被便宜地清掉，幾乎不產生填入。所以同一個矩陣，以兩種不同順序分解，可產生大小與成本相差好幾個數量級的因子。重排序演算法——最小度、巢狀分割、反向 Cuthill-McKee——是選擇消去順序以保持因子稀疏的啟發式方法。關鍵在於這是個符號步驟：它只取決於非零的模式、不取決於數值，所以可做一次後重用。

把排序做對是稀疏直接求解中最大的單一槓桿：好的排序可能是「分解能放進記憶體、幾秒內完成」與「稠密填入、耗盡機器」之間的差別。這正是稀疏求解器分成分析階段（選排序、預測填入）與分解階段的原因。誠實的注意點：找出真正使填入最小的排序是個 NP-hard 的組合問題，所以實用的排序是聰明的啟發式而非最優——而對困難的三維問題，即便最佳排序也留下足夠的填入，使迭代法可能勝出。