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

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

M/M/c休假排队系统稳态分布的数值计算

从数值计算角度研究M/M/c休假排队系统稳定状态的概率分布.采用GMRES方法求解概率分布向量所满足的大型线性方程,构造了一个循环预处理算子加速GMRES方法的收敛.数值实例验证了该算法的优越性.     

一种自适应预处理的BiCRSTAB算法

提出一种自适应预处理的BiCRSTAB方法,该预处理可以看作一个隐式构造多项式的预处理方法,由BiCRSTAB算法中嵌入几步GMRES迭代自适应构造而成.数值算例表明,该方法能有效减少迭代步数,从而减少计算过程中的贮存量和运算量.     

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

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

An Efficient Variant of the Restarted Shifted GMRES Method for Solving Shifted Linear Systems

We investigate the restart of the Restarted Shifted GMRES method for solving shifted linear systems.Recently the variant of the GMRES(m) method with the unfixed update has been proposed to improve the convergence of the GMRES(m) method for solving linear systems,and shown to have an efficient convergence property.In this paper,by applying the unfixed update to the Restarted Shifted GMRES method,we propose a variant of the Restarted Shifted GMRES method.We show a potentiality for efficient convergence within the variant by some numerical results.     

计算最小奇异组的一个精化调和 Lanczos双对角化方法

在很多实际应用中需要计算大规模矩阵的若干个最小奇异组.调和投影方法是计算内部特征对的常用方法,其原理可用于求解大规模奇异值分解问题.本文证明了,当投影空间足够好时,该方法得到的近似奇异值收敛,但近似奇异向量可能收敛很慢甚至不收敛.根据第二作者近年来提出的精化投影方法的原理,本文提出一种精化的调和Lanczos双对角化方法,证明了它的收敛性.然后将该方法与Sorensen提出的隐式重新启动技术相结合,开发出隐式重新启动的调和Lanczos双对角化算法(IRHLB)和隐式重新启动的精化调和Lanczos双对角化算法(IRRHLB).位移的合理选取是算法成功的关键之一,本文对精化算法提出了一种新的位移策略,称之为"精化调和位移".理论分析表明,精化调和位移比IRHLB中所用的调和位移要好,且可以廉价可靠地计算出来.数值实验表明,IRRHLB比IRHLB要显著优越,而且比目前常用的隐式重新启动的Lanczos双对角化方法(IRLB)和精化算法IRRLB更有效.     

Krylov子空间投影法及其在油藏数值模拟中的应用

Krylov子空间投影法是一类非常有效的大型线性代数方程组解法,随着左右空间L_m、K_m的不同选取可以得到许多人们熟知的方法.按矩阵H_m的不同类型,将Krylov子空间方法分成两大类,简要分析了这两类方法的优缺点及其最新进展.将目前最为可靠实用的广义最小余量法(GMRES)应用于油藏数值模拟计算问题,利用矩阵分块技术,采用块拟消去法(PE)对系数阵进行预处理.计算结果表明本文的预处理GMRES方法优于目前使用较多的预处理正交极小化ORTHMIN方法,最后还讨论了投影类方法的局限和今后的可能发展方向.     

简化块GMRES的稳定算法

块GMRES算法是求解多右端项线性方程组的经典算法.基于迭代过程中的迭代残量,提出一种基于残量的简化块GMRES算法,有效避免经典算法中块上Hessenberg阵的QR约化过程,比文献(Liu H,Zhong B.Simpler block GMRES for nonsymmetric systems with multiple right-hand sides.Electronic Transactions on Numerical Analysis,2008,30:1-9)提出的简化算法有更好的收敛精度和稳定性.     

不定最小二乘问题的改进的不完全双曲Gram-Schmidt预处理算法

应用改进的不完全双曲Gram-Schmidt(IHMGS)方法预处理不定最小二乘问题的共轭梯度法(CGILS)、正交分解法(ILSQR)与广义的最小剩余法(GMRES)等迭代算法来求解大型稀疏的不定最小二乘问题.数值实验表明,IHMGS预处理方法可有效提高相应算法的迭代速度,且当矩阵的条件数比较大时,效果更加显著.     

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

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

Heavy Ball Flexible GMRES Method for Nonsymmetric Linear Systems

Flexible GMRES (FGMRES) is a variant of preconditioned GMRES, which changes preconditioners at every Arnoldi step. GMRES often has to be restarted in order to save storage and reduce orthogonalization cost in the Arnoldi process. Like restarted GMRES, FGMRES may also have to be restarted for the same reason. A major disadvantage of restarting is the loss of convergence speed. In this paper, we present a heavy ball flexible GMRES method, aiming to recoup some of the loss in convergence speed in the restarted flexible GMRES while keep the benefit of limiting memory usage and controlling orthogonalization cost. Numerical tests often demonstrate superior performance of the proposed heavy ball FGMRES to the restarted FGMRES.     

GMRES with adaptively deflated restarting and its performance on an electromagnetic cavity problem

GMRES with deflated restarting, denoted by GMRES-DR(m,k), is a variant of restarted GMRES for solving nonsymmetric linear systems, which improves the convergence of restarted GMRES by weakening the influence of the eigenvalues incurring poor numerical performance. However, it is difficult to determine the deflation parameter k. In this paper, we present a new deflation strategy which determines k dynamically in different cycles. Numerical results for an electromagnetic cavity problem show that the deflation strategy is efficient.     

