几乎各向同性的高维空间分数阶扩散方程的分块快速正则Hermite分裂预处理方法

一类空间分数阶扩散方程经过有限差分离散后所得到的离散线性方程组的系数矩阵是两个对角矩阵与Toeplitz型矩阵的乘积之和.在本文中,对于几乎各向同性的二维或三维空间分数阶扩散方程的离散线性方程组,采用预处理Krylov子空间迭代方法,我们利用其系数矩阵的特殊结构和具体性质构造了一类分块快速正则Hermite分裂预处理子.通过理论分析,我们证明了所对应的预处理矩阵的特征值大部分都聚集于1的附近.数值实验也表明,这类分块快速正则Hermite分裂预处理子可以明显地加快广义极小残量(GMRES)方法和稳定化的双共轭梯度(BiCGSTAB)方法等Krylov子空间迭代方法的收敛速度.     

广义鞍点问题的松弛维数分解预条件子

本文将Benzi等提出的松弛维数分解(Relaxed dimensionalfactorization, RDF)预条件子进一步推广到广义鞍点问题上,并称为GRDF(Generalized RDF)预条件子.该预条件子可看做是用维数分裂迭代法求解广义鞍点问题而导出的改进维数分裂(Modified dimensional split, MDS)预条件子的松弛形式, 它相比MDS预条件子更接近于系数矩阵, 因而结合Krylov子空间方法(如GMRES)有更快的收敛速度.文中分析了GRDF预处理矩阵特征值的一些性质,并用数值算例验证了新预条件子的有效性.     

求解大型非对称线性方程组的不完全广义最小向后扰动法

本文给出了求解大型非对称线性方程组的广义最小向后扰动法(GMBACK)的截断版本——不完全广义最小向后扰动法(IGMBACK).该方法基于Krylov向量的不完全正交化,从而在Krylov子空间上求出一个近似的或者拟最小向后扰动解.本文对新算法IGMBACK做了一些理论研究,包括算法的有限终止、解的存在性和唯一性等方面的研究;且给出了IGMBACK的执行.数值实验表明:IGMBACK通常比GMBACK和广义最小残量法(GMRES)更有效;且IGMBACK和GMBACK经常比GMRES收敛得更好.特殊地,如果系数矩阵是敏感矩阵,且方程组右侧的向量平行于系数矩阵的最小奇异值对应的左奇异向量时,重新开始的GMRES不一定收敛,而IGMBACK和GMBACK一般收敛,且比GMRES收敛得更好.     

解非对称线性方程组的不完全广义最小残量法

研究了求解大规模非对称线性方程组常用的广义最小残量法 (GMRES)的截断版本———不完全广义最小残量法 (IGMRES)的收敛性 .该方法基于Krylov向量的不完全正交化 ,从而在Krylov子空间上求出一个近似的或拟最小残量解 .理论结果和数值实验证明 ,当由不完全正交化生成的Krylov子空间的基向量强线性无关时 ,IGMRES完全可以同GMRES相比并经常更有效 .同时 ,建立了不完全正交化方法 (IOM)和IGMRES的残量范数之间的关系式 .     

预条件广义极小残余新算法

研究Krylov子空间广义极小残余算法(GMRES(m))的基本理论，给出GMRES(m)算法透代求解所满足的代数方程组．深入探讨算法的收敛性与方程组系数矩阵的密切关系，提出一种改进GMRES(m)算法收敛性的新的预条件方法，并作出相关论证．     

简化全局GMRES算法的扩张及收缩

简化的全局GMRES算法作为求解多右端项线性方程组的方法之一,与标准的全局GMRES算法相比,需要较少的计算量,但对应的重启动方法由于矩阵Krylov子空间维数的限制,收敛会较慢.基于调和Ritz矩阵,提出了简化全局GMRES的扩张及收缩算法.数值实验结果表明,新提出的扩张及收缩算法比标准的全局GMRES算法更为快速高效.     

