Enhanced Multi-Level Block ILU Preconditioning
Strategies 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


This paper introduces several strategies to deal with pivot blocks in multi-level block incomplete LU factorization (BILUM) preconditioning techniques. These techniques are aimed at increasing the robustness and controlling the amount of fill-ins of BILUM for solving large sparse linear systems when large size blocks are used to form block independent set. Techniques proposed in this paper include double dropping strategies, approximate singular value decomposition, variable size blocks and use of arrowhead block submatrix. We point out the advantages and disadvantages of the new techniques and discuss their efficient implementations. Numerical experiments are conducted to show the usefulness of the new techniques in dealing with hard-to-solve problems arising from computational fluid dynamics. In addition, we discuss the relation between multi-level ILU preconditioning methods and algebraic multi-level methods.

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

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

Download the compressed postscript file enhanced.ps.gz, or the PDF file enhanced.pdf.gz.

This paper has been published in Journal of Computational and Applied Mathematics Vol. 130, No. 1-2, pp. 99-118 (2001).

This research was support by NSF and Minnesota Supercomputer Institute. Current citation for this paper is: Technical Report UMSI 98/98, Minnesota Supercomputer Institute, Univerity of Minnesota, Minneapolis, MN 55455, 1998.