About Incomplete LU
The Incomplete LU preconditioner performs an incomplete LU factorization of the system matrix A. That is, it drops small elements during the column-oriented Gaussian elimination (see Ref. 21 and Ref. 22). Thus it saves memory, and the resulting factors L and U are approximate. The resulting preconditioner is an approximation to A. The preconditioner supports threshold drop, fill-ratio drop, and threshold pivoting. It can optionally respect the nonzero pattern in the original matrix. The preconditioner accepts matrices in symmetric and Hermitian format but expands these to full storage before factorization.
Selecting a Drop Rule
The Incomplete LU preconditioner uses the threshold drop rule (the default) or the fill-ratio drop rule. The preconditioner drops (neglects) an element during the elimination phase if its absolute value is smaller than the Euclidean norm of the entire column times a drop tolerance. In contrast, the fill-ratio drop rule limits the number of nonzeros in the incomplete factors L and U, and it keeps the largest absolute values. The number of values it keeps depends on the number of nonzeros in the corresponding column of the original matrix times a fill-ratio factor. There are two exceptions to these drop rules:
•
The preconditioner never drops diagonal elements.
•
The preconditioner optionally drops nonzeros in positions where the original matrix is nonzero. To make the preconditioner drop them, clear the Respect pattern check box in the settings for the Incomplete LU preconditioner.
The primary problem with setting up a preconditioner is the tradeoff between resources (computer time and memory) and the preconditioner’s quality. The computational cost of setting up a preconditioner with the Incomplete LU preconditioner is at least proportional to the number of nonzeros in the produced factors L and U. An advantage of using the fill-ratio drop rule is that you can estimate and limit the cost beforehand; the main disadvantage is that the quality of the preconditioner is typically not as good as using the threshold drop rule with a drop tolerance resulting in the same number of nonzeros. However, with the threshold drop rule there is no good way of estimating resource requirements beforehand. Furthermore, there is no general formula for these drop rules that gives a drop tolerance or fill ratio that guarantees fast convergence for a certain iterative method. Therefore, it is often necessary to rely on experiments and experience for this difficult and, from a performance point of view, important choice.