Restarted Full Orthogonalization Method for Shifted Linear Systems

Restarted GMRES is known to be inefficient for solving shifted systems when the shifts are handled simultaneously. Variants have been proposed to enhance its performance. We show that another restarted method, restarted Full Orthogonalization Method (FOM), can effectively be employed. The total number of iterations of restarted FOM applied to all shifted systems simultaneously is the same as that obtained by applying restarted FOM to the shifted system with slowest convergence rate, while the computational cost grows only sub-linearly with the number of shifts. Numerical experiments are reported.     

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.     

Ritz and harmonic Ritz values and the convergence of FOM and GMRES

The Ritz and harmonic Ritz values are approximate eigenvalues, which can be computed cheaply within the FOM and GMRES Krylov subspace iterative methods for solving non‐symmetric linear systems. They are also the zeros of the residual polynomials of FOM and GMRES, respectively. In this paper we show that the Walker–Zhou interpretation of GMRES enables us to formulate the relation between the harmonic Ritz values and GMRES in the same way as the relation between the Ritz values and FOM. We present an upper bound for the norm of the difference between the matrices from which the Ritz and harmonic Ritz values are computed. The differences between the Ritz and harmonic Ritz values enable us to describe the breakdown of FOM and stagnation of GMRES. Copyright © 1999 John Wiley & Sons, Ltd.     

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

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

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.     

Restarted Full Orthogonalization Method with Deflation for Shifted Linear Systems

In this paper, we study shifted restated full orthogonalization method with deflation for simultaneously solving a number of shifted systems of linear equations. Theoretical analysis shows that with the deflation technique, the new residual of shifted restarted FOM is still collinear with each other. Hence, the new approach can solve the shifted systems simultaneously based on the same Krylov subspace. Numerical experiments show that the deflation technique can significantly improve the convergence performance of shifted restarted FOM.     

Approximate Inverse Preconditioning for Shifted Linear Systems

In this paper we consider the problem of preconditioning symmetric positive definite matrices of the form A =A+I where >0. We discuss how to cheaply modify an existing sparse approximate inverse preconditioner for A in order to obtain a preconditioner for A . Numerical experiments illustrating the performance of the proposed approaches are presented.     

隐式重新启动的Lanczos算法在模型降阶中的应用

主要研究了一种隐式重新启动的L anczos算法在模型降阶中的应用.分析了由这个算法得到的降价后的模型的一些性质,对于一个n阶稳定的线性时不变系统,模型降阶的思想是寻找一个m阶转换函数来近似原系统的n阶转换函数H(s),其中n m.传统的kry lov子空间方法仅仅产生一个不稳定的实现,并且在低频处的误差较大,本文所考虑的隐式重新启动的L anczos方法,能较好的解决上述两个问题.     

位移方程组的渐近不完全分解预条件处理

