大型矩阵函数计算中多位移线性系统的高效预处理迭代法研究

The rapid development of engineering applications provides many difficult and useful problems for scientific computation research, then large-scale matrix function computations (MFCs) must be one of the most important class of computational problems. To solve such problems, we use rational function approximations to transform MFCs into solving the multiple shifted linear systems (MSLSs). Since these problems are usually large and ill-conditioned, many existing numerical methods fail to handle this challenge, especially there is a strong need for studying efficient preconditioned iterative methods, which can solve the ill-conditioned MSLSs. This project will take the structure of shifted systems and information sharing as a starting point to study efficient preconditioned iterative algorithms for MSLSs arising from large-scale MFCs: (1) establish an economic nested Krylov subspace solver (KSS) and give some novel theoretical results on the convergence of the propose method. In particular, the efficient strategies are studied to choose the accuracy of solutions of inner iterations; (2) design a polynomial preconditioner based on GMRES iterations to keep the shift-invariant property and accelerate the convergence of shifted KSSs. The eigenvalue analysis of preconditioned shifted systems is also investigated; (3) develop an adaptive contour integral (ACI) method for efficient MFCs, in which the resultant generalized MSLSs are solved by the proposed preconditioning iterative methods from the results of (1)-(2) and their hybrid variant: the two-level preconditioning. Meanwhile, we discuss the theoretical analyses of the ACI method utilizing multilevel preconditioned iterative solvers.

工程技术领域的迅猛发展为科学计算研究提出了一系列重要计算问题，大型矩阵函数计算就是其中一类典型问题。为了高效计算大型矩阵函数，通过有理函数逼近原理将其转为求解一类多位移线性系统。由于该类问题通常规模大且病态，这对现有的数值方法提出了新的挑战，特别是迫切需要对能有效处理病态系统的预处理迭代算法的研究。本项目结合方程组的结构特征，从信息共享的角度出发，对大型矩阵函数计算中多位移线性系统的预处理迭代法展开研究：(1)提出一种经济型嵌套算法，完善嵌套算法框架的理论分析，给出其内迭代精度选取的有效策略；(2)充分利用GMRES算法迭代信息来构建一种高效的多项式预处理子，并给出预处理系统的谱分析；(3)给出一种基于自适应围道积分近似的矩阵函数计算方法，并将(1)-(2)中所提出的预处理技术及其“杂交”混合变种—两层预处理子—应用于矩阵函数计算中产生的广义多位移线性系统，对新算法的收敛性进行分析。

在日益发展的科学与工程技术领域中出现了一类典型的科学计算问题—大型矩阵函数计算。通过有理函数逼近方法将大规模矩阵函数计算转化为求解一系列多位移线性方程组，由于该类位移线性方程组的规模较大且常常病态，故而通常需要采用迭代法和预处理相结合的方法对其进行求解，但常规的预处理技术很难保持Krylov子空间的位移不变性，所以针对多位移线性方程组的预处理迭代法研究是一个极具挑战性的问题。本项目通过挖掘此类多位移线性方程组的结构特性来对其高效预处理迭代解法展开研究，主要包括基于Hessenberg过程构建的重启位移CMRH算法与其结合灵活预处理技术设计的经济型嵌套位移Krylov子空间算法：Hessenberg-FCMRH算法及其收敛性分析，基于GMRES算法的迭代信息构建的一类针对多位移线性方程组的“残差极小化”多项式预处理技术，以及利用以上研究基础并基于自适应围道积分近似和多位移线性方程组的多层预处理迭代解法所给出的一类新型矩阵函数计算方法。除此之外，在本项目中还研究了其他相关的矩阵计算问题，其中包括求解分数阶微分方程的快速并行数值解法、结构线性方程组的预处理迭代法等。具体地，发展了分数阶微分方程的基于矩阵对角化的时间并行算法、几类系数矩阵具有类Toeplitz或分块矩阵结构的特殊线性方程组的预处理迭代解法。这些工作不仅能丰富和发展分数阶微分方程数值解与线性方程组预处理迭代法的理论及方法，而且为未来更多实际应用问题的高性能算法研究提供了广泛的数学基础。