BILUM: Block Versions of Multi-Elimination and Multi-Level
ILU Preconditioner for General Sparse Linear Systems

Yousef Saad and Jun Zhang
Department of Computer Science and Engineering
University of Minnesota
4-192 EE/CS Building, 200 Union Street S.E.
Minneapolis, MN 55455, USA


We introduce block versions of the multi-elimination incomplete LU (ILUM) factorization preconditioning technique for solving general sparse unstructured linear systems. These preconditioners have a multi-level structure and can be shown to have some properties that are typically enjoyed by multigrid methods. Several heuristic strategies for forming blocks of independent set are introduced and their relative merits are discussed. Advantages of block ILUM over point ILUM include increased robustness and efficiency. We compare several versions of the block ILUM, point ILUM and the dual-threshold-based ILUT preconditioners. In particular, the ILUM preconditioned Krylov subspace solver is tested for some convection-diffusion problems to show convergence that is near Reynolds number independent and near grid independent.

Key words: Incomplete LU factorization, multi-level preconditioner, GMRES, multi-elimination incomplete LU factorization.

This research was supported in part by ARPA, NSF and Minnesota Supercomputer Institute.
This paper has been published in SIAM Journal on Scientific Computing, Vol. 20, Num. 6, 2103-2121, 1999. It has also been published as: Technical Report UMSI 97/126, Minnesota Supercomputer Institute, Univerity of Minnesota, Minneapolis, MN 55455, 1997.