Performance Study and Analysis of Parallel Multilevel Preconditioners

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


The significant gap between peak and realized performance of parallel systems motivates the need for performance analysis. In order to predict the performance of a class of parallel multilevel ILU preconditioner (PBILUM), we build two performance prediction models for both the preconditioner construction phase and the solution phase. These models combine theoretical features of the preconditioners with estimates on computation cost, communications overhead, etc. Experimental simulations show that our model predication based on certain reasonable assumptions is close to the simulation results. The models may be used to predict the performance of this class of parallel preconditioners.

Key words: Sparse matrices, parallel preconditioning, multilevel preconditioning.

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

Download the compressed postscript file, or the PDF file perf.pdf.
Technical Report 387-03, Department of Computer Science, University of Kentucky, Lexington, KY, 2003.

This research work supported in part by the U.S. National Science Foundation under the grant CCR-9988165, CCR-0092532, ACI-0202934, and ACR-0234270, in part by the U.S. Department of Energy Office of Sceince under grant DE-FG02-02ER45961, and in part by the Kentucky Science \& Engineering Foundation under grant KSEF-02-264-RED-002.