Distributed block independent set algorithms and parallel multilevel ILU preconditioners

Chi Shen, Jun Zhang, Kai Wang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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 (BISs). Two algorithms for constructing BISs of a sparse matrix in a distributed environment are proposed. We compare a few implementations of the parallel multilevel ILU preconditioners with different BIS construction strategies and different Schur complement preconditioning strategies. We also use some diagonal thresholding and perturbation strategies for the BIS 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.

Original languageEnglish
Pages (from-to)331-346
Number of pages16
JournalJournal of Parallel and Distributed Computing
Issue number3
StatePublished - Mar 2005

Bibliographical note

Funding Information:
Jun Zhang received a Ph.D. from The George Washington University in 1997. He is an Associate Professor of Computer Science and Director of the Laboratory for High Performance Scientific Computing and Computer Simulation at the University of Kentucky. His research interests include large scale parallel and scientific computing, numerical simulation, computational medical imaging, and data mining and information retrieval. Dr. Zhang is associate editor and on the editorial boards of three international journals in computer simulation and computational mathematics, and is on the program committees of a few international conferences. His research work is currently funded by the U.S. National Science Foundation and the Department of Energy. He is recipient of National Science Foundation CAREER Award and several other awards.

Funding Information:
This research work was supported in part by the US National Science Foundation under Grants CCR-9902022, CCR-9988165, CCR-0092532, and ACI-0202934, by the US Department of Energy Office of Science under Grant DE-FG02-02ER45961, by the Japanese Research Organization for Information Science and Technology, and by the University of Kentucky Research Committee.


  • Block independent set
  • Parallel multilevel preconditioning
  • Schur complement techniques
  • Sparse matrices

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Distributed block independent set algorithms and parallel multilevel ILU preconditioners'. Together they form a unique fingerprint.

Cite this