Robust Limited Memory Hybrid Sparse Solvers

鲁棒有限内存混合稀疏求解器稀疏线性求解器可以大致分为“直接”和“迭代”两类。直接求解基于相关稀疏矩阵的分解，具有极强的鲁棒性。然而，由于原始零在分解过程中被填充，它们的内存需求随着矩阵维数的非线性函数而增长。Krylov子空间（KSP）迭代方法族是内存可伸缩的，但它们的收敛速度很慢或完全失败。该项目涉及开发可扩展的混合方法，这些混合方法可以参数化，以模拟从纯迭代方法到纯直接方法的范围。我们建议开发并行算法和软件工程方法，旨在提供鲁棒的、有限内存的混合求解器，以满足各种应用的计算需求。在算法方面，我们的重点是通过使用合适的不完全矩阵因子预处理KSP求解器获得的混合。这种预调节器具有鲁棒性和广泛的适用性，但直到最近才被认为不适合并行计算。主要原因是由于相对较高的通信延迟，应用前置条件的稀疏三角解成为瓶颈。我们最近开发了一种容忍延迟的“选择性反转”方案，克服了这个问题，实现了高效和可扩展的实现。在这个项目中，我们提出开发并行稀疏分解技术，该技术对整个填充谱都是有效的。我们将为可扩展的不完全分解开发一个新的“超节点对角允许块”公式。我们还将考虑结合符号（填充级别）和数字（阈值）策略的创新方法，以指定填充是保留还是丢弃。此外，我们的算法框架使我们能够为对称正定、对称不定和非对称系统提供一个单一的、统一的、可扩展的混合实现。在软件方面，我们定义了一个新的基于“逆向工程”过程的“使用模型”，以开发一个高性能的特定领域求解器，作为几种方法的智能组合。我们的前提是正确的复合求解器是特定于领域的；通过选择合适的底层方法组合来匹配线性系统属性，可以实现实质性的性能提升。通过开发一个利用参数化多态的面向对象稀疏模板库，我们将获得与各种并行稀疏求解器软件的统一接口。复合将通过使用该模板库和支持使用MPI进行并行计算的脚本语言来实例化。我们的设计目标和性能目标将关键于三个大规模的计算科学应用。第一个涉及高级优化的计算方法；这种应用需要鲁棒不定解。第二是结构力学应用，用于模拟裂缝和断裂。第三个应用涉及量子分子动力学中出现的大稀疏特征值问题。我们的项目代表了在并行稀疏矩阵计算领域解决关键研究问题的一致努力。我们的目标是通过结合并行算法和软件工程的研究来开发下一代稀疏求解器。

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.