Weighted and deflated global GMRES algorithms for solving large Sylvester matrix equations

The solution of a large-scale Sylvester matrix equation plays an important role in control and large scientific computations. In this paper, we are interested in the large Sylvester matrix equation with large dimensionA and small dimension B, and a popular approach is to use the global Krylov subspace method. In this paper, we propose three new algorithms for this problem. We first consider the global GMRES algorithm with weighting strategy, which can be viewed as a precondition method. We present three new schemes to update the weighting matrix during iterations. Due to the growth of memory requirements and computational cost, it is necessary to restart the algorithm effectively. The deflation strategy is efficient for the solution of large linear systems and large eigenvalue problems; to the best of our knowledge, little work is done on applying deflation to the (weighted) global GMRES algorithm for large Sylvester matrix equations. We then consider how to combine the weighting strategy with deflated restarting, and propose a weighted global GMRES algorithm with deflation for solving large Sylvester matrix equations. In particular, we are interested in the global GMRES algorithm with deflation, which can be viewed as a special case when the weighted matrix is chosen as the identity. Theoretical analysis is given to show rationality of the new algorithms. Numerical experiments illustrate the numerical behavior of the proposed algorithms.

     

陀螺系统特征值问题的收缩Jacobi-Davidson方法

本文研究陀螺系统特征值问题的Jacobi-Davidson方法. 利用陀螺系统的结构性质,给出了求解Jacobi-Davidson方法中校正方程的有效方法. 基于非等价低秩收缩技术,给出了计算陀螺系统一些特征值的收缩Jacobi-Davidson方法. 数值结果表明本文所给算法是有效的.     

求解陀螺系统特征值问题的收缩二阶Lanczos方法

本文研究陀螺系统特征值问题的数值解法,利用反对称矩阵Lanczos算法,提出了求解陀螺系统特征值问题的二阶Lanczos方法.基于提出的陀螺系统特征值问题的非等价低秩收缩技术,给出了计算陀螺系统极端特征值的收缩二阶Lanczos方法.数值结果说明了算法的有效性.     

A posteriori error bounds for the zeros of a polynomial

Summary An algorithm for the computation of error bounds for the zeros of a polynomial is described. This algorithm is derived by applying Rouché's theorem to a Newton-like interpolation formula for the polynomial, and so it is suitable in the case where the approximations to the zeros of the polynomial are computed successively using deflation. Confluent and clustered approximations are handled easily. However bounds for the local rouding errors in deflation, e.g. in Horner's scheme, must be known. In practical application the method can, especially in some ill-conditioned cases, compete with other known estimates.     

A numerical example showing that deflations based on rotation leads to higher relative accuracy in QR algorithm

We present a numerical example illustrating that the deflation procedure in Francis's implicitly shifted QR algorithm can be improved by a deflation criteria based on the QR decomposition of the upper Hessenberg matrix. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multiscale deflation solvers for flow in porous media

This work describes a novel physics-based deflation preconditioner approach for solving porous media flow problems characterized by highly heterogeneous media. The approach relies on high-conductivity block solutions after rearranging the linear system coefficients into high-conductive and low condutive blocks from a given physically driven threshold value. This rearranging relies on the Hoshen-Kopelman (H-K) algorithm that is commonly used to determine percolation clusters. The resulting preconditioner may alternatively be combined with a deflation preconditioning stage. The proposed approach is coined as a physics-based 2-stage deflation preconditioner (P2SDP). Numerical experiments on different permeability distributions reveal that P2SDP is a powerful means to solve pressure systems when compared to more conventional algebraic approaches such as the incomplete Cholesky factorization. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Linear response eigenvalue problem solved by extended locally optimal preconditioned conjugate gradient methods

The locally optimal block preconditioned 4-d conjugate gradient method (LOBP4dCG) for the linear response eigenvalue problem was proposed by Bai and Li (2013) and later was extended to the generalized linear response eigenvalue problem by Bai and Li (2014). We put forward two improvements to the method: A shifting deflation technique and an idea of extending the search subspace. The deflation technique is able to deflate away converged eigenpairs from future computation, and the idea of extending the search subspace increases convergence rate per iterative step. The resulting algorithm is called the extended LOBP4dCG (ELOBP4dCG). Numerical results of the ELOBP4dCG strongly demonstrate the capability of deflation technique and effectiveness the search space extension for solving linear response eigenvalue problems arising from linear response analysis of two molecule systems.     

Convergence acceleration of preconditioned conjugate gradient solver based on error vector sampling for a sequence of linear systems

In this article, we focus on solving a sequence of linear systems that have identical (or similar) coefficient matrices. For this type of problem, we investigate subspace correction (SC) and deflation methods, which use an auxiliary matrix (subspace) to accelerate the convergence of the iterative method. In practical simulations, these acceleration methods typically work well when the range of the auxiliary matrix contains eigenspaces corresponding to small eigenvalues of the coefficient matrix. We develop a new algebraic auxiliary matrix construction method based on error vector sampling in which eigenvectors with small eigenvalues are efficiently identified in the solution process. We use the generated auxiliary matrix for convergence acceleration in the following solution step. Numerical tests confirm that both SC and deflation methods with the auxiliary matrix can accelerate the solution process of the iterative solver. Furthermore, we examine the applicability of our technique to the estimation of the condition number of the coefficient matrix. We also present the algorithm of the preconditioned conjugate gradient method with condition number estimation.     

