Diagonal Threshold Techniques in Robust Multi-Level
ILU Preconditioners 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

Abstract

This paper introduces techniques based on diagonal threshold tolerance when developing multi-elimination and multi-level incomplete LU (ILUM) factorization preconditioners for solving general sparse linear systems. Existing heuristics solely based on the adjacency graph of the matrices have been used to find independent sets and are not robust for matrices arising from certain applications in which the matrices may have small or zero diagonals. New heuristic strategies based on the adjacency graph and the diagonal values of the matrices for finding independent sets are introduced. Analytical bounds for the factorization and preconditioned errors are obtained for the case of a two-level analysis. These bounds provide useful information in designing robust ILUM preconditioners. Extensive numerical experiments are conducted in order to compare robustness and efficiency of various heuristic strategies.


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

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


This paper is published in Numerical Linear Algebra with Applications, 6(4), 257-280 (1999). This research was support by NSF and Minnesota Supercomputer Institute. Technical Report UMSI 98/7, Minnesota Supercomputer Institute, Univerity of Minnesota, Minneapolis, MN 55455, 1998. This paper has been accepted for publication in Numerical Linear Algebra with Applications.