Development, Analysis, and Implementation of Robust Algebraic Preconditioners for Sparse Linear Systems

稀疏线性系统鲁棒代数预处理器的开发、分析和实现

• 批准号: 0207599
• 负责人: Michele Benzi
• 金额: $ 13.82万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-15 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0207599&HistoricalAwards=false
• 关键词: Development; Analysis; Implementation; Robust; Algebraic

Benzi0207599 The solution of large, sparse systems of linear equations continues to be one of the fundamental problems of computational mathematics. Recent years have seen significative advances in the performance and robustness of iterative methods, prompted by the need to solve increasingly large systems of equations. The linear systems (and eigenvalue problems) arising from the discretization of partial differential equations in three space dimensions are too large for direct solution methods, and the only viable option is to use preconditioned Krylov subspace methods or, if applicable, multigrid-type methods. While robust and effective iterative solvers are available in the case of systems involving symmetric positive definite matrices or M-matrices, much work remains to be done in the case of indefinite systems. A major part of the project consists in the development of algebraic preconditioners for symmetric indefinite matrices. The investigator develops both incomplete factorization methods and sparse approximate inverses. He makes use of techniques developed by the direct solvers community, like pivoting strategies of the Bunch-Kaufman and Bunch-Parlett type. Preliminary experiments on saddle-point and shifted linear systems are encouraging. He also explores multilevel variants of these preconditoners. Special methods targeted to so-called KKT-type systems are investigated. Other parts of the project deal with the construction of robust preconditioners for least-squares problems, and for singular linear systems arising from Markov chain calculations. The latter problem is currently of particular interest due to recent applications in data mining. Specifically, the largest matrix problems currently being solved are the so-called "Google Problems", which amount to computing the stationary distribution vector of Markov chains with 2.7 billion states. Improvements in solution techniques have the potential of greatly affecting this important area. Advances in many important fields of science and technlogy depend on progress in mathematical algorithms used in computer simulations. A recent example is provided by the emerging field of data mining. The well-known search engine "Google" (see http://www.google.com) relies on the solution of an extremely large, sparse matrix model; in technical terms, a stochastic matrix, or Markov chain. This amounts to finding the solution to a very large set of simultaneous linear algebraic equations. Part of this project deals with finding improved solution methods for problems of this type. More generally, the project aims to solve challenging, large-scale problems in numerical linear algebra. The main goal is to develop efficient and robust algorithms, and related software, for solving difficult problems arising in various fields of engineering and physical sciences. Some other areas that would benefit from this work include computational fluid dynamics, structural analysis, acoustics, electromagnetics, and optimal control. In all of these areas, computer simulations are of paramount importance and there is a strong need for reliable and efficient solution algorithms and software.

Benzi0207599 大型稀疏线性方程组的求解仍然是计算数学的基本问题之一。近年来，迭代方法在性能和鲁棒性方面取得了显著的进步，这是由于需要求解越来越大的方程组。三维空间中偏微分方程的离散化所产生的线性系统（和特征值问题）对于直接求解方法来说太大了，唯一可行的选择是使用预处理Krylov子空间方法，或者如果适用的话，使用多重网格方法。虽然强大的和有效的迭代求解器的情况下，涉及对称正定矩阵或M-矩阵的系统，仍有许多工作要做的情况下，不确定的系统。该项目的一个主要部分包括在对称不定矩阵的代数预条件的发展。研究人员开发了不完全因子分解方法和稀疏近似逆。他利用了直接求解器社区开发的技术，如Bunch-Kaufman和Bunch-Parlett类型的旋转策略。鞍点和移位线性系统的初步实验令人鼓舞。他还探讨了这些先决条件的多层次变体。针对所谓的KKT型系统的特殊方法进行了研究。该项目的其他部分处理最小二乘问题的鲁棒预处理器的建设，并从马尔可夫链计算所产生的奇异线性系统。后一个问题是目前特别感兴趣的，由于最近的应用程序在数据挖掘。具体来说，目前正在解决的最大矩阵问题是所谓的“谷歌问题”，这相当于计算具有27亿个状态的马尔可夫链的平稳分布向量。解决方案技术的改进有可能极大地影响这一重要领域。 许多重要的科学和技术领域的进步依赖于计算机模拟中使用的数学算法的进步。最近的一个例子是新兴的数据挖掘领域。著名的搜索引擎“Google”（参见http://www.google.com）依赖于极大的稀疏矩阵模型的解决方案;在技术术语中，随机矩阵或马尔可夫链。这相当于找到一个非常大的联立线性代数方程组的解。该项目的一部分涉及为这类问题找到改进的解决方法。更一般地说，该项目旨在解决数值线性代数中具有挑战性的大规模问题。主要目标是开发高效和强大的算法和相关软件，用于解决工程和物理科学各个领域中出现的难题。一些其他领域，将受益于这项工作，包括计算流体动力学，结构分析，声学，电磁学和最优控制。在所有这些领域中，计算机模拟是至关重要的，并且强烈需要可靠和高效的解决方案算法和软件。