Restarted GMRES preconditioned by deflation

This paper presents a new preconditioning technique for the restarted GMRES algorithm. It is based on an invariant subspace approximation which is updated at each cycle. Numerical examples show that this deflation technique gives a more robust scheme than the restarted algorithm, at a low cost of operations and memory.     

Implicitly restarted and deflated GMRES

We introduce a deflation method that takes advantage of the IRA method, by extracting a GMRES solution from the Krylov basis computed within the Arnoldi process of the IRA method itself. The deflation is well-suited because it is done with eigenvectors associated to the eigenvalues that are closest to zero, which are approximated by IRA very quickly. By a slight modification, we adapt it to the FOM algorithm, and then to GMRES enhanced by imposing constraints within the minimization condition. The use of IRA enables us to reduce the number of matrix-vector products, while keeping a low storage. This revised version was published online in June 2006 with corrections to the Cover Date.     

Block Krylov–Schur method for large symmetric eigenvalue problems

Stewart’s Krylov–Schur algorithm offers two advantages over Sorensen’s implicitly restarted Arnoldi (IRA) algorithm. The first is ease of deflation of converged Ritz vectors, the second is the avoidance of the potential forward instability of the QR algorithm. In this paper we develop a block version of the Krylov–Schur algorithm for symmetric eigenproblems. Details of this block algorithm are discussed, including how to handle rank deficient cases and how to use varying block sizes. Numerical results on the efficiency of the block Krylov–Schur method are reported.     

Deflation algorithm for the multiple roots of a system of nonlinear equations

T. Ojika, S. Watanabe, and T. Mitsui (in preparation) have been developing a subroutine package NAES (Nonlinear Algebraic Equations Solver) for the numerical solutions of the system of nonlinear equations. An algorithm, in the package, termed the deflation algorithm, for determining multiple roots for a system of nonlinear equations, is presented and its effectiveness is shown by solving a numerical example.     

基于灰色灾变模型的通货紧缩预测

针对未来期间通货紧缩是否存在的分歧以及通货紧缩可能存在的危害性,利用灰色灾变预测模型结合中国通货紧缩的小样本数据,预测未来通货紧缩发生的日期,预测结果显示通货紧缩约在2020年前后出现,预测结果一方面意味着当前应该审慎选择货币政策和财政政策,另一方面在2020年前后应该积极调整货币政策和财政政策,避免通货紧缩的出现可能给经济运行带来的负面性影响.     

TWO ALGORITHMS FOR SYMMETRIC LINEAR SYSTEMS WITH MULTIPLE RIGHT-HAND SIDES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｍａｎｙａｐｐｌｉｃａｔｉｏｎｓｗｅｎｅｅｄｔｏｓｏｌｖｅｍｕｌｔｉｐｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓＡｘ(ｉ) =ｂ(ｉ) ,ｉ=1,… ,ｓ (1)ｗｉｔｈｔｈｅｓａｍｅｎ×ｎｒｅａｌｓｙｍｍｅｔｒｉｃｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘＡ ,ｂｕｔｓｄｉｆｆｅｒｅｎｔｒｉｇｈｔ ｈａｎｄｓｉｄｅｓｂ(ｉ) (ｉ=1,… ,ｓ) .Ｉｆａｌｌｏｆｔｈｅｒｉｇｈｔ ｈａｎｄｓｉｄｅｓａｒｅａｖａｉｌａｂｌｅｓｉｍｕｌｔａｎｅｏｕｓｌｙ ,ｔｈｅｎｔｈｅｓｅｓｌｉｎｅａｒｓｙｓｔｅ…     

有限区间上的函数K<1集压缩映象的性质

有界闭集上的函数Ｋ＜１集压缩映象是紧压缩映象，且是闭映象．有界闭凸集到自身的函数Ｋ＜１集压缩映象一定有不动点．     

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.     

Trimmed linearizations for structured matrix polynomials

We discuss the eigenvalue problem for general and structured matrix polynomials which may be singular and may have eigenvalues at infinity. We derive condensed forms that allow (partial) deflation of the infinite eigenvalue and singular structure of the matrix polynomial. The remaining reduced order staircase form leads to new types of linearizations which determine the finite eigenvalues and corresponding eigenvectors. The new linearizations also simplify the construction of structure preserving linearizations.     

Twofold deflation preconditioning of linear algebraic systems. I. Theory

In this paper, preconditioning of linear algebraic systems with symmetric positive-definite coefficient matrices by deflation is considered. The twofold deflation technique for simultaneously deflating largest s and smallest s eigenvalues using an appropriate deflating subspace of dimension s is suggested. The possibility of using the extreme Ritz vectors of the coefficient matrix for deflation is analyzed. Bibliography: 15 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 95–152. Translated by L. Yu. Kolotilina.     

广义特征值问题近似收缩对组误差的残量界限

近年来,人们对矩阵不变子空间和矩阵束的广义不变子空间的计算颇为注意,关于误差和摄动理论的研究也比较深入.对于单个矩阵的情况,[4]中研究了非规范矩阵的近似特征组的残量界限,与大多数已有的误差估计不同,这个界限是可计算的,因而便于