Advances in Robust Multilevel Preconditioning Methods for Sparse Linear Systems

许多学科的科学家和工程师，从机械或航空航天工程到化学和经济学，都需要求解大型线性方程组。这些系统通常是“稀疏的”，因为它们的大多数条目都是零。由三维物理系统产生的线性系统通常通过标准的直接消去法(也称为直接消去法)来求解，成本非常高。在这种情况下，产生解的近似序列的迭代方法成为强制性的。近年来，这些方法取得了重要进展，但它们在处理各种现实生活问题时缺乏稳健性仍然是一个问题。最近对所谓的预条件Krylov子空间方法的研究旨在通过结合来自不同水平的技术来实现通用性和效率之间的良好折衷，包括提高可伸缩性的多级概念和吸收直接求解方法的思想来提高鲁棒性。在部署这些改进的同时，具有挑战性的应用程序以及新的计算环境的新需求正在使通常需要数十年才能成熟的过时算法和计算代码变得过时。这个项目的目的是解决近年来迭代方法出现的这些新的需求和挑战，以及探索其他具有重要实际意义的研究问题。本项目将探索一类求解线性方程组的迭代方法，强调稳健性和可伸缩性问题。该研究的出发点是在区域分解(DD)型方法中研究一组新的多层低阶(MLR)逼近技术。MLR预处理方，特别是在DD框架内，具有巨大的潜力，原因有很多。首先，由于它们依赖于近似逆，这些方法往往比它们的不完全逻辑单元(ILU)对应的方法更健壮。因此，当处理高度不确定的线性系统时，它们可能比现有方法更有效，例如，那些由波散射模拟引起的系统。其次，MLR不需要因式分解，是高性能计算机的极佳候选者，例如配备图形处理单元(GPU)的计算机。最后，它们很容易更新，因为在观察到的性能不令人满意的情况下，为了提高它们的准确性，增加或改进它们是廉价的。我们将探索定义低阶近似的不同方法，这些方法都植根于域分解框架和Schur补码技术。该项目还将继续探索标准的多级预处理器，高度重视稳健性问题。最后，还将审议与高性能计算的影响和开发有效软件有关的其他重要议题。在这项研究的更广泛影响中，该项目突出了计算机软件的传播和在一个至关重要且日益重要的领域对学生的培训。此外，为教育目的，国际宣传会继续免费传播文章、书籍、讲稿和MatLab讲稿。

Scientists and engineers in many disciplines, ranging from mechanical or aerospace engineering to chemistry and economics, need to solve large linear systems of equations. These systems are typically 'sparse' in that most of their entries are zeros. Linear systems that arise from three-dimensional physical systems are often exceedingly costly to solve by standard direct elimination, also called direct methods. In such cases, iterative methods, which produce a sequence of approximations to the solution, become mandatory. These methods have made important advances in recent years but their lack of robustness when dealing with a variety of real-life problems remains an issue. Recent research on so-called Preconditioned Krylov Subspace Methods has aimed at achieving a good compromise between generality and efficiency by incorporating techniques from different horizons, including multilevel concepts to improve scalability and adopting ideas from direct solution methods to improve robustness. At the same time that these improvements are being deployed, new demands from challenging applications as well as from the new computational environments are making obsolete algorithms and computational codes that often took several decades to mature. The aim of this project is to address these new demands and the challenges that have emerged for iterative methods in recent years, as well as to explore other research issues that are of great practical importance.This project will explore a class of iterative methods for solving linear systems of equations, emphasizing robustness and scalability issues. The starting point of the proposed research is to investigate a new set of Multi-Level Low-Rank (MLR) approximation techniques within Domain-Decomposition (DD) type methods. MLR preconditioners, especially within the DD framework have a great potential for a number of reasons. First, because they rely on approximate inverses, these methods tend to be far more robust than their Incomplete LU (ILU) counterparts. As such they can be much more effective than existing methods when dealing with highly indefinite linear systems, e.g., those arising from wave scattering simulations. 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 that are all rooted in the Domain-Decomposition framework and Schur complement techniques. This project will also continue to explore standard multi-level preconditioners, placing a high emphasis on robustness issues. Finally, other important topics related to the impact of high-performance computing on the one hand and to the development of effective software on the other will be considered. Among the broader impacts of this research the project highlights the dissemination of computational software and the training of students in an area that is of vital and growing importance. In addition, the PI will continue the practice of freely disseminating articles, books, lecture notes, and MATLAB scripts for educational purposes.