大规模线性方程组的稀疏近似逆预处理方法及应用

Since the middle of 1990s, it has been well accepted that it is preconditioning rather than choice or development of a Krylov algorithm that is more important.This is why research on the construction of effective preconditioners has significantly grown over the last two decades, while advances on Krylov subspace methods have progressively faded. Currently, preconditioning appears to be a much more active and promising research field than either direct and iterative methods. There are two preconditioning approches.One is problem-specific preconditioning by using physical properties of a specific problem, discretization details and the properties of the resulting coefficient matrix. But it is not always feasible and desirable. It is usually simpler to introduce preconditioning as a black box which is expected to work independently of the specific problem and to be robust and applicable for a wide range of application problems. This is why a great interest has been in the development of purely algebraic preconditioners that are as much general purpose as possible. Algebraic preconditioners are usually robust algorithms which require the knowledge of the coefficient matrix only, independently of the underlying physical problem. There are two major classes of algebraic preconditioning approaches: Incomplete LU (ILU) factorization type preconditioning and sparse approximate inverse type preconditioning. ILU preconditioners can be very effective. However,their construction is intrinsically sequential, and parallelism is very limited. Furthermore, for many problems, especially those highly unsymmetric, indefinite and far from diagonally dominant, ILU preconditioners may not exist, or their computation and application may be very unstable, or they are not robust. These drawbacks lead to frequent failure of preconditioning. To cope with them, over the last two decades many researchers have focused on development of a second major class of algebraic preconditioners with the aim of explicitly computing sparse approximate inverses (SAI). In principle, many SAI preconditioners can be computed in parallel, and they are robust for general purpose and avoid the solving linear systems when applied in iterative solvers. They have turned out powerful for regular sparse problems. But they encounter serious difficulties when used to precondition irregular sparse problems. Meanwhile, there are many important issues unsolved or needed further investigation, such as robust criteria for dropping tolerances, adaptive determinations of effective sparsity patterns of SAI preconditioners, parallelization implementations of adaptive SAI procedures, ordering effects, etc. In this project we concentrate on these problems, propose new robust SAI preconditioning precedures and improve some existing SAI procedures. We also explore the feasibility of SAI type preconditioning for large linear ill-conditioned and ill-posed least squares problems.

学术界自上世纪90年代中期已形成共识，大规模稀疏线性方程组有效数值求解的关键是对问题进行合理的预处理，有效地构造预处理子比选择或开发Krylov子空间方法更为重要。预处理技术分为两类，一类是面向特殊问题构造特殊的预处理子，这需要对连续问题、离散化细节、系数矩阵的性质了解很多，因此不容易做到，不一定可行，而且特殊的预处理只能用于范围很窄的问题。另一类是普适性尽可能广的纯代数预处理技术，它们只利用系数矩阵本身设计预处理方法。这类方法的代表有不完全分解预处理和稀疏近似逆预处理两大类。前者高度串行，研究相对成熟，但对于非对称性强、不定等问题，其存在性、稳定性、预处理的有效性等方面存在固有缺陷。稀疏近似逆预处理能较好地克服这些缺陷，近20年一直是研究热点之一，但理论和算法相对不成熟，有很大的拓展空间。本项目针对该课题存在的多方面问题开展研究，提出新算法，及对多个已有算法进行改进，增强鲁棒性和普适性。

大规模稀疏线性方程组的有效数值求解是大规模科学计算中的核心问题之一，其关键是对问题进行预处理，高效构造有效的构造预处理子比选择或开发Krylov子空间方法更为重要。预处理技术分为两类，一类是面向特殊问题构造特殊的预处理子，这需要对连续问题、离散化细节、系数矩阵的性质有深入了解，缺点是特殊的预处理只能用于范围很窄的问题。另一类是普适性尽可能广的纯代数预处理技术，它们只利用系数矩阵本身设计预处理方法预处理技术的代表方法有不完全分解预处理和稀疏近似逆预处理两大类。前者高度串行，研究相对成熟，但对于非对称性强、不定等问题，其存在性、稳定性、预处理的有效性等方面存在固有缺陷。稀疏近似逆预处理能较好地克服这些缺陷，20年来一直是研究热点之一，但理论和算法相对不成熟。本项目针对该课题存在的多方面问题开展了研究，提出了有效的新算法，对多个已有的算法进行了改进，增强鲁棒性和普适性。我们用大量的来自于应用中的实际问题对提出和改进的算法进行了广泛的佐证。项目同时对有广泛和重要应用背景的大规模二次特征值问题、大规模M-矩阵和非负矩阵的特征值问题、大规模矩阵函数的计算问题、大规模线性离散不适定问题的理论和数值解法开展了深入系统的研究。在这些问题的研究上取得了一系列重要的理论结果，取得了本质性的突破，丰富和发展了相关问题的数学理论；根据所建立的理论结果，对上述特征值问题和矩阵函数的计算问题分别提出了数值求解方法，开发出有效的实用算法；发现求解离散不适定问题的一些最常用迭代法的基本理论有很大的欠缺，对方法的本质存在许多模糊甚至错误的认识，对一些关键问题数十年来一直没有任何结果，项目对其中一些问题进行了研究，得到了初步而重要的理论结果，澄清了学术界一些误解。在以上各个问题上均完成了研究论文，七篇论文发表在Numerische Mathematik, Journal of Computational and Applied Mathematics, Numerical Linear Algebra with Applications, Numerical Algorithms, Science China Mathematics, Taiwanese Journal of Mathematics等国际顶尖或著名、知名杂志上，Google检索他引18篇次，SCI检索他引9篇次。