不完全 LU 預條件子

不完全 LU 預條件子是最廣為使用的通用預條件子，它出自一個巧妙的折衷。完整的 LU 分解把 A = L U 寫成一個下三角與一個上三角矩陣的乘積；有了它，你就能精確又便宜地解 A x = b。但對大型稀疏的 A，計算完整的 L 與 U 是毀滅性的，因為消去會製造填入——在 A 原為零之處冒出許多新非零元——使三角因子變稠密。不完全 LU 繞過這點：照常規方式計算 L 與 U，卻單純「拒絕」儲存大部分填入，新非零元一出現就丟掉。你得到稀疏、便宜、近似的因子。

這些近似因子的乘積 M = L_近似 U_近似 並不等於 A，但很接近——接近到 M 是個極佳的預條件子。最簡單的變體 ILU(0)（零填入），讓因子的稀疏型樣與 A 完全相同：A 中原為零的每個位置，在 L 與 U 中仍為零。更精確的變體允許受控的額外填入：ILU(p) 保留到「層級 p」的填入，ILUT 則保留數值超過某門檻（捨棄容忍度）的元素，花更多記憶體換取更緊的近似。當 A 對稱正定時，對稱的表親是不完全喬列斯基，是共軛梯度法的標準搭檔。屆時每個預條件步只要做一次稀疏的前代與回代，很便宜。

ILU 受歡迎是因為它通用——它對 A 的來源要求不多，且在不規則、無結構的矩陣上往往運作良好，而像多重網格這類幾何方法在那裡並不直接適用。但它帶著誠實的告誡。對非對角佔優或非對稱正定的矩陣，不完全分解可能崩潰（出現零或負樞紐），有時產生不穩定的預條件子、讓情況更糟。它的品質對未知數的排序、以及你允許的填入層級都很敏感，而三角求解本質上是依序的，限制了平行可擴展性。所以 ILU 是個穩健、易上手的首選——但在有結構的偏微分方程問題上，量身打造的多重網格預條件子通常勝過它。