Block Krylov Subspace Methods for Solving Large Sylvester Equations

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX–XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.     

Approximate inverse preconditioner by computing approximate solution of Sylvester equation

This paper presents a new method for obtaining a matrix M which is an approximate inverse preconditioner for a given matrix A, where the eigenvalues of A all either have negative real parts or all have positive real parts. This method is based on the approximate solution of the special Sylvester equation AX + XA = 2I. We use a Krylov subspace method for obtaining an approximate solution of this Sylvester matrix equation which is based on the Arnoldi algorithm and on an integral formula. The computation of the preconditioner can be carried out in parallel and its implementation requires only the solution of very simple and small Sylvester equations. The sparsity of the preconditioner is preserved by using a proper dropping strategy. Some numerical experiments on test matrices from Harwell–Boing collection for comparing the numerical performance of the new method with an available well-known algorithm are presented.     

On the Krylov subspace methods based on tensor format for positive definite Sylvester tensor equations

This paper deals with studying some of well‐known iterative methods in their tensor forms to solve a Sylvester tensor equation. More precisely, the tensor form of the Arnoldi process and full orthogonalization method are derived by using a product between two tensors. Then tensor forms of the conjugate gradient and nested conjugate gradient algorithms are also presented. Rough estimation of the required number of operations for the tensor form of the Arnoldi process is obtained, which reveals the advantage of handling the algorithms based on tensor format over their classical forms in general. Some numerical experiments are examined, which confirm the feasibility and applicability of the proposed algorithms in practice. Copyright © 2016 John Wiley & Sons, Ltd.     

Sylvester与Lyapunov方程向后误差分析

利用矩阵Kronecker积的性质,研究Sylvester矩阵方程Ax YB=C与Lyapunov矩阵方程ATX XA=-Q(Q0)的向后误差,获得了这两类矩阵方程向后误差η(X,Y)与η(X)的精确表达式及其更易计算的上下界.这些结果是对有关文献相应结果的改进与补充.     

一类Sylvester矩阵方程的一个迭代算法

考虑这样一类Sylvester矩阵方程:AX XB=C,A,B分别为n阶正半定、正定矩阵,C为n阶矩阵.给出了一个收敛的迭代算法.     

连续Sylvester矩阵方程求解的分裂迭代算法

有效求解连续的Sylvester矩阵方程对于科学和工程计算有着重要的应用价值,因此该文提出了一种可行的分裂迭代算法.该算法的核心思想是外迭代将连续Sylvester矩阵方程的系数矩阵分裂为对称矩阵和反对称矩阵,内迭代求解复对称矩阵方程.相较于传统的分裂算法,该文所提出的分裂迭代算法有效地避免了最优迭代参数的选取,并利用了复对称方程组高效求解的特点,进而提高了算法的易实现性、易操作性.此外,从理论层面进一步证明了该分裂迭代算法的收敛性.最后,通过数值算例表明分裂迭代算法具有良好的收敛性和鲁棒性,同时也证实了分裂迭代算法的收敛性很大程度依赖于内迭代格式的选取.     

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 version of the Smith method for solving Sylvester equation and discrete-time Sylvester equation

Recently, Xue etc. \cite{28} discussed the Smith method for solving Sylvester equation $AX+XB=C$, where one of the matrices $A$ and $B$ is at least a nonsingular $M$-matrix and the other is an (singular or nonsingular) $M$-matrix. Furthermore, in order to find the minimal non-negative solution of a certain class of non-symmetric algebraic Riccati equations, Gao and Bai \cite{gao-2010} considered a doubling iteration scheme to inexactly solve the Sylvester equations. This paper discusses the iterative error of the standard Smith method used in \cite{gao-2010} and presents the prior estimations of the accurate solution $X$ for the Sylvester equation. Furthermore, we give a new version of the Smith method for solving discrete-time Sylvester equation or Stein equation $AXB+X=C$, while the new version of the Smith method can also be used to solve Sylvester equation $AX+XB=C$, where both $A$ and $B$ are positive definite. % matrices. We also study the convergence rate of the new Smith method. At last, numerical examples are given to illustrate the effectiveness of our methods     

Computational Krylov‐based methods for large‐scale differential Sylvester matrix problems

