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.

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

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.