Robust Limited Memory Hybrid Sparse Solvers

点击翻译按钮获取中文摘要

Robust Limited Memory Hybrid Sparse SolversSparse linear solvers can be broadly classified as being either 'direct' or 'iterative.' Direct solvers are basedon 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 convergencecan be slow or fail altogether. This project concerns developing scalable hybrids than can be parameterizedto model the range from pure iterative to pure direct methods. We propose to develop parallel algorithmsand software engineering methods aimed at providing robust, limited memory hybrid solvers that satisfy thecomputational demands of a variety of applications.On the algorithmic front, our focus is on hybrids obtained by preconditioning KSP solvers using suitableincomplete matrix factors. Such preconditioners are robust and widely applicable, but until recently theywere considered unsuitable for parallel computing. The main reason is that the sparse triangular solves forapplying the preconditioner become a bottleneck due to the relatively high latency of communication. Wehave recently developed a latency tolerant 'selective-inversion' scheme that overcomes this problem to yieldan efficient and scalable implementation. In this project, we propose developing parallel sparse factorizationtechniques that are efficient for the entire spectrum of fill-in. We will develop a new 'supernodal diagonalrow block' formulation for scalable incomplete factorization. We will also consider innovative ways ofcombining symbolic (level of fill) and numeric (threshold) strategies to specify fill-in to be either retainedor discarded. Additionally, our algorithmic framework enables us to provide a single, unified, extensibleimplementation 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 sparsematrix computations. Our goal is to develop the next generation of sparse solvers by combining research inparallel algorithms and software engineering.