DSCPACK-IC

A Parallel Direct-Iterative Hybrid Solver Through Flexible Incomplete Cholesky Preconditioning

Author: Keita Teranishi and Padma Raghavan

DSCPACK-IC is a general-purpose parallel drop-tolerance incomplete Cholesky preconditioner for the Conjugate Gradients iterative solution. This package is suitable for memory-efficient solution for systems where the coefficient matrix is symmetric, positive definite and sparse. The amount of nonzero entries in the preconditioner can be adjusted using the drop tolerance condition to model the range from nearly a pure iterative method to a pure direct method. Although the software supports this wide range of preconditioning, we expect it to perform best when the preconditioner allows a resonable fraction (10% or more) of the fill-in for the true sparse factor. This preconditioner is written in C; it uses MPI for inter-processor communication and provides an interface for KSP (Krylov Subspace Solvers) solvers in PETSc package. The implementation of this package is based on the DSCPACK direct solver to compute parallel ordering and symbolic factorization to support the fully parallel construction of the preconditioner and its application.

Traditionally, preconditioning through incomplete factors (though widely accepted as the method of choice on serial computers) has been considered infeasible for multiprocessors and networks of workstations. This is primarily because the large latencies of interprocessor communiation on such multiptocessors make applying the preconditioner using parallel substitution very inefficient.

This software is based on new techniques developed in Teranishi's thesis to address this problem. DSCPACK-IC provides scalable latency tolerant implementation using these techniques. The main new techniques concern preconditioner construction using `Selective Inversion (SI)' of a limited number of diagonal blocks which allow their application using parallel sparse matrix vector multiplication instead of substitution. To make preconditioner construction more efficient, we also propose the `Selective Sparse Approximate Inversion (SSAI)' scheme to construct such inverses in selected diagonal blocks.

We have just completed a first alpha-release of the package. We will provide this version upon your request by email to teranish@cse.psu.edu.

Related Publications

Keita Teranishi, Padma Raghavan, and Esmond Ng, A New Data Mapping Scheme for Latency Tolerant Distributed Triangular Solution, Proceedings of SC2002 High Performance Network and Computing, Baltimore MD, Nov. 16-22, 2002.
Padma Raghavan, Keita Teranishi, and Esmond Ng, A Latency Tolerant Hybrid Sparse Solver Scheme Using Incomplete Cholesky Factorization, Numerical Linear Algebra, Volume 10, pp. 541-560, 2003.
Keita Teranishi, Scalable Hybrid Sparse Linear Solvers, Ph.D. thesis, Department of Computer Science and Engineering, The Pennsylvania State University, December 2004.

This project has been supprted by NSF, "Robust Limited Memory Hybrid Sparse Solvers," Grant ACI-0102537 PI, duration 8/01-08/04 and Lawrence Berkeley National Labs (Department of Energy), "Terascale Optimal PDE Simulation: An Enabling Technology Center," PI, duration 5/02-5/04.