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.     

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.     

Deflated and Augmented Krylov Subspace Techniques

We present a general framework for a number of techniques based on projection methods on ‘augmented Krylov subspaces’. These methods include the deflated GMRES algorithm, an inner–outer FGMRES iteration algorithm, and the class of block Krylov methods. Augmented Krylov subspace methods often show a significant improvement in convergence rate when compared with their standard counterparts using the subspaces of the same dimension. The methods can all be implemented with a variant of the FGMRES algorithm. © 1997 by John Wiley & Sons, Ltd.     

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.     

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

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

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方法的收敛率

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步     

A kernel-free boundary integral method for elliptic boundary value problems

This paper presents a class of kernel-free boundary integral (KFBI) methods for general elliptic boundary value problems (BVPs). The boundary integral equations reformulated from the BVPs are solved iteratively with the GMRES method. During the iteration, the boundary and volume integrals involving Green’s functions are approximated by structured grid-based numerical solutions, which avoids the need to know the analytical expressions of Green’s functions. The KFBI method assumes that the larger regular domain, which embeds the original complex domain, can be easily partitioned into a hierarchy of structured grids so that fast elliptic solvers such as the fast Fourier transform (FFT) based Poisson/Helmholtz solvers or those based on geometric multigrid iterations are applicable. The structured grid-based solutions are obtained with standard finite difference method (FDM) or finite element method (FEM), where the right hand side of the resulting linear system is appropriately modified at irregular grid nodes to recover the formal accuracy of the underlying numerical scheme. Numerical results demonstrating the efficiency and accuracy of the KFBI methods are presented. It is observed that the number of GMRES iterations used by the method for solving isotropic and moderately anisotropic BVPs is independent of the sizes of the grids that are employed to approximate the boundary and volume integrals. With the standard second-order FEMs and FDMs, the KFBI method shows a second-order convergence rate in accuracy for all of the tested Dirichlet/Neumann BVPs when the anisotropy of the diffusion tensor is not too strong.     

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.     

Necessary and sufficient conditions for GMRES complete and partial stagnation

In this paper we give necessary and sufficient conditions for the complete or partial stagnation of the GMRES iterative method for solving real linear systems. Our results rely on a paper by Arioli, Pták and Strakoš (1998), characterizing the matrices having a prescribed convergence curve for the residual norms. We show that we have complete stagnation if and only if the matrix A is orthonormally similar to an upper or lower Hessenberg matrix having a particular first row or column or a particular last row or column. Partial stagnation is characterized by a particular pattern of the matrix Q in the QR factorization of the upper Hessenberg matrix generated by the Arnoldi process.