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

大型稀疏线性方程组的求解仍然是计算数学的基本问题之一。近年来，由于需要求解越来越大的方程组，迭代方法在性能和稳健性方面取得了显著的进步。三维空间偏微分方程组的离散化所产生的线性系统(和特征值问题)对于直接求解方法来说太大了，唯一可行的选择是使用预条件Krylov子空间方法，或者如果适用，使用多重网格型方法。虽然在涉及对称正定矩阵或M-矩阵的情况下，已有稳健而有效的迭代求解器可用，但对于不确定系统，仍有许多工作要做。该项目的一个主要部分是开发对称不定矩阵的代数预条件。研究者发展了不完全因式分解方法和稀疏近似逆方法。他利用了直接求解者社区开发的技术，比如Bunch-Kaufman和Bunch-Parlett类型的旋转策略。在鞍点和移位线性系统上的初步实验令人鼓舞。他还探索了这些前置条件的多层次变体。研究了针对所谓KKT型系统的特殊方法。该项目的其他部分涉及为最小二乘问题和由马尔科夫链计算产生的奇异线性系统构造健壮的预条件。由于最近在数据挖掘中的应用，后一个问题目前特别令人感兴趣。具体地说，目前正在解决的最大的矩阵问题是所谓的“谷歌问题”，这相当于计算具有27亿个状态的马尔可夫链的平稳分布向量。解决方案技术的改进有可能极大地影响这一重要领域。许多重要科学和技术领域的进步依赖于计算机模拟中使用的数学算法的进步。数据挖掘这一新兴领域提供了一个最近的例子。著名的搜索引擎“GOOGLE”(见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.