Developing an Efficient Hybrid ICCG Solver

Esmond G. Ng

Computer Science and Mathematics Division
Oak Ridge National Laboratory
P.O. Box 2008, Oak Ridge, TN 37831-6367


Abstract

Large linear systems associated with sparse, symmetric positive-definite matrices can be solved using the method of "Conjugate Gradients" with incomplete Cholesky preconditioners (ICCG). Such ICCG schemes for solving large, sparse linear systems offer the potential for combining the best features of both direct and iterative solvers.

We report on the performance of ICCG using both levels of fill and drop threshold IC preconditioners. Our experiments involve several fill-reducing orderings, as well as a variety of schemes to allow a wide range of "incompleteness." Our experiments indicate that drop threshold IC is more robust and general-purpose than IC based on levels of fill.

We develop a "hybrid" solver based on ICCG with a "block" drop threshold scheme. The overall "blocked" code is aimed at improved use of the memory hierarchy by identifying and using dense blocks or panels. Such dense blocks or panels are used to efficiently compute and apply the IC preconditioner.

Our goal to make the overall solver deliver good performance for a range of preconditioning, i.e., from a nearly pure CG solver with very little preconditioning to a nearly direct solver incurring a substantial amount of fill. We report on the performance of such a flexible, hybrid solver on serial and shared-memory multiprocessors.

This is joint work with John G. Gilbert (Xerox PARC), Barry W. Peyton (ORNL), and Padma Raghavan (The University of Tennessee).