Advances in Robust Multilevel Preconditioning Methods for Sparse Linear Systems

求解线性方程组是科学和工程中许多大规模数值模拟的核心。这些系统可以在飞机气动设计和宏观经济平衡模型中进行数千万或数亿次的模拟。在大多数情况下，这些应用中遇到的方程是“稀疏”的，因为每个方程都包含少量的未知数或参数。这个项目是关于这种系统的有效解决方案的一类方法，被称为“迭代”。迭代法并不试图通过古老的消去法来计算精确解。相反，它会生成一系列逐渐接近解的近似值。然而，尽管在过去的几十年里，在线性系统的迭代求解方法取得了许多进展，从业者仍然面临困难时，将这些方法应用到某些类型的问题。该提案旨在推进一个特定类别中的最新技术，称为预处理Krylov子空间方法。本质上，所提出的技术将联合收割机预处理器（通过利用近似消除使问题更容易解决），用好的加速方法（结合连续迭代以加速收敛）和区域分解思想（将问题分解为多个部分，以便利用每个部分的并行处理）。本项目的重点是一类预条件Krylov子空间方法（PKSMs）求解线性方程组的方法。这些方法试图通过结合加速剂（例如，GMRES）和预处理器（例如，不完全LU或代数多重网格）。现在众所周知，预条件子是这种组合成功的关键。该项目的主要目标是解决这些方法的两个最重要的弱点。它们的第一个弱点是在某些情况下缺乏鲁棒性，例如，当手头的线性系统是高度不确定的或病态的。在过去的研究人员往往限制了他们的注意力对角占优系统，产生离散泊松方程。然而，工程师和科学家解决的更现实的问题变得更加难以解决，导致对新型预处理器的需求。迭代方法的第二个弱点是，预处理器传统上是在顺序环境中开发的，因此它们在并行环境中通常表现不佳。必须努力通过从一开始就采用基于域分解的观点来开发更好的、更具可伸缩性的并行方法。为了提高并行效率的预处理器，它是至关重要的，采用多级范式的想法。在这个项目中要探索的第二条途径主要是通过一类方法来提高鲁棒性，这些方法将扩展和优化基于柯西积分公式的开发预处理器的策略。该项目的出发点是扩展PI对多级低秩（MLR）近似技术的研究，重点是并行区域分解框架。MLR技术在解决上述问题方面显示出巨大的潜力。首先，它们依赖于近似的逆视点，因此这些方法往往比它们的不完全LU（ILU）对应方法更鲁棒。它们可以处理高度不确定的线性系统，如波散射模拟所产生的，比现有的方法更有效。其次，MLR不需要因子分解，是高性能计算机的优秀候选者，例如，配备图形处理单元（GPU）的系统。最后，它们易于更新，因为当它们的观测性能不令人满意时，为了提高它们的准确性而对其进行扩充或改进是廉价的。不同的方法来定义低秩近似将探讨都植根于域分解框架和舒尔补技术。计划工作的第二部分是考虑扩展的想法，将复杂的转变时，解决线性系统。这里要发展的技术将专门针对高度不确定的系统，例如那些由波传播现象引起的系统（亥姆霍兹，麦克斯韦）。该项目的更广泛影响包括PI研究团队开发的通用代码的免费分发，以及在对计算数学专家需求强烈的时候对研究生和本科生的培训。在其他培训活动中，公共信息机构将继续免费散发书籍，（目前有两本书），讲义（目前发布的三门课程），以及用于教育目的的MATLAB脚本，因为这些可以在促进知识和知识方面发挥重要作用，该奖项反映了NSF的法定使命，并已被认为是值得通过评估的支持使用基金会的知识价值和更广泛的影响审查标准。

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.