Advances in Robust Multilevel Preconditioning Methods for Sparse Linear Systems

稀疏线性系统鲁棒多级预处理方法的进展

• 批准号: 1912048
• 负责人: Yousef Saad
• 金额: $ 30万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-08-01 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1912048&HistoricalAwards=false
• 关键词: Advances; Robust; Multilevel; Preconditioning; Methods

Solving linear systems of equations is at the heart of many large scale numerical simulations in sciences and engineering. These systems can have tens or hundreds of millions simulations in the aerodynamic design of airplanes and equilibrium models in macro-economics. In most common situations, the equations encountered in these applications are 'sparse' in the sense that each equation involves a small number of unknowns or parameters. This project is about the effective solution of such systems by a class of methods that are termed 'iterative'. An iterative method does not attempt to compute an exact solution by the age-old method of elimination. Instead, it generates a sequence of approximations that gradually approaches the solution. However, in spite of the numerous advances made in past decades in iterative solution methods for linear systems, practitioners still face difficulties when applying these methods to certain types of problems. The proposal aims at advancing the state-of-the art in a specific class called Preconditioning Krylov subspace methods. In essence, the techniques proposed combine preconditioners (making the problem easier to solve by exploiting approximate elimination), with good acceleration methods (combining successive iterates to accelerate convergence) and Domain Decomposition ideas (decomposing the problem into parts so as to exploit parallel treatment of each part).This project focuses on the class of Preconditioned Krylov Subspace Methods (PKSMs) for solving linear systems of equations. These methods try to reach a compromise between generality and efficiency by combining an accelerator (e.g., GMRES) and a preconditioner (e.g., Incomplete LU or Algebraic Multi-Grid). It is now well-known that the preconditioner holds the key to the success of this combination. The primary goal of this project is to address the two most important weaknesses of these methods. Their first weakness is their lack robustness in some situations, e.g., when the linear system at hand is highly indefinite or ill-conditioned. In the past researchers have often limited their attention to diagonally dominant systems that arise from discretizing Poisson-like equations. However, the more realistic problems addressed by engineers and scientists have become much harder to solve, leading to a demand for new types of preconditioners. The second weakness of iterative methods is that preconditioners have traditionally been developed with sequential environments in mind, and therefore they often perform poorly in parallel environments. An effort must be made to develop better, more scalable, parallel methods by adopting a view-point that is based on domain-decomposition from the start. To improve the parallel efficiency of preconditioners it is vital to incorporate ideas that exploit a multilevel paradigm. A second avenue to be explored in this project aims primarily at improving robustness by a class of methods that will extend and optimize a strategy based on the Cauchy integral formula for developing preconditioners. The starting point of the project is to expand the PI's research on Multi-Level Low-Rank (MLR) approximation techniques, focusing on a parallel Domain Decomposition framework. MLR techniques have shown a great potential in addressing the issues raised above. First, they rely on an approximate inverse viewpoint and as such these methods tend to be far more robust than their Incomplete LU (ILU) counterparts. They can handle highly indefinite linear systems, such as those arising from wave scattering simulations, more effectively than existing methods. Second, MLRs do not require factorizations and are excellent candidates for high-performance computers, e.g., ones equipped with Graphical Processing Units (GPUs). Finally, they are easy to update in that it is inexpensive to augment or refine them in order to improve their accuracy in the situation when their observed performance is not satisfactory. Different ways to define low-rank approximations will be explored which are all rooted in the Domain-Decomposition framework and Schur complement techniques. The second part of the planned work is to consider extensions of the idea of incorporating complex shifts when solving linear systems. The techniques to be developed here will aim specifically at highly indefinite systems such as those that arise from wave propagation phenomena (Helmholtz, Maxwell). The broader impacts of this project include the free distribution of general purpose codes developed by the PI's research team, and the training of graduate and undergraduate students at a time where demand for specialists in computational mathematics is strong. Among other training activities, the PI will continue the practice of freely disseminating books (two books currently available), lecture notes (three courses currently posted), and MATLAB scripts for educational purposes, as these can play a major role in promoting knowledge and know-how in the theory and application of numerical linear algebra.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