讨论位移方程组(A α_jI)x(α_j)=b(α_j,x(α_i)),(i相似文献   

ON AUGMENTED LAGRANGIAN METHODS FOR SADDLE-POINT LINEAR SYSTEMS WITH SINGULAR OR SEMIDEFINITE （1, 1） BLOCKS

An effective algorithm for solving large saddle-point linear systems, presented by Krukier et al., is applied to the constrained optimization problems. This method is a modification of skew-Hermitian triangular splitting iteration methods. We consider the saddle-point linear systems with singular or semidefinite （1, 1） blocks. Moreover, this method is applied to precondition the GMRES. Numerical results have confirmed the effectiveness of the method and showed that the new method can produce high-quality preconditioners for the Krylov subspace methods for solving large sparse saddle-point linear systems.     

Computation of matrix functions with deflated restarting

A deflated restarting Krylov subspace method for approximating a function of a matrix times a vector is proposed. In contrast to other Krylov subspace methods, the performance of the method in this paper is better. We further show that the deflating algorithm inherits the superlinear convergence property of its unrestarted counterpart for the entire function and present the results of numerical experiments.     

On IOM(q): The Incomplete Orthogonalization Method for Large Unsymmetric Linear Systems

The incomplete orthogonalization method (IOM(q)), a truncated version of the full orthogonalization method (FOM) proposed by Saad, has been used for solving large unsymmetric linear systems. However, no convergence analysis has been given. In this paper, IOM(q) is analysed in detail from a theoretical point of view. A number of important results are derived showing how the departure of the matrix A from symmetric affects the basis vectors generated by IOM(q), and some relationships between the residuals for IOM(q) and FOM are established. The results show that IOM(q) behaves much like FOM once the basis vectors generated by it are well conditioned. However, it is proved that IOM(q) may generate an ill-conditioned basis for a general unsymmetric matrix such that IOM(q) may fail to converge or at least cannot behave like FOM. Owing to the mathematical equivalence between IOM(q) and the truncated ORTHORES(q) developed by Young and Jea, insights are given into the convergence of the latter. A possible strategy is proposed for choosing the parameter q involved in IOM(q). Numerical experiments are reported to show convergence behaviour of IOM(q) and of its restarted version.     

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.     

求解增广线性系统的局部多分裂迭代法

为了在高性能计算机上求解增广线性系统,基于并行多分裂的两种技巧,本文提出一种局部多分裂迭代格式,给出当增广线性系统的矩阵为M-矩阵和H-矩阵时新方法的收敛性理论.并讨论预条件矩阵的特征值情形.     

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.     

Krylov Subspaces Associated with Higher-Order Linear Dynamical Systems

A standard approach to model reduction of large-scale higher-order linear dynamical systems is to rewrite the system as an equivalent first-order system and then employ Krylov-subspace techniques for model reduction of first-order systems. This paper presents some results about the structure of the block-Krylov subspaces induced by the matrices of such equivalent first-order formulations of higher-order systems. Two general classes of matrices, which exhibit the key structures of the matrices of first-order formulations of higher-order systems, are introduced. It is proved that for both classes, the block-Krylov subspaces induced by the matrices in these classes can be viewed as multiple copies of certain subspaces of the state space of the original higher-order system. AMS subject classification (2000) 65F30, 15A57, 65P99, 41A21     

A Variant of the ORTHOMIN(2) Method for Singular Linear Systems

For singular linear systems A x=b, ORTHOMIN(2) is known theoretically to attain the minimum residual min _xR nb–A x₂ under a certain condition. However, in the actual computation with finite precision arithmetic, the residual is often observed to be reduced further than the theoretically expected level. Therefore, we propose a variant of ORTHOMIN(2), which is mathematically equivalent to the original ORTHOMIN(2) method, but uses recurrence formulas that are different from those of ORTHOMIN(2); they contain alternative expressions for the auxiliary vector and the recurrence coefficients. Although our implementation has the same computational costs as ORTHOMIN(2), numerical experiments on singular systems show that our implementation is more accurate and less affected by rounding errors than ORTHOMIN(2).     

ON THE BREAKDOWNS OF THE GALERKIN AND LEAST-SQUARES METHODS

1　ＩｎｔｒｏｄｕｃｔｉｏｎＷｅｃｏｎｓｉｄｅｒｌｉｎｅａｒｓｙｓｔｅｍｓｏｆｔｈｅｆｏｒｍＡｘ=ｂ,(1 )ｗｈｅｒｅＡ∈ＣＮ×Ｎｉｓｎｏｎｓｉｎｇｕｌａｒａｎｄｐｏｓｓｉｂｌｙｎｏｎ Ｈｅｒｍｉｔｉａｎ .Ａｍａｊｏｒｃｌａｓｓｏｆｍｅｔｈｏｄｓｆｏｒｓｏｌｖｉｎｇ (1 )ｉｓｔｈｅｃｌａｓｓｏｆＫｒｙｌｏｖｓｕｂｓｐａｃｅｍｅｔｈｏｄｓ (ｓｅｅ[6] ,[1 3]ｆｏｒｏｖｅｒｖｉｅｗｓｏｆｓｕｃｈｍｅｔｈｏｄｓ) ,ｄｅｆｉｎｅｄｂｙｔｈｅｐｒｏｐｅｒｔｉｅｓｘｍ ∈ｘ0 +Ｋｍ(ｒ0 ,Ａ) ;(2 )ｒｍ ⊥Ｌｍ, (3)ｗｈｅ…     

The global Hessenberg and CMRH methods for linear systems with multiple right-hand sides

In this paper, we introduce two new methods for solving large sparse nonsymmetric linear systems with several right-hand sides. These methods are the global Hessenberg and global CMRH methods. Using the global Hessenberg process, these methods are less expensive than the global FOM and global GMRES methods [9]. Theoretical results about the new methods are given, and experimental results that show good performances of these new methods are presented.     

求解病态线性方程组的收缩Lanczos方法

Lanczos方法是求解大型线性方程组的常用方法.遗憾的是,在Lanczos过程中通常会发生算法中断或数值不稳定的情况.将给出求解大型对称线性方程组的收缩Lanczos方法,即DLanczos方法.新算法将采用增广子空间技术,在Lanczos过程中向Krylov子空间加入少量绝对值较小的特征值所对应的特征向量进行收缩.数值实验表明,新算法比Lanczos方法收敛速度更快,并且适合求解病态对称线性方程组.