Distributed block independent set algorithms and parallel multilevel ILU preconditioners

Chi Shen; Jun Zhang; Kai Wang

doi:10.1016/j.jpdc.2004.10.007

Distributed block independent set algorithms and parallel multilevel ILU preconditioners

Chi Shen, Jun Zhang, Kai Wang

Computer Science

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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 language	English
Pages (from-to)	331-346
Number of pages	16
Journal	Journal of Parallel and Distributed Computing
Volume	65
Issue number	3
DOIs	https://doi.org/10.1016/j.jpdc.2004.10.007
State	Published - 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.

Funding

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. 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.

Funders	Funder number
Japanese Research Organization for Information Science and Technology
University of Kentucky Research Committee
National Science Foundation (NSF)	CCR-0092532, CCR-9902022, ACI-0202934, CCR-9988165
Michigan State University-U.S. Department of Energy (MSU-DOE) Plant Research Laboratory	DE-FG02-02ER45961

Keywords

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

Access to Document

10.1016/j.jpdc.2004.10.007

Cite this

@article{f78cd993add4437f90d232af69884b8a,

title = "Distributed block independent set algorithms and parallel multilevel ILU preconditioners",

abstract = "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.",

keywords = "Block independent set, Parallel multilevel preconditioning, Schur complement techniques, Sparse matrices",

author = "Chi Shen and Jun Zhang and Kai Wang",

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. ",

year = "2005",

month = mar,

doi = "10.1016/j.jpdc.2004.10.007",

language = "English",

volume = "65",

pages = "331--346",

number = "3",

}

TY - JOUR

T1 - Distributed block independent set algorithms and parallel multilevel ILU preconditioners

AU - Shen, Chi

AU - Zhang, Jun

AU - Wang, Kai

N1 - 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.

PY - 2005/3

Y1 - 2005/3

N2 - 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.

AB - 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.

KW - Block independent set

KW - Parallel multilevel preconditioning

KW - Schur complement techniques

KW - Sparse matrices

UR - http://www.scopus.com/inward/record.url?scp=14544294386&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=14544294386&partnerID=8YFLogxK

U2 - 10.1016/j.jpdc.2004.10.007

DO - 10.1016/j.jpdc.2004.10.007

M3 - Article

AN - SCOPUS:14544294386

SN - 0743-7315

VL - 65

SP - 331

EP - 346

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 3

ER -

Distributed block independent set algorithms and parallel multilevel ILU preconditioners

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this