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.     

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.     

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.     

The preconditioned GMRES method for systems of coupled FEM-BEM equations

We analyze the generalized minimal residual method (GMRES) as a solver for coupled finite element and boundary element equations. To accelerate the convergence of GMRES we apply a hierarchical basis block preconditioner for piecewise linear finite elements and piecewise constant boundary elements. It is shown that the number of iterations which is necessary to reach a given accuracy grows only poly-logarithmically with the number of unknowns. This revised version was published online in June 2006 with corrections to the Cover Date.     

Inexact Perturbed Newton Methods and Applications to a Class of Krylov Solvers

Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system (Ref. 1). The local convergence theory given by the authors of Ref. 1 and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals. We extend this local convergence theory to the general case, characterizing the rate of convergence in terms of the perturbations and residuals.The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton–Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton–Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method. At the end of the paper, the theoretical results are verified on some numerical examples.     

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.     

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.     

A preconditioned GMRES for complex dense linear systems from electromagnetic wave scattering problems

We consider the numerical solution of linear systems arising from the discretization of the electric field integral equation (EFIE). For some geometries the associated matrix can be poorly conditioned making the use of a preconditioner mandatory to obtain convergence. The electromagnetic scattering problem is here solved by means of a preconditioned GMRES in the context of the multilevel fast multipole method (MLFMM). The novelty of this work is the construction of an approximate hierarchically semiseparable (HSS) representation of the near-field matrix, the part of the matrix capturing interactions among nearby groups in the MLFMM, as preconditioner for the GMRES iterations. As experience shows, the efficiency of an ILU preconditioning for such systems essentially depends on a sufficient fill-in, which apparently sacrifices the sparsity of the near-field matrix. In the light of this experience we propose a multilevel near-field matrix and its corresponding HSS representation as a hierarchical preconditioner in order to substantially reduce the number of iterations in the solution of the resulting system of equations.     

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.     

Weighted FOM and GMRES for solving nonsymmetric linear systems

This paper presents two new methods called WFOM and WGMRES, which are variants of FOM and GMRES, for solving large and sparse nonsymmetric linear systems. To accelerate the convergence, these new methods use a different inner product instead of the Euclidean one. Furthermore, at each restart, a different inner product is chosen. The weighted Arnoldi process is introduced for implementing these methods. After describing the weighted methods, we give the relations that link them to FOM and GMRES. Experimental results are presented to show the good performances of the new methods compared to FOM(m) and GMRES(m). This revised version was published online in August 2006 with corrections to the Cover Date.     

Generalizations and modifications of the GMRES iterative method

For solving nonsymmetric linear systems, the well-known GMRES method is considered to be a stable method; however, the work per iteration increases as the number of iterations increases. We consider two new iterative methods GGMRES and MGMRES, which are a generalization and a modification of the GMRES method, respectively. Instead of using a minimization condition as in the derivation of GGMRES, we use a Galerkin condition to derive the MGMRES method. We also introduce another new iterative method, LAN/MGMRES, which is designed to combine the reliability of GMRES with the reduced work of a Lanczos-type method. A computer program has been written based on the use of the LAN/MGMRES algorithm for solving nonsymmetric linear systems arising from certain elliptic problems. Numerical tests are presented comparing this algorithm with some other commonly used iterative algorithms. These preliminary tests of the LAN/MGMRES algorithm show that it is comparable in terms of both the approximate number of iterations and the overall convergence behavior. This revised version was published online in June 2006 with corrections to the Cover Date.     

GMRES and the Arioli,Pták,and Strakoš parametrization

In this paper we study the parametrization proposed by Arioli, Pták and Strakoš (BIT Numerical Mathematics, v 38, 1998) for the class of matrices having the same GMRES residual norm convergence curve. We give expressions for the Hessenberg matrix and the orthonormal basis vectors constructed by GMRES as well as for iterates and error vectors. The iterates do not depend on the eigenvalues in the sense that changing the coefficients of the characteristic polynomial in the parametrization does not change the GMRES iterates as well as the residuals. However, the error vectors do depend on these coefficients.     

Inner solvers for interior point methods for large scale nonlinear programming

This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative solvers, with an adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution. In this work, we analyse the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior point schemes. We discuss the convergence of the whole approach, the implementation details and report the results of numerical experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison with other interior point codes is also reported. This research was supported by the Italian Ministry for Education, University and Research (MIUR) projects: FIRB Project: “Parallel Nonlinear Numerical Optimization PN ² O” (grant n. RBAU01JYPN, ) and COFIN/PRIN04 Project “Numerical Methods and Mathematical Software for Applications” (grant n. 2004012559, ).     

