RILUM: A General Framework for Robust Multilevel
Recursive Incomplete LU Preconditioning Techniques

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


We introduce a general framework for constructing multilevel recursive incomplete LU preconditioning techniques (RILUM) for solving general sparse matrices. This technique is based on a recursive two by two block incomplete LU factorization on the coefficient matrix. The coarse level system is constructed as an (approximate) Schur complement. A dynamic preconditioner is obtained by solving the Schur complement matrix approximately. The novelty of the proposed techniques is to solve the Schur complement matrix by a preconditioned Krylov subspace method. The very preconditioner for this secondary iteration is constructed by considering the Schur complement matrix as a general sparse matrix and by applying to it the block ILU factorization process that was applied to the original matrix. This recursive procedure continues for a few times and results in a multilevel preconditioner. Different implementation strategies are discussed. We conduct numerical experiments with two particular RILUM implementations to show the performance of the proposed techniques and to demonstrate grid independent convergence rates of RILUM for solving certain problems.

Key words: Multilevel recursive incomplete LU preconditioner, preconditioning techniques, sparse matrices.

This paper has been published in Korean Journal of Computational and Applied Mathematics, Vol. 8, No. 2, pp/ 213-234 (2001).

Technical Report 284-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.