求解方程式的线性系统是许多大规模数值模拟和工程中的核心。这些系统可以在宏观经济学中的飞机和平衡模型的空气动力学设计中具有数千万个模拟。在大多数常见情况下，这些应用程序中遇到的方程式是“稀疏”的，因为每个方程都涉及少数未知数或参数。该项目是关于通过称为“迭代”的一类方法对此类系统的有效解决方案的。迭代方法不会尝试通过古老的消除方法来计算精确的解决方案。取而代之的是，它生成一系列近似序列，这些近似值逐渐接近解决方案。但是，尽管过去几十年来线性系统的迭代解决方案方法取得了许多进步，但在将这些方法应用于某些类型的问题时，从业人员仍然面临困难。该提案旨在在特定类别的“预处理Krylov子空间方法”中推进最先进的艺术。 In essence, the techniques proposed combine preconditioners (making the problem easier to solve by exploiting approximate elimination), with good acceleration methods (combining successive iterates to accelerate convergence) and Domain Decomposition ideas (decomposing the problem into parts so as to exploit parallel treatment of each part).This project focuses on the class of Preconditioned Krylov Subspace Methods (PKSMs) for solving linear方程系统。这些方法试图通过组合加速器（例如GMRE）和预处理器（例如，LU或代数多机）结合加速器（例如GMRE）和效率之间的妥协。现在众所周知，预科人员是该组合成功的关键。该项目的主要目标是解决这些方法的两个最重要的弱点。他们的第一个弱点是他们在某些情况下缺乏鲁棒性，例如，当手头的线性系统高度不确定或条件不足时。过去，研究人员经常将注意力限制在因对角占主导地位的系统上，这些系统是由泊松式方程式离散而产生的。但是，工程师和科学家解决的更现实的问题已经变得更加难以解决，从而导致对新型预处理的需求。迭代方法的第二个弱点是传统上已经考虑了顺序环境，因此在平行环境中经常表现较差。必须通过从一开始就采用基于域分解的视点来做出更好，更可扩展的并行方法。为了提高预处理的并行效率，至关重要的是结合利用多层次范式的思想。该项目中要探索的第二大道主要是通过一类方法来改善鲁棒性，这些方法将扩展和优化基于Cauchy Integrant公式的策略，以开发预调节器。该项目的起点是扩展PI对多级低级别（MLR）近似技术的研究，重点是平行域分解框架。 MLR技术在解决上述问题方面具有巨大的潜力。首先，它们依赖于近似的逆观点，因此，这些方法往往比其不完整的LU（ILU）对应物更强大。与现有方法相比，他们可以处理高度无限的线性系统，例如波浪散射模拟引起的那些系统。其次，MLR不需要因素化，并且是具有图形处理单元（GPU）的高性能计算机的出色候选者。最后，它们很容易更新，因为在观察到的性能不满意的情况下，增加或完善它们是为了提高其准确性是很便宜的。将探索定义低级近似值的不同方法，这些方法都植根于域分解框架和Schur补体技术。计划工作的第二部分是考虑在求解线性系统时结合复杂变化的想法的扩展。这里要开发的技术将专门针对高度不确定的系统，例如由波传播现象（Helmholtz，Maxwell）引起的系统。该项目的更广泛的影响包括PI研究团队开发的通用代码的自由分发，以及在计算数学专家的需求强劲的时候，对研究生和本科生进行了培训。 Among other training activities, the PI will continue the practice of freely disseminating books (two books currently available), lecture notes (three courses currently posted), and MATLAB scripts for educational purposes, as these can play a major role in promoting knowledge and know-how in the theory and application of numerical linear algebra.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and更广泛的影响审查标准。

项目成果

A Parallel Algorithm for Computing Partial Spectral Factorizations of Matrix Pencils via Chebyshev Approximation

通过切比雪夫近似计算矩阵笔部分谱分解的并行算法

• DOI: 10.1137/22m1501155
• 发表时间: 2023
• 期刊: SIAM Journal on Scientific Computing
• 影响因子: 3.1
• 作者: Xu, Tianshi;Austin, Anthony;Kalantzis, Vasileios;Saad, Yousef
• 通讯作者: Saad, Yousef

A power Schur complement Low-Rank correction preconditioner for general sparse linear systems

• DOI: 10.1137/20m1316445
• 发表时间: 2020-02
• 期刊: ArXiv
• 作者: Q. Zheng;Yuanzhe Xi;Y. Saad

Multicolor low‐rank preconditioner for general sparse linear systems

• DOI: 10.1002/nla.2316
• 发表时间: 2020-06
• 期刊: Numerical Linear Algebra with Applications
• 影响因子: 4.3
• 作者: Q. Zheng;Yuanzhe Xi;Y. Saad

parGeMSLR: A parallel multilevel Schur complement low-rank preconditioning and solution package for general sparse matrices

parGeMSLR：用于一般稀疏矩阵的并行多级 Schur 补充低秩预处理和解决方案包

• DOI: 10.1016/j.parco.2022.102956
• 发表时间: 2022
• 期刊: Parallel Computing
• 影响因子: 1.4
• 作者: Xu, Tianshi;Kalantzis, Vassilis;Li, Ruipeng;Xi, Yuanzhe;Dillon, Geoffrey;Saad, Yousef
• 通讯作者: Saad, Yousef

Proxy-GMRES: Preconditioning via GMRES in Polynomial Space

Proxy-GMRES：通过多项式空间中的 GMRES 进行预处理

• DOI: 10.1137/20m1342562
• 发表时间: 2021
• 期刊: SIAM Journal on Matrix Analysis and Applications
• 影响因子: 1.5
• 作者: Ye, Xin;Xi, Yuanzhe;Saad, Yousef
• 通讯作者: Saad, Yousef