Scalable Sparse Solvers

在高性能多处理器上高效求解大型稀疏线性系统一直是研究的主题。 没有一种方法在应用程序领域和计算平台上始终是上级的。 例如，对于与椭圆型偏微分方程的数值解相关联的线性系统，区域分解方法提供了自然并行的高效公式。 然而，区域分解依赖于密切联系的偏微分方程离散化和网格制定。 因此，它不适合作为一个通用的“黑箱”稀疏求解器只给出稀疏矩阵，没有其他信息。 Krylov子空间迭代（KSP）求解器和直接求解器都可以用作“黑箱”求解器。 但是，这两类方法都有严重的局限性。 直接求解器（基于某种形式的矩阵分解）不是内存可扩展的;当原始零填充时，内存需求随问题大小非线性增长。 KSP迭代求解器避免了记忆问题，但它们的收敛速度可能非常慢或完全失败，这取决于稀疏矩阵的谱特性。强大的，可扩展的稀疏求解器，适用于各种大规模的高性能多处理器上的应用程序，需要一系列的方法，从纯迭代到纯直接的方法。 这个项目将开发并行的，“灵活的”混合求解器的基础上KSP矩阵分解预条件。 开发的混合求解器将结合联合收割机固有的可扩展性和并行性的KSP迭代求解器与强大的预处理器获得使用数据结构，算法和图形技术从稀疏直接求解器。 该项目将在两个方面开展工作：（1）通过扩展现有技术开发可扩展的混合求解器，即，不完全因子分解预条件子，以及（2）通过使用结构和数值信息的组合来开发新的改进的“结构增强”矩阵因子预条件子。

The efficient solution of large, sparse linear systems on high-performance multiprocessors continues to be the subject of research. There is no single method that is consistently superior across application domains and computing platforms. For example, for linear systems associated with the numerical solutions of elliptic partial differential equations, domain decomposition methods provide a naturally parallel, efficient formulation. However, domain-decomposition relies on close tie-ins to partial-differential-equation discretization and mesh formulation. Consequently, it is not suitable as a general-purpose "black-box" sparse solver given only the sparse matrix and no other information. Both Krylov subspace iterative (KSP) solvers and direct solvers can be used as "black-box" solver. But, once again, both classes of methods have serious limitations. Direct solvers (based on some form of matrix factorization) are not memory scalable; memory requirement grows nonlinearly with problem size when original zeroes fill-in. KSP iterative solvers avoid the memory problem but their convergence can be very slow or fail altogether depending on the spectral properties of the sparse matrix. Robust, scalable sparse solver, suitable for a variety of large-scale applications on high-performance multiprocessors, require a spectrum of methods that range from pure iterative to pure direct methods. This project will develop parallel, "flexible," hybrid solvers based on KSP with matrix factorization preconditioners. The hybrid solvers developed will combine the inherent scalability and parallelism of KSP iterative solvers with robust preconditioners obtained using data-structures, algorithms and graph-techniques from sparse direct solver. The project will work on two fronts: (1) developing scalable, hybrid solvers by extending current technology, i.e., incomplete factorization preconditioners, and , (2) developing new improved "structurally enhanced" matrix factor preconditioners by using a combination of structural and numerical information.