Convergence conditions for a restarted GMRES method augmented with eigenspaces

We consider the GMRES(m,k) method for the solution of linear systems Ax=b, i.e. the restarted GMRES with restart m where to the standard Krylov subspace of dimension m the other subspace of dimension k is added, resulting in an augmented Krylov subspace. This additional subspace approximates usually an A‐invariant subspace. The eigenspaces associated with the eigenvalues closest to zero are commonly used, as those are thought to hinder convergence the most. The behaviour of residual bounds is described for various situations which can arise during the GMRES(m,k) process. The obtained estimates for the norm of the residual vector suggest sufficient conditions for convergence of GMRES(m,k) and illustrate that these augmentation techniques can remove stagnation of GMRES(m) in many cases. All estimates are independent of the choice of an initial approximation. Conclusions and remarks assessing numerically the quality of proposed bounds conclude the paper. Copyright © 2004 John Wiley & Sons, Ltd.     

On IGMRES: An incomplete generalized minimal residual method for large unsymmetric linear systems

The truncated version of the generalized minimal residual method (GMRES), the incomplete generalized minimal residual method (IGMRES), is studied. It is based on an incomplete orthogonalization of the Krylov vectors in question, and gives an approximate or quasi-minimum residual solution over the Krylov subspace. A convergence analysis of this method is given, showing that in the non-restarted version IGMRES can behave like GMRES once the basis vectors of Krylov subspace generated by the incomplete orthogonalization are strongly linearly independent. Meanwhile, some relationships between the residual norms for IOM and IGMRES are established. Numerical experiments are reported to show convergence behavior of IGMRES and of its restarted version IGMRES(m). Project supported by the China State Key Basic Researches, the National Natural Science Foundation of China (Grant No. 19571014), the Doctoral Program (97014113), the Foundation of Returning Scholars of China and the Natural Science Foundation of Liaoning Province.     

Improving GMRES(m) using an adaptive switching controller

The restarted generalized minimal residual (denoted as GMRES(m)) normally used for solving a linear system of equations of the form Ax=b has the drawback of eventually presenting a stagnation or a slowdown in its rate of convergence at certain restarting cycles. In this article, a switching controller is introduced to modify the structure of the GMRES(m) when a stagnation is detected, enlarging and enriching the subspace. In addition, an adaptive control law is introduced to update the restarting parameter to modify the dimension of the Krylov subspace. This combination of strategies is competitive from the point of view of helping to avoid the stagnation and accelerating the convergence with respect to the number of iterations and the computational time. Computational experiments corroborate the theoretical results.     

On preconditioned MHSS iteration methods for complex symmetric linear systems

We propose a preconditioned variant of the modified HSS (MHSS) iteration method for solving a class of complex symmetric systems of linear equations. Under suitable conditions, we prove the convergence of the preconditioned MHSS (PMHSS) iteration method and discuss the spectral properties of the PMHSS-preconditioned matrix. Numerical implementations show that the resulting PMHSS preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as GMRES and its restarted variants. In particular, both the stationary PMHSS iteration and PMHSS-preconditioned GMRES show meshsize-independent and parameter-insensitive convergence behavior for the tested numerical examples.     

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

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

Preconditioning iterative algorithm for the electromagnetic scattering from a large cavity

A preconditioning iterative algorithm is proposed for solving electromagnetic scattering from an open cavity embedded in an infinite ground plane. In this iterative algorithm, a physical model with a vertically layered medium is employed as a preconditioner of the model of general media. A fast algorithm developed in (SIAM J. Sci. Comput. 2005; 27 :553–574) is applied for solving the model of layered media and classical Krylov subspace methods, restarted GMRES, COCG, and BiCGstab are employed for solving the preconditioned system. Our numerical experiments on cavity models with large numbers of mesh points and large wave numbers show that the algorithm is efficient and the number of iterations is independent of the number of mesh points and dependent upon the wave number. Copyright © 2008 John Wiley & Sons, Ltd.     