Restarted GMRES preconditioned by deflation

This paper presents a new preconditioning technique for the restarted GMRES algorithm. It is based on an invariant subspace approximation which is updated at each cycle. Numerical examples show that this deflation technique gives a more robust scheme than the restarted algorithm, at a low cost of operations and memory.     

Some results about GMRES in the singular case

In this paper, we study the Generalized Minimal Residual (GMRES) method for solving singular linear systems, particularly when the necessary and sufficient condition to obtain a Krylov solution is not satisfied. Thanks to some new results which may be applied in exact arithmetic or in finite precision, we analyze the convergence of GMRES and restarted GMRES. These formulas can also be used in the case when the systems are nonsingular. In particular, it allows us to understand what is often referred to as stagnation of the residual norm of GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

一种灵活的混合GMRES算法

1　引　　言考虑线性方程组Ax =b (1 .1 )其中 A∈RN× N是非奇异的 .求解方程组 (1 .1 )的很多迭代方法都可归类于多项式法 ,即满足x(n) =x(0 ) +qn- 1 (A) r(0 ) ,degqn- 1 ≤ n -1这里 x(n) ,n≥ 0为第 n步迭代解 ,r(n) =b-Ax(n) 是对应的迭代残量 .等价地 ,r(n) =pn(A) r(0 ) ,degpn≤ n;pn(0 ) =1 (1 .2 )其中 pn(z) =1 -zqn- 1 (z)称为残量多项式 .或有r(n) -r(0 ) ∈ AKn(r(0 ) ,A)其中 Kn(v,A)≡span{ Aiv} n- 1 i=0 是对应于 v,A的 Krylov子空间 .对于非对称问题 ,可以用正交性条件r(n)⊥ AKn(r(0 ) ,A)来确定 (1 .2 )中的…     

Partitioned-GMRES in Domain Decomposition with Approximate Subdomain Solution

Solution of large linear systems encountered in computational fluid dynamics often leads to some form of domain decomposition, especially when it is desired to use parallel machines. In this paper P-GMRES, a partitioned modification of GMRES, is applied to such problems. It is shown that P-GMRES converges faster than GMRES if the subdomains are solved exactly, and that P-GMRES requires less communication in the computation of the inner products. Also, approximate solutions for the subdomains by an inner preconditioned GMRES iteration are considered, in combination with a restarted version of P-GMRES. It turns out that rather crude tolerances are allowed, and that a good strategy is to vary the tolerance for the subdomains in the course of the outer iteration.This revised version was published online in October 2005 with corrections to the Cover Date.     

基于GMRES的多项式预处理广义极小残差法

求解大型稀疏线性方程组一般采用迭代法,其中GMRES(m)算法是一种非常有效的算法,然而该算法在解方程组时,可能发生停滞．为了克服算法GMRES(m)解线性系统Ax=b过程中可能出现的收敛缓慢或不收敛,本文利用GMRES本身构造出一种有效的多项式预处理因子pk(z),该多项式预处理因子非常简单且易于实现．数值试验表明,新算法POLYGMRES(m)较好地克服了GMRES(m)的缺陷．     

Any admissible cycle‐convergence behavior is possible for restarted GMRES at its initial cycles

We show that any admissible cycle‐convergence behavior is possible for restarted GMRES at a number of initial cycles, moreover the spectrum of the coefficient matrix alone does not determine this cycle‐convergence. The latter can be viewed as an extension of the result of Greenbaum, Pták and Strako? (SIAM Journal on Matrix Analysis and Applications 1996; 17 (3):465–469) to the case of restarted GMRES. Copyright © 2010 John Wiley & Sons, Ltd.     

CGS/GMRES(k): AN ADAPTIVE PRECONDITIONED CGS ALGORITHM FOR NONSYMMETRIC LINEAR SYSTEMS

Recently Y. Saad proposed a flexible inner-outer preconditioned GMRES algorithm for nonsymmetric linear systems [4]. Following their ideas, we suggest an adaptive preconditioned CGS method, called CGS/GMRES (k), in which the preconditioner is constructed in the iteration step of CGS, by several steps of GMRES(k). Numerical experiments show that the residual of the outer iteration decreases rapidly. We also found the interesting residual behaviour of GMRES for the skewsymmetric linear system Ax = b, which gives a convergence result for restarted GMRES (k). For convenience, we discuss real systems.     

A simpler GMRES and its adaptive variant for shifted linear systems

A variant of the simpler GMRES method is developed for solving shifted linear systems (SGMRES‐Sh), exhibiting almost the same advantage of the simpler GMRES method over the regular GMRES method. Because the remedy adapted by GMRES‐Sh is no longer feasible for SGMRES‐Sh due to the differences between simpler GMRES and GMRES for constructing the residual vectors of linear systems, we take an alternative strategy to force the residual vectors of the add system also be orthogonal to the subspaces, to which the residual vectors of the seed system are orthogonal when the seed system is solved with the simpler GMRES method. In addition, a seed selection strategy is also employed for solving the rest non‐converged linear systems. Furthermore, an adaptive version of SGMRES‐Sh is presented for the purpose of improving the stability of SGMRES‐Sh based on the technique of the adaptive choice of the Krylov subspace basis developed for the adaptive simpler GMRES. Numerical experiments demonstrate the benefits of the presented methods.