一类大规模稀疏奇异鞍点问题的高效求解算法及预处理技术研究

Large sparse non-Hermitian positive semidefinite singular saddle point problems arise in a wide variety of scientific computing and engineering applications. Designing efficient algorithms for this kind of singular problems is very important for the settlement of the practical problems. Up to now, few algorithms can be used to solve this kind of singular saddle point problems. The preconditioners used for improving the spectral properties of the coefficient matrix and accelerating the convergence rate of the iteration method are even rarer. In order to solve the singular saddle point problems efficiently, this project will study high efficient numerical algorithms and singular preconditioners by referencing the designing experience of preconditioners for nonsingular saddle point problems and analyzing the characteristics and properties of the coefficient matrix of singular saddle point problems. We believe that, through the research of this project, high efficient iteration methods and singular preconditioners will be proposed for the non-Hermitian positive semidefinite singular saddle point problems. In addition, with the help of singular preconditioners proposed above, the spectral properties of the coefficient matrices and thus the convergence rates of the Krylov subspace methods etc will be improved. Furthermore, the needs for the fast settlement of the associated practical problems will be satisfied.

大规模稀疏非埃尔米特半正定奇异鞍点系统广泛存在于科学计算与工程应用等众多领域，设计高效的求解奇异鞍点系统的数值算法对于解决这些领域中的实际问题起着至关重要的作用。但是到目前为止，真正适合这类奇异鞍点系统求解的数值迭代方法很少，而对于能够改善其系数矩阵谱性质及加速迭代方法收敛的预处理技术的研究则更为少见。为了有效解决奇异鞍点系统的数值求解问题，本项目将在借鉴非奇异鞍点系统数值求解方法设计经验的基础上，通过分析奇异鞍点系统系数矩阵的特点和性质，研究适用于奇异鞍点系统求解的高效数值迭代算法和奇异预处理技术。相信通过本项目的研究，不仅可以为非埃尔米特半正定奇异鞍点系统的求解提供高效数值算法，还能显著改善其系数矩阵的谱性质，提高Krylov子空间等迭代方法求解该类奇异鞍点系统的效率，进而为相关领域实际问题的快速有效解决提供算法保障。

科学计算与工程应用等众多领域，例如计算流体力学、PDE约束优化以及图像处理中许多问题等的解决，都需要求解大规模稀疏的奇异鞍点问题。从而设计高效的求解奇异鞍点问题的数值算法有着重要的理论和实际意义，可以有效促进相关实际问题的快速有效解决。本项目首先通过分析奇异鞍点矩阵及其Schur补的性质，提出了两类高效的迭代算法，即参数化不精确Uzawa算法和Uzawa--HSS算法，并给出了这两类方法的收敛性结果，显著提高了奇异鞍点问题的收敛效率。另外，我们基于奇异约束预处理技术，进一步提出了一类约束预处理迭代方法，也讨论了它的收敛性。奇异鞍点问题现有的算法以及我们提出的这三种方法都收敛到奇异鞍点问题的其中一个解，但这个解是不是实际问题所需要的并不清楚。为了解决这一问题，我们进一步分析现有迭代方法的原理，找到了使迭代方法收敛到具有实际应用的极小范数最小二乘解的标准，并进而构造出收敛到奇异鞍点问题极小范数最小二乘解的迭代方法，并给出了理论证明。此外，我们还就研究内容进行了扩展，针对具有不同块形式的非奇异鞍点问题，提出了一种快速迭代方法和三种高效预处理技术；提出了两类求解矩阵方程的迭代方法，并分别给出了方法的收敛结果；最后对于一类椭圆偏微分方程离散后得到的线性系统，我们引入了非均匀网格增量未知元预处理方法，估计出了预处理矩阵的条件数。综上，通过本项目的研究，我们为奇异鞍点问题及相关实际问题的解决提供了高效的算法保障和严密的理论支持，圆满完成了项目的研究工作。