Robust Limited Memory Hybrid Sparse Solvers

Pennsylvania State Univ University Park, University Park PA

Investigators

Abstract

Robust Limited Memory Hybrid Sparse Solvers Sparse linear solvers can be broadly classified as being either 'direct' or 'iterative.' Direct solvers are based on a factorization of the associated sparse matrix and are extremely robust. However, their memory requirements grow as a non-linear function of the matrix dimension because original zeroes fill-in during factorization. The Krylov subspace (KSP) family of iterative methods are memory scalable, but their convergence can be slow or fail altogether. This project concerns developing scalable hybrids than can be parameterized to model the range from pure iterative to pure direct methods. We propose to develop parallel algorithms and software engineering methods aimed at providing robust, limited memory hybrid solvers that satisfy the computational demands of a variety of applications. On the algorithmic front, our focus is on hybrids obtained by preconditioning KSP solvers using suitable incomplete matrix factors. Such preconditioners are robust and widely applicable, but until recently they were considered unsuitable for parallel computing. The main reason is that the sparse triangular solves for applying the preconditioner become a bottleneck due to the relatively high latency of communication. We have recently developed a latency tolerant 'selective-inversion' scheme that overcomes this problem to yield an efficient and scalable implementation. In this project, we propose developing parallel sparse factorization techniques that are efficient for the entire spectrum of fill-in. We will develop a new 'supernodal diagonal row block' formulation for scalable incomplete factorization. We will also consider innovative ways of combining symbolic (level of fill) and numeric (threshold) strategies to specify fill-in to be either retained or discarded. Additionally, our algorithmic framework enables us to provide a single, unified, extensible implementation of hybrids for symmetric positive definite, symmetric indefinite, and nonsymmetric systems. On the software front, we define a new 'usage model' based 'reverse engineering' process to develop a high-performance domain specific solver as a smart composite of several methods. Our premise is that the right composite solver is domain specific; substantial performance gains can be realized by selecting the right combination of underlying methods to match linear system attributes. We will obtain a uniform interface to a variety of parallel sparse solver software by developing an object-oriented sparse template library that utilizes parameterized polymorphism. Composites will be instantiated by using this template library and a scripting language that supports parallel computing using MPI. Our design goals and performance targets will be keyed to three large-scale computational science applications. The first concerns computational methods for advanced optimization; this application requires robust indefinite solvers. The second is a structural mechanics application for modeling cracks and fractures. The third application involves large sparse eigenvalue problems that arise in quantum molecular dynamics. Our project represents a concerted effort to resolve critical research issues in the area of parallel sparse matrix computations. Our goal is to develop the next generation of sparse solvers by combining research in parallel algorithms and software engineering.