求解PageRank问题的重启GMRES修正的多分裂迭代法

PageRank算法已经成为网络搜索引擎的核心技术。针对PageRank问题导出的线性方程组,首先将Krylov子空间方法中的重启GMRES(generalized minimal residual)方法与多分裂迭代(multi-splitting iteration,MSI)方法相结合,提出了一种重启GMRES修正的多分裂迭代法;然后,给出了该算法的详细计算流程和收敛性分析;最后,通过数值实验验证了该算法的有效性。     

非埃尔米特正定线性系统的m步预处理的斜埃尔米特和反埃尔米特分裂方法（英文）

进一步研究了非埃尔米特正定线性系统的斜埃尔米特和反埃尔米特迭代方法,并在预处理的斜埃尔米特和反埃尔米特迭代方法的基础上,引入了m步多项式预处理子,证明了预处理的斜埃尔米特和反埃尔米特迭代方法在一定条件下是收敛的,而且得到了预处理的斜埃尔米特和反埃尔米特迭代方法的收缩因子.通过数值例子说明,对于非埃尔米特正定线性系统m步的预处理有效地加速了Krylov子空间方法,例如GMRES.     

GMRES方法的收敛率

1 引 言 GMRES方法是目前求解大型稀疏非对称线性方程组 Ax=b,A∈R~(n×n);x,b∈R~n (1)最为流行的方法之一.设x~((0))是(1)解的初始估计,r~((0))=b-Ax~((0))是初始残量,K_k=span{r~((0)),Ar~((0)),…A~(k-1)r~((0))}为由r~((0))和A产生的Krylov子空间.GMRES方法的第k步     

基于GMRES(m)法的双连通区域数值保角变换的计算法

本文研究了基于模拟电荷法的双连通区域的数值保角变换问题.利用限制Krylov子空间最大维数的算法–GMRES(m)算法,求解基于模拟电荷法的双连通区域数值保角变换中的约束方程,获得了模拟电荷和变换半径,构造了近似保角变换函数.数值实验表明了本文算法的有效性.     

Structured preconditioners for nonsingular matrices of block two-by-two structures

For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of practical and efficient structured preconditioners through matrix transformation and matrix approximations. For the specific versions such as modified block Jacobi-type, modified block Gauss-Seidel-type, and modified block unsymmetric (symmetric) Gauss-Seidel-type preconditioners, we precisely describe their concrete expressions and deliberately analyze eigenvalue distributions and positive definiteness of the preconditioned matrices. Also, we show that when these structured preconditioners are employed to precondition the Krylov subspace methods such as GMRES and restarted GMRES, fast and effective iteration solvers can be obtained for the large sparse systems of linear equations with block two-by-two coefficient matrices. In particular, these structured preconditioners can lead to efficient and high-quality preconditioning matrices for some typical matrices from the real-world applications.

     

On SSOR‐like preconditioners for non‐Hermitian positive definite matrices

We construct, analyze, and implement SSOR‐like preconditioners for non‐Hermitian positive definite system of linear equations when its coefficient matrix possesses either a dominant Hermitian part or a dominant skew‐Hermitian part. We derive tight bounds for eigenvalues of the preconditioned matrices and obtain convergence rates of the corresponding SSOR‐like iteration methods as well as the corresponding preconditioned GMRES iteration methods. Numerical implementations show that Krylov subspace iteration methods such as GMRES, when accelerated by the SSOR‐like preconditioners, are efficient solvers for these classes of non‐Hermitian positive definite linear systems. Copyright © 2015 John Wiley & Sons, Ltd.     

Constraint preconditioning for nonsymmetric indefinite linear systems

