Multi-Level Preconditioning Techniques for General Sparse Linear Systems *

Yousef Saad and Jun Zhang

Department of Computer Science and Engineering, and
Minnesota Supercomputer Institute,
University of Minnesota,
200 Union Street, S.E.,
Minneapolis, MN 55455


We introduce multi-level block incomplete LU (BILUM) factorization preconditioning techniques for solving general sparse linear systems. The preconditioner is constructed by using recursive block incomplete LU factorization from the original coefficient matrix. It has a multi-level structure and exhibits some properties that are usually characteristic of multigrid-type methods. Advantages of BILUM over the point version of ILUM (ILU with multi-elimination, Saad 1996) include increased robustness and computational efficiency. In this talk, we will focus on the use of large blocks as pivoting entries in constructing BILUM and discuss strategies to insure the sparsity of the resulting preconditioners. Numerical results, including tests with some hard-to-solve problems, are presented. They show that BILUM is more robust and converges faster than traditional single-level ILU preconditioners. Test results with certain problems are also presented to illustrate the near grid-independent convergence of the BILUMpreconditioned GMRES.

* Work supported by NSF/CCR and by the Minnesota Supercomputer Institute.