Edmond Chow
Iterative Construction of ILU Preconditioners

School of Computational Science and Engineering
Georgia Institute of Technology
echow@cc.gatech.edu
Aftab Patel

An incomplete LU (ILU) factorization is generally computed by a Gaussian elimination process where certain nonzeros are neglected in some way. Here, we present a completely different method for computing ILU factorizations. The new method is iterative in nature and is highly parallel. Given a matrix $A$ , the new method computes the incomplete factors $L$ and $U$ by using the property

$$(L U)_{ij} = a_{ij}, \quad (i,j) \in S$$ (1)

where $(LU)_{ij}$ denotes the $(i,j)$ entry of the product $LU$ , $a_{ij}$ denotes the $(i,j)$ entry of $A$ , and $S$ denotes a set of matrix locations where nonzeros are allowed. In other words, the factorization is exact on the sparsity pattern $S$ . The precursors to ILU methods in separate works by Buleev, Oliphant, and Varga in the early 1960's constructed matrix factorizations in a similar fashion, much before they were recognized as a form of Gaussian elimination.

The new method interprets an ILU factorization as, instead of a Gaussian elimination process, a problem of computing the unknowns $l_{ij}$ and $u_{ij}$ , which are the entries of $L$ and $U$ , using property (1) as constraint equations. Such an approach may seem impractical because these equations are nonlinear and there are more equations than the number of rows in $A$ . However, there are several potential advantages to computing an ILU factorization this way: 1) the equations can be solved in parallel without needing to reorder the matrix $A$ , 2) the equations do not need to be solved very accurately to produce a good ILU preconditioner, and 3) we often have a good initial guess for the solution.

The constraint equations may be solved via a fixed-point iteration, or a parallel asynchronous iteration in the parallel setting. We will present theoretical and experimental results on the convergence of these methods for computing ILU factorizations. The fact that the method is iterative means that the exact ILU factorization does not need to be computed, and we show experimentally that roughly converged iterations produce factorizations that are very effective preconditioners. Furthermore, the number of iterations required is typically very small (less than 5), especially when good initial guesses for the ILU factorization are available, such as in the case when solving a sequence of related linear systems. We can also interpret the new method as a way of updating an existing ILU preconditioner.