Distributed Block Independent Set Algorithms and
Parallel Multilevel ILU Preconditioners

Chi Shen, Jun Zhang, and Kai Wang
Laboratory for High Performance Scientific Computing and Computer Simulation
Department of Computer Science
University of Kentucky
Lexington, KY 40506-0046, USA


We present a class of parallel preconditioning strategies utilizing multilevel block incomplete LU (ILU) factorization techniques to solve large sparse linear systems. The preconditioners are constructed by exploiting the concept of block independent sets. Two algorithms for constructing block independent sets of a sparse matrix in a distributed environment are proposed. We compare a few implementations of the parallel multilevel ILU preconditioners with different block independent set construction strategies and different Schur complement preconditioning strategies. We also use some diagonal thresholding and perturbation strategies for the block independent set construction and for the last level Schur complement ILU factorization. Numerical experiments indicate that our domain based parallel multilevel block ILU preconditioners are robust and efficient.

Key words: Parallel multilevel preconditioning, block independent set, sparse matrices, Schur complement techniques.

Mathematics Subject Classification: 65F10, 65F50, 65N55, 65Y05.

Download the compressed postscript file shen5.ps.gz, or the PDF file shen5.pdf.
This paper has been accepted for publication in Journal of Parallel and Distributed Computing, Vol. 65, pp. 331--346 (2005).

Also as Technical Report 358-02, Department of Computer Science, University of Kentucky, Lexington, KY, 2002.

This research work supported in part by the U.S. National Science Foundation under the grant CCR-9902022, CCR-9988165, CCR-0092532, and ACI-0202934, in part by the U.S. Department of Energy Office of Sceince under grant DE-FG02-02ER45961, in part by the Japanese Research Organization for Information Science & Technology, and in part by the University of Kentucky Research Committee.