Advances in Robust Multilevel Preconditioning Methods for Sparse Linear Systems

许多学科的科学家和工程师，从机械或航空航天工程到化学和经济学，都需要解决大型线性方程组。这些系统通常是“稀疏的”，因为它们的大多数条目都是零。由三维物理系统产生的线性系统，通常用标准的直接消去法（也称为直接法）来求解成本非常高。在这种情况下，产生一系列近似解的迭代方法就变得必不可少了。近年来，这些方法取得了重要进展，但在处理各种现实问题时，它们缺乏鲁棒性仍然是一个问题。最近对所谓的预条件Krylov子空间方法的研究旨在通过结合来自不同领域的技术，包括多层概念来提高可伸缩性和采用直接解决方法的思想来提高鲁棒性，从而在通用性和效率之间取得良好的妥协。在部署这些改进的同时，来自具有挑战性的应用程序以及新的计算环境的新需求正在使过时的算法和计算代码变得过时，这些算法和计算代码通常需要几十年才能成熟。该项目的目的是解决近年来迭代方法出现的这些新要求和挑战，以及探索其他具有重要实际意义的研究问题。本项目将探讨一类求解线性方程组的迭代方法，强调鲁棒性和可扩展性问题。本研究的出发点是在域分解（DD）类型的方法中研究一套新的多层次低秩（MLR）逼近技术。MLR预调节器，特别是在DD框架中，由于许多原因具有巨大的潜力。首先，因为它们依赖于近似逆，所以这些方法往往比它们的不完全逻辑单元（ILU）对应物健壮得多。因此，在处理高度不确定的线性系统时，例如，由波散射模拟产生的系统，它们可以比现有方法有效得多。其次，mlr不需要因式分解，是高性能计算机的优秀候选者，例如配备图形处理单元（gpu）的计算机。最后，它们易于更新，因为在观察到的性能不令人满意的情况下，为了提高它们的准确性而增加或改进它们是不昂贵的。我们将探讨定义低秩近似的不同方法，这些方法都植根于域分解框架和Schur互补技术。该项目还将继续探索标准的多级预调节器，高度强调鲁棒性问题。最后，将考虑与高性能计算的影响以及有效软件的开发有关的其他重要主题。在这项研究的广泛影响中，该项目强调了计算软件的传播和在一个至关重要且日益重要的领域对学生的培训。此外，PI将继续为教育目的自由传播文章、书籍、课堂讲稿和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.