A block GMRES method with deflated restarting for solving linear systems with multiple shifts and multiple right‐hand sides

The restarted block generalized minimum residual method (BGMRES) with deflated restarting (BGMRES‐DR) was proposed by Morgan to dump the negative effect of small eigenvalues from the convergence of the BGMRES method. More recently, Wu et al. introduced the shifted BGMRES method (BGMRES‐Sh) for solving the sequence of linear systems with multiple shifts and multiple right‐hand sides. In this paper, a new shifted block Krylov subspace algorithm that combines the characteristics of both the BGMRES‐DR and the BGMRES‐Sh methods is proposed. Moreover, our method is enhanced with a seed selection strategy to handle the case of almost linear dependence of the right‐hand sides. Numerical experiments illustrate the potential of the proposed method to solve efficiently the sequence of linear systems with multiple shifts and multiple right‐hand sides, with and without preconditioner, also against other state‐of‐the‐art solvers.     

A simpler GMRES

The generalized minimal residual (GMRES) method is widely used for solving very large, nonsymmetric linear systems, particularly those that arise through discretization of continuous mathematical models in science and engineering. By shifting the Arnoldi process to begin with Ar₀ instead of r₀, we obtain simpler Gram–Schmidt and Householder implementations of the GMRES method that do not require upper Hessenberg factorization. The Gram–Schmidt implementation also maintains the residual vector at each iteration, which allows cheaper restarts of GMRES(m) and may otherwise be useful.     

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 new implementation of the CMRH method for solving dense linear systems

The CMRH method [H. Sadok, Méthodes de projections pour les systèmes linéaires et non linéaires, Habilitation thesis, University of Lille1, Lille, France, 1994; H. Sadok, CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm, Numer. Algorithms 20 (1999) 303–321] is an algorithm for solving nonsymmetric linear systems in which the Arnoldi component of GMRES is replaced by the Hessenberg process, which generates Krylov basis vectors which are orthogonal to standard unit basis vectors rather than mutually orthogonal. The iterate is formed from these vectors by solving a small least squares problem involving a Hessenberg matrix. Like GMRES, this method requires one matrix–vector product per iteration. However, it can be implemented to require half as much arithmetic work and less storage. Moreover, numerical experiments show that this method performs accurately and reduces the residual about as fast as GMRES. With this new implementation, we show that the CMRH method is the only method with long-term recurrence which requires not storing at the same time the entire Krylov vectors basis and the original matrix as in the GMRES algorithm. A comparison with Gaussian elimination is provided.     

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.     

添加近似误差的重新启动的simpler GMRES方法

本文给出了重新启动的LGMRES方法的一种代价更小的实现方式.这种做法基于消除以下减慢收敛速度的现象:重新启动的simpler GMRES的每次循环结束时得到的残向量经常交替方向,与重新启动的GMRES的情形类似.这种新的变形的方法的优点是它比重新启动的LGMRES所需要的计算量要少.大量的例子表明该方法计算速度更快.     

A note on ℝ‐linear GMRES for solving a class of ℝ‐linear systems

We prove that ?‐linear GMRES for solving a class of ?‐linear systems is faster than GMRES applied to the related ?‐linear systems in terms of matrix–vector products. Numerical examples are given to demonstrate the theoretical result. Copyright © 2011 John Wiley & Sons, Ltd.     

Analysis of the convergence of the minimal and the orthogonal residual methods

We consider two Krylov subspace methods for solving linear systems, which are the minimal residual method and the orthogonal residual method. These two methods are studied without referring to any particular implementations. By using the Petrov–Galerkin condition, we describe the residual norms of these two methods in terms of Krylov vectors, and the relationship between there two norms. We define the Ritz singular values, and prove that the convergence of these two methods is governed by the convergence of the Ritz singular values. AMS subject classification 65F10     

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.     

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步     

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.     

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.     

A novel approach to solve linear systems arising from BEM using fast wavelet transforms

This paper uses Daubechies orthogonal wavelets to change dense and fully populated matrices of boundary element method (BEM) systems into sparse and semi‐banded matrices. Then a novel algorithm based on hierarchical nature of multiresolution analysis is introduced to solving resultant sparse linear systems. This algorithm decomposes NS‐form of transformed parent matrix into descendant systems with reduced sizes and solves them iteratively using GMRES algorithm. Both parts, changing dense matrices to sparse systems and the novel solver, can be added as a black box to the existing BEM codes. Transforming matrices into wavelet space needs less time than saved by solving sparse large systems. Numerical results with a precise study on sensitivity of solution for physical variables to the thresholding parameter, and savings in computer time and memory are presented. Also, the suitable value for thresholding parameter is recommended for elasticity problems. The results indicate that the proposed method is efficient for large problems. Copyright © 2009 John Wiley & Sons, Ltd.     

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.     

求解离散不适定问题的正则化GMERR方法

迭代极小残差方法是求解大型线性方程组的常用方法, 通常用残差范数控制迭代过程.但对于不适定问题, 即使残差范数下降, 误差范数未必下降. 对大型离散不适定问题,组合广义最小误差(GMERR)方法和截断奇异值分解(TSVD)正则化方法, 并利用广义交叉校验准则(GCV)确定正则化参数,提出了求解大型不适定问题的正则化GMERR方法.数值结果表明, 正则化GMERR方法优于正则化GMRES方法.     

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.     

有界多连通区域数值保角变换的GMRES(m)法北大核心CSCD

求解复杂多连通区域的保角变换函数是困难的.针对这一问题,该文将求解保角变换函数转化为利用模拟电荷法求解一对定义在问题区域上的共轭调和函数,再根据边界条件建立约束方程,并利用GMRES(m)(the generalized minimal residual method)算法求解约束方程,获得了模拟电荷,进而构造了高精度的近似保角变换函数,将有界多连通区域映射为三种无界正则狭缝域.数值实验验证了该文算法的有效性.     

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.     

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.     

A simple strategy for varying the restart parameter in GMRES()

When solving a system of linear equations with the restarted GMRES method, a fixed restart parameter is typically chosen. We present numerical experiments that demonstrate the beneficial effects of changing the value of the restart parameter in each restart cycle on the total time to solution. We propose a simple strategy for varying the restart parameter and provide some heuristic explanations for its effectiveness based on analysis of the symmetric case.