Advances in Robust Multilevel Preconditioning Methods for Sparse Linear Systems

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

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

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.

从机械或航空航天工程到化学和经济学，许多学科的科学家和工程师都需要求解大型线性方程组。这些系统通常是“稀疏的”，因为它们的大多数条目都是零。由三维物理系统产生的线性系统通常用标准的直接消去法（也称为直接法）求解成本非常高。在这种情况下，产生一系列近似解的迭代方法成为强制性的。这些方法近年来取得了重要进展，但在处理各种现实问题时缺乏鲁棒性仍然是一个问题。最近的研究，所谓的预处理Krylov子空间方法的目的是实现一个很好的折衷之间的通用性和效率，从不同的视野，包括多层次的概念，以提高可扩展性，并采用直接解决方案的方法，以提高鲁棒性的技术。在部署这些改进的同时，来自具有挑战性的应用以及来自新的计算环境的新需求正在使过时的算法和计算代码变得过时，这些算法和计算代码通常需要几十年才能成熟。本项目的目的是为了解决这些新的需求和挑战，出现了迭代方法在最近几年，以及探索其他研究问题，是非常实际的重要性。本项目将探讨一类迭代方法求解线性方程组，强调鲁棒性和可扩展性的问题。所提出的研究的出发点是研究一组新的多层次低秩（MLR）近似技术域分解（DD）类型的方法。MLR预处理器，特别是在DD框架中，由于许多原因具有很大的潜力。首先，因为它们依赖于近似逆，所以这些方法往往比它们的不完全LU（ILU）对应方法更鲁棒。因此，当处理高度不确定的线性系统时，它们可以比现有方法有效得多，例如，这些是由波散射模拟产生的。其次，MLR不需要因子分解，是高性能计算机的优秀候选者，例如，配备图形处理单元（GPU）的系统。最后，它们易于更新，因为当它们的观测性能不令人满意时，为了提高它们的准确性而对其进行扩充或改进是廉价的。不同的方法来定义低秩近似将被探索，都植根于域分解框架和舒尔补技术。该项目还将继续探索标准的多级预处理器，高度重视鲁棒性问题。最后，将考虑与高性能计算的影响和有效软件的开发有关的其他重要主题。在这项研究的更广泛的影响中，该项目突出了计算软件的传播和学生在一个至关重要和日益重要的领域的培训。此外，PI将继续免费传播文章，书籍，讲座笔记和MATLAB脚本用于教育目的的做法。