an incomplete LU preconditioner
An incomplete LU preconditioner is the most widely used general-purpose preconditioner, and it comes from a clever compromise. A full LU factorization writes A = L U as a product of a lower- and an upper-triangular matrix; with it you could solve A x = b exactly and cheaply. But for a large sparse A, computing the full L and U is ruinous because elimination creates fill-in — many new nonzeros where A had zeros — and the triangular factors become dense. Incomplete LU sidesteps this by computing L and U the usual way but simply REFUSING to store most of the fill-in, throwing away the new nonzeros as they appear. You get sparse, cheap, approximate factors.
The product of these approximate factors, M = L_approx U_approx, is not equal to A, but it is close — close enough that M is an excellent preconditioner. The simplest variant, ILU(0) (zero fill-in), keeps the factors with exactly the same sparsity pattern as A: every entry of A that was zero stays zero in L and U. More accurate variants allow a controlled amount of extra fill: ILU(p) keeps fill up to 'level p', and ILUT keeps entries above a numerical threshold (drop tolerance), spending more memory for a tighter approximation. When A is symmetric positive-definite, the symmetric cousin is incomplete Cholesky, the standard companion to conjugate gradient. Each preconditioning step then costs just a sparse forward-and-back substitution, which is cheap.
ILU is popular because it is general — it asks little about the origin of A and often works well on irregular, unstructured matrices where geometric methods like multigrid do not directly apply. But it carries honest caveats. The incomplete factorization can break down (a zero or negative pivot) for matrices that are not diagonally dominant or SPD, sometimes producing an unstable preconditioner that makes things worse. Its quality is sensitive to the ordering of the unknowns and to the fill level you allow, and the triangular solves are inherently sequential, which limits parallel scalability. So ILU is a robust, easy first thing to try — but on structured PDE problems a tailored multigrid preconditioner usually beats it.
ILU(0) on a matrix with 5 nonzeros per row produces L and U also with about 5 nonzeros per row (no extra fill stored), so applying M^{-1} is two sparse triangular solves. A complete LU of the same matrix might have hundreds of nonzeros per row after fill-in — far costlier.
Factor A approximately, discard the fill-in — a cheap, sparse stand-in for the true L and U.
Incomplete factorization is not guaranteed to exist or be stable: for non-SPD, non-diagonally-dominant matrices it can hit a zero pivot and break down, or yield a poor preconditioner. Its serial triangular solves also limit parallel performance, which is why structured problems often prefer multigrid.