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

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

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.