The convergence of Krylov subspace methods for large unsymmetric linear systems

The convergence problem of many Krylov subspace methods,e.g., FOM, GCR, GMRES and QMR, for solving large unsymmetric (non-Hermitian) linear systems is considered in a unified way when the coefficient matrixA is defective and its spectrum lies in the open right (left) half plane. Related theoretical error bounds are established and some intrinsic relationships between the convergence speed and the spectrum ofA are exposed. It is shown that these methods are likely to converge slowly once one of the three cases occurs:A is defective, the distribution of its spectrum is not favorable, or the Jordan basis ofA is ill conditioned. In the proof, some properties on the higher order derivatives of Chebyshev polynomials in an ellipse in the complex plane are derived, one of which corrects a result that has been used extensively in the literature. Supported by the China State Major Key Project for Basic Researches, the National Natural Science Foundation of China, the Doctoral Program of the Chinese National Educational Commission, the Foundation of Returned Scholars of China and Liaoning Province Natural Science Foundation.     

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

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

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.     

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.     

Multistep matrix splitting iteration preconditioning for singular linear systems

Multistep matrix splitting iterations serve as preconditioning for Krylov subspace methods for solving singular linear systems. The preconditioner is applied to the generalized minimal residual (GMRES) method and the flexible GMRES (FGMRES) method. We present theoretical and practical justifications for using this approach. Numerical experiments show that the multistep generalized shifted splitting (GSS) and Hermitian and skew-Hermitian splitting (HSS) iteration preconditioning are more robust and efficient compared to standard preconditioners for some test problems of large sparse singular linear systems.     

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.     

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.     

几乎各向同性的高维空间分数阶扩散方程的分块快速正则Hermite分裂预处理方法

一类空间分数阶扩散方程经过有限差分离散后所得到的离散线性方程组的系数矩阵是两个对角矩阵与Toeplitz型矩阵的乘积之和.在本文中,对于几乎各向同性的二维或三维空间分数阶扩散方程的离散线性方程组,采用预处理Krylov子空间迭代方法,我们利用其系数矩阵的特殊结构和具体性质构造了一类分块快速正则Hermite分裂预处理子.通过理论分析,我们证明了所对应的预处理矩阵的特征值大部分都聚集于1的附近.数值实验也表明,这类分块快速正则Hermite分裂预处理子可以明显地加快广义极小残量(GMRES)方法和稳定化的双共轭梯度(BiCGSTAB)方法等Krylov子空间迭代方法的收敛速度.     

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.     

A block incomplete orthogonalization method for large nonsymmetric eigenproblems

The incomplete orthogonalization method (IOM) proposed by Saad for computing a few eigenpairs of large nonsymmetric matrices is generalized into a block incomplete orthogonalization method (BIOM). It is studied how the departure from symmetry A – A ^H affects the conditioning of the block basis vectors generated by BIOM, and some relationships are established between the approximate eigenpairs obtained by BIOM and Ritz pairs. It is proved that BIOM behaves much like generalized block Lanczos methods if the basis vectors of the block Krylov subspace generated by it are strongly linearly independent. However, it is shown that BIOM may generate a nearly linearly dependent basis for a general nonsymmetric matrix. Numerical experiments illustrate the convergence behavior of BIOM.This work was supported in part by the Graduiertenkolleg at the University of Bielefeld, Germany.     

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     

Deflated Krylov subspace methods for nearly singular linear systems

This paper concerns the use of Krylov subspace methods for the solution of nearly singular nonsymmetric linear systems. We show that the incomplete orthogonalization methods (IOM) in conjunction with certain deflation techniques of Stewart, Chan, and Saad can be used to solve large nonsymmetric linear systems which are nearly singular.This work was supported by the National Science Foundation, Grants DMS-8403148 and DCR-81-16779, and by the Office of Naval Research, Contract N00014-85-K-0725.     

On the Generalized Deteriorated Positive Semi-Definite and Skew-Hermitian Splitting Preconditioner

For nonsymmetric saddle point problems, Huang et al. in [Numer. Algor. 75 (2017), pp. 1161-1191] established a generalized variant of the deteriorated positive semi-definite and skew-Hermitian splitting (GVDPSS) preconditioner to expedite the convergence speed of the Krylov subspace iteration methods like the GMRES method. In this paper, some new convergence properties as well as some new numerical results are presented to validate the theoretical results.     

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.     

Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones. Project supported by the China State Major Key Projects for Basic Researches, the National Natural Science Foundation of China (Grant No. 19571014), the Doctoral Program (97014113), the Foundation of Excellent Young Scholors of Ministry of Education, the Foundation of Returned Scholars of China and the Liaoning Province Natural Science Foundation.     

IMinpert： An Incomplete Minimum Perturbation Algorithm for Large Unsymmetric Linear Systems

This paper gives the truncated version of the Minpert method:the incomplete minimum perturbation algorithm(IMinpert).It is based on an incomplete orthogonal- ization of the Krylov vectors in question,and gives a quasi-minimum backward error solution over the Krylov subspace.In order to make the practical implementation of IMinpert easy and convenient,we give another approximate version of the IMinpert method:A-IMinpert.Theoretical properties of the latter algorithm are discussed.Nu- merical experiments are reported to show the proposed method is effective in practice and is competitive with the Minpert algorithm.     

Adaptive version of Simpler GMRES

In this paper we propose a stable variant of Simpler GMRES. It is based on the adaptive choice of the Krylov subspace basis at a given iteration step using the intermediate residual norm decrease criterion. The new direction vector is chosen as in the original implementation of Simpler GMRES or it is equal to the normalized residual vector as in the GCR method. We show that such an adaptive strategy leads to a well-conditioned basis of the Krylov subspace and we support our theoretical results with illustrative numerical examples.     

A new look at CMRH and its relation to GMRES

CMRH is a Krylov subspace method which uses the Hessenberg process to produce a basis of a Krylov method, and minimizes a quasiresidual. This method produces convergence curves which are very close to those of GMRES, but using fewer operations and storage. In this paper we present new analysis which explains why CMRH has this good convergence behavior. Numerical examples illustrate the new bounds.     

预条件广义极小残余新算法

研究Krylov子空间广义极小残余算法(GMRES(m))的基本理论，给出GMRES(m)算法透代求解所满足的代数方程组．深入探讨算法的收敛性与方程组系数矩阵的密切关系，提出一种改进GMRES(m)算法收敛性的新的预条件方法，并作出相关论证．     

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.