A Fully Parallel Block Independent Set Algorithm
for Distributed Sparse Matrices

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

Abstract

We present a fully parallel algorithm for constructing block independent set for general sparse matrices in a distributed environment. The block independent set is used in the construction of parallel multilevel preconditioners in solving large sparse matrices on distributed memory parallel computers. We compare a few implementations of the parallel multilevel ILU preconditioners with different block independent set construction strategies. Numerical experiments indicate that the parallel block independent set algorithm is efficient in reducing both the parallel multilevel preconditioner construction time and the size of the last level reduced system.

Key words: Parallel multilevel preconditioning, block independent set, distributed sparse matrices.

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

Download the compressed postscript file fpbis.ps.gz, or the PDF file fpbis.pdf.gz.
Technical Report 365-03, Department of Computer Science, University of Kentucky, Lexington, KY, 2003.

This paper has been published in Parallel Computing, Vol. 29, No. 11-12, pp. 1685--1699, (2003).

The research work of C. Shen was supported in part by the U.S. National Science Foundation under grant CCR-0092532.

The research work of J. Zhang was supported in part by the U.S. National Science Foundation under grants CCR-9988165, CCR-0092532, and ACR-0202934, by the U.S. Department of Energy Office of Science under grant DE-FG02-02ER45961, by the Kentucky Science & Engineering Foundation under grant KSEF-02-264-RED-002, by the apanese Research Organization for Information Science & Technology, and by the University of Kentucky Research Committee.