A Grid Based Multilevel Incomplete LU Factorization
Preconditioning Technique for General Sparse Matrices

Jun Zhang
Department of Computer Science
University of Kentucky
773 Anderson Hall
Lexington, KY 40506--0046, USA


We design a grid based multilevel incomplete LU preconditioner (GILUM) for solving general sparse matrices. This preconditioner combines a high accuracy ILU factorization with an algebraic multilevel recursive reduction. The GILUM preconditioner is a compliment to the domain based multilevel block ILUT preconditioner. A major difference between these two preconditioners is the way that the coarse level nodes are chosen. In this sense the approach of GILUM is analogous to that of algebraic multigrid method. However, the GILUM construction is completely different from the algebraic multigrid construction. A partial ILUT factorization is applied to the reordered matrix and the coarse level system is obtained implicitly. The incomplete factorization process is repeated with the coarse level systems recursively. The GILUM approach avoids some controversial issues in algebraic multigrid method such as how to construct the interlevel transfer operators and how to compute the coarse level operator. Numerical experiments are conducted to compare GILUM with other ILU preconditioners.

Key words: Incomplete LU factorization, multilevel ILU preconditioner, algebraic multigrid method, sparse matrices.

This paper has been published in Applied Mathematics and Computation, Vol. 124, Num. 1, 95-115, (2001). Technical Report No. 283-99, Department of Computer Science, University of Kentucky, Lexington, KY, 1999. This research was supported in part by the University of Kentucky Center for Computational Sciences.