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求解器获得的混合。这样的预条件是强大的和广泛适用的，但直到最近，他们被认为是不适合并行计算。主要原因是由于通信延迟相对较高，应用预处理器的稀疏三角解成为瓶颈。我们最近开发了一个延迟容忍的“选择性反转”计划，克服了这个问题，yieldan高效和可扩展的实现。在这个项目中，我们建议开发并行稀疏factorizationtechniques，是有效的整个频谱的填充。我们将开发一个新的'supernodal diagonalrow块'制定可扩展的不完全因式分解。我们还将考虑结合符号（填充级别）和数字（阈值）策略的创新方法，以指定填充是保留还是丢弃。此外，我们的算法框架使我们能够提供一个单一的，统一的，可扩展的实现对称正定，对称不确定，和非对称system.On软件方面，我们定义了一个新的“使用模型”为基础的“逆向工程”过程开发一个高性能的特定领域的求解器作为一个智能复合的几种方法。我们的前提是正确的复合求解器是特定于域的;通过选择合适的底层方法组合来匹配线性系统属性，可以实现显著的性能增益。我们将获得一个统一的接口，各种并行稀疏求解器软件开发一个面向对象的稀疏模板库，利用参数化多态性。复合材料将使用这个模板库和一个脚本语言，支持并行计算使用MPI实例化。我们的设计目标和性能目标将是关键的三个大规模的计算科学应用。第一个问题涉及先进的优化计算方法，这个应用程序需要强大的不确定求解器。第二个是结构力学应用程序，用于对裂缝和断裂进行建模。第三个应用程序涉及量子分子动力学中出现的大型稀疏特征值问题。我们的项目代表了一个共同努力，以解决并行稀疏矩阵计算领域的关键研究问题。我们的目标是通过结合并行算法研究和软件工程来开发下一代稀疏求解器。