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.     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

Objective acceleration for unconstrained optimization

Acceleration schemes can dramatically improve existing optimization procedures. In most of the work on these schemes, such as nonlinear generalized minimal residual (N‐GMRES), acceleration is based on minimizing the ?₂ norm of some target on subspaces of ${\mathbb{R}}^n$. There are many numerical examples that show how accelerating general‐purpose and domain‐specific optimizers with N‐GMRES results in large improvements. We propose a natural modification to N‐GMRES, which significantly improves the performance in a testing environment originally used to advocate N‐GMRES. Our proposed approach, which we refer to as O‐ACCEL (objective acceleration), is novel in that it minimizes an approximation to the objective function on subspaces of ${\mathbb{R}}^n$. We prove that O‐ACCEL reduces to the full orthogonalization method for linear systems when the objective is quadratic, which differentiates our proposed approach from existing acceleration methods. Comparisons with the limited‐memory Broyden–Fletcher–Goldfarb–Shanno and nonlinear conjugate gradient methods indicate the competitiveness of O‐ACCEL. As it can be combined with domain‐specific optimizers, it may also be beneficial in areas where limited‐memory Broyden–Fletcher–Goldfarb–Shanno and nonlinear conjugate gradient methods are not suitable.     

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.     

Using successive approximations for improving the convergence of GMRES method

In this paper, our attention is concentrated on the GMRES method for the solution of the system (I–T)x=b of linear algebraic equations with a nonsymmetric matrix. We perform m pre-iterations y _l+1 =T _yl +b before starting GMRES and put y _m for the initial approximation in GMRES. We derive an upper estimate for the norm of the error vector in dependence on the mth powers of eigenvalues of the matrix T Further we study under what eigenvalues lay-out this upper estimate is the best one. The estimate shows and numerical experiments verify that it is advisable to perform pre-iterations before starting GMRES as they require fewer arithmetic operations than GMRES. Towards the end of the paper we present a numerical experiment for a system obtained by the finite difference approximation of convection-diffusion equations.     

Numerical stability of GMRES

The Generalized Minimal Residual Method (GMRES) is one of the significant methods for solving linear algebraic systems with nonsymmetric matrices. It minimizes the norm of the residual on the linear variety determined by the initial residual and then-th Krylov residual subspace and is therefore optimal, with respect to the size of the residual, in the class of Krylov subspace methods. One possible way of computing the GMRES approximations is based on constructing the orthonormal basis of the Krylov subspaces (Arnoldi basis) and then solving the transformed least squares problem. This paper studies the numerical stability of such formulations of GMRES. Our approach is based on the Arnoldi recurrence for the actually, i.e., in finite precision arithmetic, computed quantities. We consider the Householder (HHA), iterated modified Gram-Schmidt (IMGSA), and iterated classical Gram-Schmidt (ICGSA) implementations. Under the obvious assumption on the numerical nonsingularity of the system matrix, the HHA implementation of GMRES is proved backward stable in the normwise sense. That is, the backward error for the approximation is proportional to machine precision . Additionally, it is shown that in most cases the norm of the residual computed from the transformed least squares problem (Arnoldi residual) gives a good estimate of the true residual norm, until the true residual norm has reached the level A x.This work was supported by NSF contract Int921824.     

Strang-Type Preconditioners for Solving Linear Systems from Delay Differential Equations

We consider the solution of delay differential equations (DDEs) by using boundary value methods (BVMs). These methods require the solution of one or more nonsymmetric, large and sparse linear systems. The GMRES method with the Strang-type block-circulant preconditioner is proposed for solving these linear systems. We show that if a P _{k 1},k ₂-stable BVM is used for solving an m-by-m system of DDEs, then our preconditioner is invertible and all the eigenvalues of the preconditioned system are clustered around 1. It follows that when the GMRES method is applied to solving the preconditioned systems, the method may converge fast. Numerical results are given to illustrate the effectiveness of our methods.     

Generalization of convergence conditions for a restarted GMRES

We consider the GMRES(s), i.e. the restarted GMRES with restart s for the solution of linear systems Ax = b with complex coefficient matrices. It is well known that the GMRES(s) applied on a real system is convergent if the symmetric part of the matrix A is positive definite. This paper introduces sufficient conditions implying the convergence of a restarted GMRES for a more general class of non‐Hermitian matrices. For real systems these conditions generalize the known result initiated as above. The discussion after the main theorem concentrates on the question of how to find an integer j such that the GMRES(s) converges for all s ≥ j. Additional properties of GMRES obtained by derivation of the main theorem are presented in the last section. Copyright © 2000 John Wiley & Sons, Ltd.     

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.     

A note on the mesh independence of convergence bounds for additive Schwarz preconditioned GMRES