Strang-type preconditioners for systems of LMF-based ODE codes

We consider the solution of ordinary differential equations(ODEs) using boundary value methods. These methods require thesolution of one or more unsymmetric, large and sparse linearsystems. The GMRES method with the Strang-type block-circulantpreconditioner is proposed for solving these linear systems.We show that if an A_k1,k2 -stable boundary value method is usedfor an m-by-m system of ODEs, then our preconditioners are invertibleand all the eigenvalues of the preconditioned systems are 1except for at most 2m(k₁ + k₂) outliers. It follows that whenthe GMRES method is applied to solving the preconditioned systems,the method will converge in at most 2m(k₁ + k₂) + 1 iterations.Numerical results are given to illustrate the effectivenessof our methods. Received 8 October 1999. Accepted 30 May 2000.     

二维Helmholtz方程的联合紧致差分离散方程组的预处理方法

对于二维的Helmholtz方程,本文用联合紧致差分格式(CCD)离散,该差分格式具有六阶精度,三点差分和隐式的特点.本文基于CCD格式离散得到的线性系统和循环矩阵的快速傅里叶变换,提出了一种循环型预处理算子用于广义极小残量迭代算法(GMRES).给出了循环型预处理子的求解算法,证明了该预处理算子能使迭代算法具有较快的收敛速度.本文还与其他算法的预处理算子作比较,数值结果表明本文提出的循环型预处理算子具有更好的稳定性,并且对于较大的波数k,收敛速度也更快.     

An adaptive finite volume method for the diffraction grating problem with the truncated DtN boundary condition

We consider GMRES applied to discretisations of the high-frequency Helmholtz equation with strong trapping; recall that in this situation the problem is exponentially ill-conditioned through an increasing sequence of frequencies. Our main focus is on boundary-integral-equation formulations of the exterior Dirichlet and Neumann obstacle problems in 2- and 3-d. Under certain assumptions about the distribution of the eigenvalues of the integral operators, we prove upper bounds on how the number of GMRES iterations grows with the frequency; we then investigate numerically the sharpness (in terms of dependence on frequency) of both our bounds and various quantities entering our bounds. This paper is therefore the first comprehensive study of the frequency-dependence of the number of GMRES iterations for Helmholtz boundary-integral equations under trapping.

     

Inexact Inverse Iteration for Generalized Eigenvalue Problems

In this paper, we study an inexact inverse iteration with inner-outer iterations for solving the generalized eigenvalu problem Ax = Bx, and analyze how the accuracy in the inner iterations affects the convergence of the outer iterations. By considering a special stopping criterion depending on a threshold parameter, we show that the outer iteration converges linearly with the inner threshold parameter as the convergence rate. We also discuss the total amount of work and asymptotic equivalence between this stopping criterion and a more standard one. Numerical examples are given to illustrate the theoretical results.     

A Levenberg–Marquardt method based on Sobolev gradients

We extend the theory of Sobolev gradients to include variable metric methods, such as Newton’s method and the Levenberg–Marquardt method, as gradient descent iterations associated with stepwise variable inner products. In particular, we obtain existence, uniqueness, and asymptotic convergence results for a gradient flow based on a variable inner product.     

GMRES, L-Curves, and Discrete Ill-Posed Problems

The GMRES method is a popular iterative method for the solution of large linear systems of equations with a nonsymmetric nonsingular matrix. This paper discusses application of the GMRES method to the solution of large linear systems of equations that arise from the discretization of linear ill-posed problems. These linear systems are severely ill-conditioned and are referred to as discrete ill-posed problems. We are concerned with the situation when the right-hand side vector is contaminated by measurement errors, and we discuss how a meaningful approximate solution of the discrete ill-posed problem can be determined by early termination of the iterations with the GMRES method. We propose a termination criterion based on the condition number of the projected matrices defined by the GMRES method. Under certain conditions on the linear system, the termination index corresponds to the vertex of an L-shaped curve.     

Superlinear Convergence of the GMRES for PDE-Constrained Optimization Problems

Optimal control problems for PDEs arise in many important applications. A main step in the solution process is the solution of the arising linear system, where the crucial point is usually finding a proper preconditioner. We propose both proper block diagonal and more involved preconditioners, and derive mesh independent superlinear convergence of the preconditioned GMRES iterations based on a compact perturbation property of the underlying operators.