A geometric view of Krylov subspace methods on singular systems

We give a geometric framework for analysing iterative methods on singular linear systems A x = b and apply them to Krylov subspace methods. The idea is to decompose the method into the ?(A) component and its orthogonal complement ?(A)^?, where ?(A) is the range of A. We apply the framework to GMRES, GMRES(k) and GCR(k), and derive conditions for convergence without breakdown for inconsistent and consistent singular systems. The approach also gives a geometric interpretation and different proofs of the conditions obtained by Brown and Walker for GMRES. We also give examples arising in the finite difference discretization of two‐point boundary value problems of an ordinary differential equation. Copyright © 2010 John Wiley & Sons, Ltd.     

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 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.     

Preconditioned Krylov subspace method for the solution of least-squares problems

We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least-squares problems min ∥Ax – b ∥₂, with A ∈ R ^m×n, based on the Krylov subspaces K_k (BA, Br) and K_k (AB, r), respectively, where B ∈ R ^n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least-squares problems, the preconditioned GMRES methods are the best for large, sparse and ill-conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly-proposed GMRES-type methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Krylov subspace methods with deflation and balancing preconditioners for least squares problems

For solving least squares problems, the CGLS method is a typical method in the point of view of iterative methods. When the least squares problems are ill-conditioned, the convergence behavior of the CGLS method will present a deteriorated result. We expect to select other iterative Krylov subspace methods to overcome the disadvantage of CGLS. Here the GMRES method is a suitable algorithm for the reason that it is derived from the minimal residual norm approach, which coincides with least squares problems. Ken Hayami proposed BAGMRES for solving least squares problems in [\emph{GMRES Methods for Least Squares Problems, SIAM J. Matrix Anal. Appl., 31(2010)}, pp.2400-2430]. The deflation and balancing preconditioners can optimize the convergence rate through modulating spectral distribution. Hence, in this paper we utilize preconditioned iterative Krylov subspace methods with deflation and balancing preconditioners in order to solve ill-conditioned least squares problems. Numerical experiments show that the methods proposed in this paper are better than the CGLS method.     

CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm

The Generalized Minimal Residual (GMRES) method and the Quasi-Minimal Residual (QMR) method are two Krylov methods for solving linear systems. The main difference between these methods is the generation of the basis vectors for the Krylov subspace. The GMRES method uses the Arnoldi process while QMR uses the Lanczos algorithm for constructing a basis of the Krylov subspace. In this paper we give a new method similar to QMR but based on the Hessenberg process instead of the Lanczos process. We call the new method the CMRH method. The CMRH method is less expensive and requires slightly less storage than GMRES. Numerical experiments suggest that it has behaviour similar to GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

Hybrid enriched bidiagonalization for discrete ill‐posed problems

The regularizing properties of the Golub–Kahan bidiagonalization algorithm are powerful when the associated Krylov subspace captures the dominating components of the solution. In some applications the regularized solution can be further improved by enrichment, that is, by augmenting the Krylov subspace with a low‐dimensional subspace that represents specific prior information. Inspired by earlier work on GMRES, we demonstrate how to carry these ideas over to the bidiagonalization algorithm, and we describe how to incorporate Tikhonov regularization. This leads to a hybrid iterative method where the choice of regularization parameter in each iteration also provides a stopping rule.     

New conditions for non-stagnation of minimal residual methods

In the solution of large linear systems, a condition guaranteeing that a minimal residual Krylov subspace method makes some progress, i.e., that it does not stagnate, is that the symmetric part of the coefficient matrix be positive definite. This condition results in a well-established worst-case bound for the convergence rate of the iterative method, due to Elman. This bound has been extensively used, e.g., when the linear system comes from discretized partial differential equations, to show that the convergence of GMRES is independent of the underlying mesh size. In this paper we introduce more general non-stagnation conditions, which do not require the symmetric part of the coefficient matrix to be positive definite, and that guarantee, for example, the non-stagnation of restarted GMRES for certain values of the restarting parameter. Work on this paper was supported in part by the U.S. Department of Energy under grant DE-FG02-05ER25672.     

