Advances in Robust Multilevel Preconditioning Methods for Sparse Linear Systems

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

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.