Additive Schwarz preconditioners, when including a coarse grid correction, are said to be optimal for certain discretized partial differential equations, in the sense that bounds on the convergence of iterative methods are independent of the mesh size h. Cai and Zou (Numer. Linear Algebra Appl. 2002; 9 :379–397) showed with a one‐dimensional example that in the absence of a coarse grid correction the usual GMRES bound has a factor of the order of . In this paper we consider the same example and show that for that example the behavior of the method is not well represented by the above‐mentioned bound: We use an a posteriori bound for GMRES from (SIAM Rev. 2005; 47 :247–272) and show that for that example a relevant factor is bounded by a constant. Furthermore, for a sequence of meshes, the convergence curves for that one‐dimensional example, and for several two‐dimensional model problems, are very close to each other; thus, the number of preconditioned GMRES iterations needed for convergence for a prescribed tolerance remains almost constant. Copyright © 2008 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.     

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.     

DQGMRES: a Direct Quasi-minimal Residual Algorithm Based on Incomplete Orthogonalization

We describe a Krylov subspace technique, based on incomplete orthogonalization of the Krylov vectors, which can be considered as a truncated version of GMRES. Unlike GMRES(m), the restarted version of GMRES, the new method does not require restarting. Like GMRES, it does not break down. Numerical experiments show that DQGMRES(k) often performs as well as the restarted GMRES using a subspace of dimension m=2k. In addition, the algorithm is flexible to variable preconditioning, i.e., it can accommodate variations in the preconditioner at every step. In particular, this feature allows the use of any iterative solver as a right-preconditioner for DQGMRES(k). This inner-outer iterative combination often results in a robust approach for solving indefinite non-Hermitian linear systems.     

On the convergence behavior of the restarted GMRES algorithm for solving nonsymmetric linear systems

The solution of nonsymmetric systems of linear equations continues to be a difficult problem. A main algorithm for solving nonsymmetric problems is restarted GMRES. The algorithm is based on restarting full GMRES every s iterations, for some integer s>0. This paper considers the impact of the restart frequency s on the convergence and work requirements of the method. It is shown that a good choice of this parameter can lead to reduced solution time, while an improper choice may hinder or preclude convergence. An adaptive procedure is also presented for determining automatically when to restart. The results of numerical experiments are presented.     

New convergence results on the global GMRES method for diagonalizable matrices

In the present paper, we give some new convergence results of the global GMRES method for multiple linear systems. In the case where the coefficient matrix A is diagonalizable, we derive new upper bounds for the Frobenius norm of the residual. We also consider the case of normal matrices and we propose new expressions for the norm of the residual.     

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.     

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.     

The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

Steepest descent preconditioning for nonlinear GMRES optimization

Steepest descent preconditioning is considered for the recently proposed nonlinear generalized minimal residual (N‐GMRES) optimization algorithm for unconstrained nonlinear optimization. Two steepest descent preconditioning variants are proposed. The first employs a line search, whereas the second employs a predefined small step. A simple global convergence proof is provided for the N‐GMRES optimization algorithm with the first steepest descent preconditioner (with line search), under mild standard conditions on the objective function and the line search processes. Steepest descent preconditioning for N‐GMRES optimization is also motivated by relating it to standard non‐preconditioned GMRES for linear systems in the case of a standard quadratic optimization problem with symmetric positive definite operator. Numerical tests on a variety of model problems show that the N‐GMRES optimization algorithm is able to very significantly accelerate convergence of stand‐alone steepest descent optimization. Moreover, performance of steepest‐descent preconditioned N‐GMRES is shown to be competitive with standard nonlinear conjugate gradient and limited‐memory Broyden–Fletcher–Goldfarb–Shanno methods for the model problems considered. These results serve to theoretically and numerically establish steepest‐descent preconditioned N‐GMRES as a general optimization method for unconstrained nonlinear optimization, with performance that appears promising compared with established techniques. In addition, it is argued that the real potential of the N‐GMRES optimization framework lies in the fact that it can make use of problem‐dependent nonlinear preconditioners that are more powerful than steepest descent (or, equivalently, N‐GMRES can be used as a simple wrapper around any other iterative optimization process to seek acceleration of that process), and this potential is illustrated with a further application example. Copyright © 2012 John Wiley & Sons, Ltd.     

Reorthogonalized block classical Gram–Schmidt

A reorthogonalized block classical Gram–Schmidt algorithm is proposed that factors a full column rank matrix $A$ into $A=QR$ where $Q$ is left orthogonal (has orthonormal columns) and $R$ is upper triangular and nonsingular. This block Gram–Schmidt algorithm can be implemented using matrix–matrix operations making it more efficient on modern architectures than orthogonal factorization algorithms based upon matrix-vector operations and purely vector operations. Gram–Schmidt orthogonal factorizations are important in the stable implementation of Krylov space methods such as GMRES and in approaches to modifying orthogonal factorizations when columns and rows are added or deleted from a matrix. With appropriate assumptions about the diagonal blocks of $R$ , the algorithm, when implemented in floating point arithmetic with machine unit $\varepsilon _M$ , produces $Q$ and $R$ such that $\Vert I- Q ^T\!~ Q \Vert =O(\varepsilon _M)$ and $\Vert A-QR \Vert =O(\varepsilon _M\Vert A \Vert )$ . The first of these bounds has not been shown for a block Gram–Schmidt procedure before. As consequence of these results, we provide a different analysis, with a slightly different assumption, that re-establishes a bound of Giraud et al. (Num Math, 101(1):87–100, 2005) for the CGS2 algorithm.