In the present paper, we propose Krylov‐based methods for solving large‐scale differential Sylvester matrix equations having a low‐rank constant term. We present two new approaches for solving such differential matrix equations. The first approach is based on the integral expression of the exact solution and a Krylov method for the computation of the exponential of a matrix times a block of vectors. In the second approach, we first project the initial problem onto a block (or extended block) Krylov subspace and get a low‐dimensional differential Sylvester matrix equation. The latter problem is then solved by some integration numerical methods such as the backward differentiation formula or Rosenbrock method, and the obtained solution is used to build the low‐rank approximate solution of the original problem. We give some new theoretical results such as a simple expression of the residual norm and upper bounds for the norm of the error. Some numerical experiments are given in order to compare the two approaches.     

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.     

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     

Multilevel Minimal Residual Methods for Nonsymmetric Elliptic Problems

The subject of this paper is to study the performance of multilevel preconditioning for nonsymmetric elliptic boundary value problems. In particular, a minimal residual method with respect to an appropriately scaled norm, measuring the size of the residual projections on all levels, is studied. This norm, induced by the multilevel splitting, is also the basis for a proper stopping criterion. Our analysis shows that the convergence rate of this minimal residual method using the multilevel preconditioner by Bramble, pasciak and Xu is bounded independently of the mesh-size. However, the convergence rate deteriorates with increasing size of the skew-symmetric part. Our numerical results show that by incorporating this into a multilevel cycle starting on the coarsest level, one can save fine-level-iterations and, therefore, computational work.     

ON THE BREAKDOWNS OF THE GALERKIN AND LEAST-SQUARES METHODS

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

Convergence of Krylov methods for sums of two operators

We discuss the convergence of Krylov subspace methods for equationsx =Tx +f whereT is a sum of two operators,T =B +K, whereB is bounded andK is nuclear. Bounds are given for inf Q _k (B+K) and for inf p _k (B+K), where the infimum is over all polynomials of degreek, such thatQ _k is monic andp _k is normalized:p _k (1) = 1.     

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.     

求解大规模非Hermite线性方程组的Krylov子空间型方法的收敛性分析

本文用统一的方式研究了当系数矩阵Ａ亏损且其谱位于右（左）半开平面时很多求解大规模非Ｈｅｒｍｉｔｅ线性方程组的Ｋｒｙｌｏｖ子空间型方法的收敛性，建立了有关的理论收敛界，揭示了收敛速度和Ａ的谱之间的内在联系．结果证明，当如下三种情形之一出现时，这些方法的收敛速度将会减慢：Ａ亏损，其谱的分布不理想，或Ａ的Ｊｏｒｄａｎ基病态．在证明中，我们给出了Ｃｈｅｂｙｓｈｅｖ多项式的高阶导数在复平面中某椭圆域上的若干新性质，其中之一修正了文献中广泛使用的一个结果．     

Shift-and-Invert Krylov Methods for Time-Fractional Wave Equations

The article deals with evolution problems involving time derivatives of fractional order α, with 1 < α ≤2. The solutions are expressed in terms of operator Mittag-Leffler functions. The action of such operator functions is approximated by rational Krylov methods whose convergence features are investigated.     

Compress‐and‐restart block Krylov subspace methods for Sylvester matrix equations

Block Krylov subspace methods (KSMs) comprise building blocks in many state‐of‐the‐art solvers for large‐scale matrix equations as they arise, for example, from the discretization of partial differential equations. While extended and rational block Krylov subspace methods provide a major reduction in iteration counts over polynomial block KSMs, they also require reliable solvers for the coefficient matrices, and these solvers are often iterative methods themselves. It is not hard to devise scenarios in which the available memory, and consequently the dimension of the Krylov subspace, is limited. In such scenarios for linear systems and eigenvalue problems, restarting is a well‐explored technique for mitigating memory constraints. In this work, such restarting techniques are applied to polynomial KSMs for matrix equations with a compression step to control the growing rank of the residual. An error analysis is also performed, leading to heuristics for dynamically adjusting the basis size in each restart cycle. A panel of numerical experiments demonstrates the effectiveness of the new method with respect to extended block KSMs.     

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.     

Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems

Summary. The convergence rate of Krylov subspace methods for the solution of nonsymmetric systems of linear equations, such as GMRES or FOM, is studied. Bounds on the convergence rate are presented which are based on the smallest real part of the field of values of the coefficient matrix and of its inverse. Estimates for these quantities are available during the iteration from the underlying Arnoldi process. It is shown how these bounds can be used to study the convergence properties, in particular, the dependence on the mesh-size and on the size of the skew-symmetric part, for preconditioners for finite element discretizations of nonsymmetric elliptic boundary value problems. This is illustrated for the hierarchical basis and multilevel preconditioners which constitute popular preconditioning strategies for such problems. Received May 3, 1996