This paper introduces and presents theoretical analyses of constraint preconditioning via a Schilders'‐like factorization for nonsymmetric saddle‐point problems. We extend the Schilders' factorization of a constraint preconditioner to a nonsymmetric matrix by using a different factorization. The eigenvalue and eigenvector distributions of the preconditioned matrix are determined. The choices of the parameter matrices in the extended Schilders' factorization and the implementation of the preconditioning step are discussed. An upper bound on the degree of the minimum polynomial for the preconditioned matrix and the dimension of the corresponding Krylov subspace are determined, as well as the convergence behavior of a Krylov subspace method such as GMRES. Numerical experiments are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

On approximated ILU and UGS preconditioning methods for linearized discretized steady incompressible Navier-Stokes equations

When the artificial compressibility method in conjunction with high-order upwind compact finite difference schemes is employed to discretize the steady-state incompressible Navier-Stokes equations, in each pseudo-time step we need to solve a structured system of linear equations approximately by, for example, a Krylov subspace method such as the preconditioned GMRES. In this paper, based on the special structure and concrete property of the linear system we construct a structured preconditioner for its coefficient matrix and estimate eigenvalue bounds of the correspondingly preconditioned matrix. Numerical examples are given to illustrate the effectiveness of the proposed preconditioning methods.     

A class of constraint preconditioners for nonsymmetric saddle point matrices

We consider the use of a class of constraint preconditioners for the application of the Krylov subspace iterative method to the solution of large nonsymmetric, indefinite linear systems. The eigensolution distribution of the preconditioned matrix is determined and the convergence behavior of a Krylov subspace method such as GMRES is described. The choices of the parameter matrices and the implementation of the preconditioning step are discussed. Numerical experiments are presented. This work is supported by NSFC Projects 10171021 and 10471027.     

A new relaxed HSS preconditioner for saddle point problems

We present a preconditioner for saddle point problems. The proposed preconditioner is extracted from a stationary iterative method which is convergent under a mild condition. Some properties of the preconditioner as well as the eigenvalues distribution of the preconditioned matrix are presented. The preconditioned system is solved by a Krylov subspace method like restarted GMRES. Finally, some numerical experiments on test problems arisen from finite element discretization of the Stokes problem are given to show the effectiveness of the preconditioner.     

椭圆离散方程并行预条件子局部构造算法Ⅱ：非自共轭型方程

椭圆离散方程并行预条件子局部构造算法Ⅱ：非自共轭型方程孙家昶，曹建文（中国科学院软件研究所并行软件研究开发中心）ＡＣＬＡＳＳＯＦＬＯＣＡＬＧＲＥＥＮ－ＬＩＫＥＰＡＲＡＬＬＥＬＰＲＥＣＯＮＤＩＴＩＯＮＥＲＡＬＧＯＲＩＴＨＭＦＯＲＥＬＬＩＰＴＩＣＤＩＳＣ...     

Multistep matrix splitting iteration preconditioning for singular linear systems

Multistep matrix splitting iterations serve as preconditioning for Krylov subspace methods for solving singular linear systems. The preconditioner is applied to the generalized minimal residual (GMRES) method and the flexible GMRES (FGMRES) method. We present theoretical and practical justifications for using this approach. Numerical experiments show that the multistep generalized shifted splitting (GSS) and Hermitian and skew-Hermitian splitting (HSS) iteration preconditioning are more robust and efficient compared to standard preconditioners for some test problems of large sparse singular linear systems.     

Direct and iterative solution of the generalized Dirichlet–Neumann map for elliptic PDEs on square domains

In this work we derive the structural properties of the Collocation coefficient matrix associated with the Dirichlet–Neumann map for Laplace’s equation on a square domain. The analysis is independent of the choice of basis functions and includes the case involving the same type of boundary conditions on all sides, as well as the case where different boundary conditions are used on each side of the square domain. Taking advantage of said properties, we present efficient implementations of direct factorization and iterative methods, including classical SOR-type and Krylov subspace (Bi-CGSTAB and GMRES) methods appropriately preconditioned, for both Sine and Chebyshev basis functions. Numerical experimentation, to verify our results, is also included.