BILUTM: A Domain-Based Multi-Level Block ILUT Preconditioner for General Sparse Matrices

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


This paper describes a domain-based multi-level block ILU preconditioner (BILUTM) for solving general sparse linear systems. This preconditioner combines a high accuracy incomplete LU factorization with an algebraic multi-level recursive reduction. Thus, in the first level the matrix is permuted into a block form using (block) independent set ordering and an ILUT factorization for the reordered matrix is performed. The reduced system is the approximate Schur complement associated with the partitioning and it is obtained implicitly as a by-product of the partial ILUT factorization with respect to the complement of the independent set. The incomplete factorization process is repeated with the reduced systems recursively. The last reduced system is factored approximately using ILUT again. The successive reduced systems are not stored. This implementation is efficient in controlling the fill-in elements during the multi-level block ILU factorization, especially when large size blocks are used in domain decomposition type implementations. Numerical experiments are used to show the robustness and efficiency of the proposed technique for solving some difficult problems.

Key words: Incomplete LU factorization, ILUT, multi-level ILU preconditioner, Krylove subspace methods, multi-elimination ILU factorization.

1991 AMS subject classifications: 65F10, 65F50, 65N55, 65Y05.

This research was supported in part by NSF and Minnesota Supercomputer Institute. This paper has been accepted for publication in SIAM Journal on Matrix Analysis and Applications. It has also been published as: Technical Report UMSI 98/118, Minnesota Supercomputer Institute, Univerity of Minnesota, Minneapolis, MN 55455, 1998.