A new adaptive GMRES algorithm for achieving high accuracy

GMRES(k) is widely used for solving non-symmetric linear systems. However, it is inadequate either when it converges only for k close to the problem size or when numerical error in the modified Gram–Schmidt process used in the GMRES orthogonalization phase dramatically affects the algorithm performance. An adaptive version of GMRES(k) which tunes the restart value k based on criteria estimating the GMRES convergence rate for the given problem is proposed here. This adaptive GMRES(k) procedure outperforms standard GMRES(k), several other GMRES-like methods, and QMR on actual large scale sparse structural mechanics postbuckling and analog circuit simulation problems. There are some applications, such as homotopy methods for high Reynolds number viscous flows, solid mechanics postbuckling analysis, and analog circuit simulation, where very high accuracy in the linear system solutions is essential. In this context, the modified Gram–Schmidt process in GMRES, can fail causing the entire GMRES iteration to fail. It is shown that the adaptive GMRES(k) with the orthogonalization performed by Householder transformations succeeds whenever GMRES(k) with the orthogonalization performed by the modified Gram–Schmidt process fails, and the extra cost of computing Householder transformations is justified for these applications. © 1998 John Wiley & Sons, Ltd.     

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.     

TOTAL GENERALIZED MINIMUM BACKWARD ERROR ALGORITHM FOR SOLVING NONSYMMETRIC LINEAR SYSTEMS

1.IntroductionAnimportantaspectofanyiterativemethodforapproximatingthesolutionofalinearsystemAx~b,(1.1)whereAisannxnrealnonsymmetricmatrixandbisann-vector,istodecideatwhatpointtostoptheiteration.Wecustomarilyusetheresidualerrorasastoppingcondition.Theresidualerrorre=b--AxmcanbeviewedasaperturbationtothevectorbsuchthattheapproximatesolutionisanexactsolutionoftheperturbedlinearsystemAx=b 5,inwhichchangesarepermittedtothevectorbonly.TheGMRESalgorithmisbasedonclassicalKrylovsubspacetechniquesa…     

A Non-Krylov Subspace Method for Solving Large and Sparse Linear System of Equations

Most current prevalent iterative methods can be classified into the socalled extended Krylov subspace methods, a class of iterative methods which do not fall into this category are also proposed in this paper. Comparing with traditional Krylov subspace methods which always depend on the matrix-vector multiplication with a fixed matrix, the newly introduced methods (the so-called (progressively) accumulated projection methods, or AP (PAP) for short) use a projection matrix which varies in every iteration to form a subspace from which an approximate solution is sought. More importantly, an accelerative approach (called APAP) is introduced to improve the convergence of PAP method. Numerical experiments demonstrate some surprisingly improved convergence behaviors. Comparisons between benchmark extended Krylov subspace methods (Block Jacobi and GMRES) are made and one can also see remarkable advantage of APAP in some examples. APAP is also used to solve systems with extremely ill-conditioned coefficient matrix (the Hilbert matrix) and numerical experiments shows that it can bring very satisfactory results even when the size of system is up to a few thousands.     

Restarted FOM Augmented with Ritz Vectors for Shifted Linear Systems

The restarted FOM method presented by Simoncini[7]according to the natural collinearity of all residuals is an efficient method for solving shifted systems,which generates the same Krylov subspace when the shifts are handled simultaneously.However,restarting slows down the convergence.We present a practical method for solving the shifted systems by adding some Ritz vectors into the Krylov subspace to form an augmented Krylov subspace. Numerical experiments illustrate that the augmented FOM approach(restarted version)can converge more quickly than the restarted FOM method.     

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.