Robust Limited Memory Hybrid Sparse Solvers

鲁棒的有限内存混合稀疏求解器

• 批准号: 0102537
• 负责人: Padma Raghavan
• 金额: --
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-15 至 2006-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0102537&HistoricalAwards=false
• 关键词: Robust; Limited; Memory; Hybrid; Sparse

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.

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