稀疏直接求解器

真實應用中大多數巨大矩陣都是稀疏的：在數百萬個元素中，每列只有寥寥幾個非零，因為每個未知數只與少數幾個互動（想像一張網格，格點只和鄰居對話）。若把這種矩陣當成稠密的來儲存或分解，將毫無希望。稀疏直接求解器是一種以消去為基礎的求解器，工程化地只觸及、儲存與計算非零元素，藉此分解稀疏矩陣。

它執行與稠密求解器相同的高斯消去或喬列斯基分解，但作用於只記錄非零元素及其位置的壓縮表示上。挑戰在於消去會在原矩陣為零之處製造出新的非零——稱為填入——因為一列減去另一列可能把零變成非零。稀疏直接求解器努力把填入壓小，通常先重排各列與各行（一個符號分析階段），使因子 L 與 U 盡量保持稀疏，再做數值分解，再做便宜的三角求解。總成本完全取決於發生多少填入——對排序良好的二維問題可接近線性，但若填入稠密則退化趨向立方的稠密成本。

稀疏直接求解器（SuiteSparse、MUMPS、PARDISO、UMFPACK 等）是有限元素與電路模擬的骨幹，它們穩健地給出可重用於許多右端的精確分解。相對於迭代法，它們的一大優點是可靠：不需要好的預條件子、也不必擔心收斂，就能給出向後穩定的答案。它們的極限是記憶體：對非常大的三維問題，填入會使因子大到無法儲存，此時迭代法或多重網格法接手。所以在稀疏直接法與迭代法之間的選擇，大致是問題填入有多嚴重的問題。