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.     

Alternating Krylov subspace image restoration methods

Alternating methods for image deblurring and denoising have recently received considerable attention. The simplest of these methods are two-way methods that restore contaminated images by alternating between deblurring and denoising. This paper describes Krylov subspace-based two-way alternating iterative methods that allow the application of regularization operators different from the identity in both the deblurring and the denoising steps. Numerical examples show that this can improve the quality of the computed restorations. The methods are particularly attractive when matrix-vector products with a discrete blurring operator and its transpose can be evaluated rapidly, but the structure of these operators does not allow inexpensive diagonalization.     

A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems

The inverse-free preconditioned Krylov subspace method of Golub and Ye [G.H. Golub, Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comp. 24 (2002) 312-334] is an efficient algorithm for computing a few extreme eigenvalues of the symmetric generalized eigenvalue problem. In this paper, we first present an analysis of the preconditioning strategy based on incomplete factorizations. We then extend the method by developing a block generalization for computing multiple or severely clustered eigenvalues and develop a robust black-box implementation. Numerical examples are given to illustrate the analysis and the efficiency of the block algorithm.     

Krylov subspace methods of Hessenberg based for algebraic Riccati equation

In this paper, we propose a class of special Krylov subspace methods to solve continuous algebraic Riccati equation (CARE), i.e., the Hessenberg-based methods. The presented approaches can obtain efficiently the solution of algebraic Riccati equation to some extent. The main idea is to apply Kleinman-Newton"s method to transform the process of solving algebraic Riccati equation into Lyapunov equation at every inner iteration. Further, the Hessenberg process of pivoting strategy combined with Petrov-Galerkin condition and minimal norm condition is discussed for solving the Lyapunov equation in detail, then we get two methods, namely global generalized Hessenberg (GHESS) and changing minimal residual methods based on the Hessenberg process (CMRH) for solving CARE, respectively. Numerical experiments illustrate the efficiency of the provided methods.     

Restarted generalized Krylov subspace methods for solving large-scale polynomial eigenvalue problems

In this paper, we introduce a generalized Krylov subspace based on a square matrix sequence {A _j } and a vector sequence {u _j }. Next we present a generalized Arnoldi procedure for generating an orthonormal basis of . By applying the projection and the refined technique, we derive a restarted generalized Arnoldi method and a restarted refined generalized Arnoldi method for solving a large-scale polynomial eigenvalue problem (PEP). These two methods are applied to solve the PEP directly. Hence they preserve essential structures and properties of the PEP. Furthermore, restarting reduces the storage requirements. Some theoretical results are presented. Numerical tests report the effectiveness of these methods. Yimin Wei is supported by the National Natural Science Foundation of China and Shanghai Education Committee.     

Deflation in Krylov subspace methods and distance to uncontrollability

The task of extracting from a Krylov decomposition the approximation to an eigenpair that yields the smallest backward error can be phrased as finding the smallest perturbation which makes an associated matrix pair uncontrollable. Exploiting this relationship, we propose a new deflation criterion, which potentially admits earlier deflations than standard deflation criteria. Along these lines, a new deflation procedure for shift-and-invert Krylov methods is developed. Numerical experiments demonstrate the merits and limitations of this approach. This author has been supported by a DFG Emmy Noether fellowship and in part by the Swedish Foundation for Strategic Research under the Frame Programme Grant A3 02:128.     

Matrix Krylov subspace methods for linear systems with multiple right-hand sides

In this paper, we first give a result which links any global Krylov method for solving linear systems with several right-hand sides to the corresponding classical Krylov method. Then, we propose a general framework for matrix Krylov subspace methods for linear systems with multiple right-hand sides. Our approach use global projection techniques, it is based on the Global Generalized Hessenberg Process (GGHP) – which use the Frobenius scalar product and construct a basis of a matrix Krylov subspace – and on the use of a Galerkin or a minimizing norm condition. To accelerate the convergence of global methods, we will introduce weighted global methods. In these methods, the GGHP uses a different scalar product at each restart. Experimental results are presented to show the good performances of the weighted global methods. AMS subject classification 65F10     

Spectral Variants of Krylov Subspace Methods

Krylov iterative methods usually solve an optimization problem, per iteration, to obtain a vector whose components are the step lengths associated with the previous search directions. This vector can be viewed as the solution of a multiparameter optimization problem. In that sense, Krylov methods can be combined with the spectral choice of step length that has recently been developed to accelerate descent methods in optimization. In this work, we discuss different spectral variants of Krylov methods and present encouraging preliminary numerical experiments, with and without preconditioning.     

A note on Krylov subspace methods for singular systems

Recently, Calvetti et al. have published an interesting paper [Linear Algebra Appl. 316 (2000) 157–169] concerning the least-squares solution of a singular system by using the so-called range restricted GMRES (RRGMRES) method. However, one of the main results (cf. [loc. cit., Theorem 3.3]) seems to be incomplete. As a complement of paper [loc. cit.], in this note we first make an example to show the incompleteness of that theorem, then we give a modified result.     

On preconditioned Krylov subspace methods for discrete convection–diffusion problems

We study nonstationary iterative methods for solving preconditioned systems arising from discretizations of the convection–diffusion equation. The preconditioners arise from Gauss–Seidel methods applied to the original system. It is shown that the performance of the iterative solvers is affected by the relationship of the ordering of the underlying grid and the direction of the fow associated with the differential operator. Specifically, only those orderings that follow the fow give fast iterative solvers. © 1997 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 13 :321–330     

Roundoff error analysis of algorithms based on Krylov subspace methods

We study the roundoff error propagation in an algorithm which computes the orthonormal basis of a Krylov subspace with Householder orthonormal matrices. Moreover, we analyze special implementations of the classical GMRES algorithm, and of the Full Orthogonalization Method. These techniques approximate the solution of a large sparse linear system of equations on a sequence of Krylov subspaces of small dimension. The roundoff error analyses show upper bounds for the error affecting the computed approximated solutions.This work was carried out with the financial contribution of the Human Capital and Mobility Programme of the European Union grant ERB4050PL921378.     

A geometric view of Krylov subspace methods on singular systems

We give a geometric framework for analysing iterative methods on singular linear systems A x = b and apply them to Krylov subspace methods. The idea is to decompose the method into the ?(A) component and its orthogonal complement ?(A)^?, where ?(A) is the range of A. We apply the framework to GMRES, GMRES(k) and GCR(k), and derive conditions for convergence without breakdown for inconsistent and consistent singular systems. The approach also gives a geometric interpretation and different proofs of the conditions obtained by Brown and Walker for GMRES. We also give examples arising in the finite difference discretization of two‐point boundary value problems of an ordinary differential equation. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

A multigrid-based preconditioned Krylov subspace method for the Helmholtz equation with PML

In this paper, we generalize the complex shifted Laplacian preconditioner to the complex shifted Laplacian-PML preconditioner for the Helmholtz equation with perfectly matched layer (Helmholtz-PML equation). The Helmholtz-PML equation is discretized by an optimal 9-point difference scheme, and the preconditioned linear system is solved by the Krylov subspace method, especially by the biconjugate gradient stabilized method (Bi-CGSTAB). The spectral analysis of the linear system is given, and a new matrix-based interpolation operator is proposed for the multigrid method, which is used to approximately invert the preconditioner. The numerical experiments are presented to illustrate the efficiency of the preconditioned Bi-CGSTAB method with the multigrid based on the new interpolation operator, also, numerical results are given for comparing the performance of the new interpolation operator with that of classic bilinear interpolation operator and the one suggested in Erlangga et al. (2006) [10].     

Adaptive solution of infinite linear systems by Krylov subspace methods

In this paper we consider the problem of approximating the solution of infinite linear systems, finitely expressed by a sparse coefficient matrix. We analyse an algorithm based on Krylov subspace methods embedded in an adaptive enlargement scheme. The management of the algorithm is not trivial, due to the irregular convergence behaviour frequently displayed by Krylov subspace methods for nonsymmetric systems. Numerical experiments, carried out on several test problems, indicate that the more robust methods, such as GMRES and QMR, embedded in the adaptive enlargement scheme, exhibit good performances.     

Comparison of Krylov subspace methods on the PageRank problem

PageRank algorithm plays a very important role in search engine technology and consists in the computation of the eigenvector corresponding to the eigenvalue one of a matrix whose size is now in the billions. The problem incorporates a parameter that determines the difficulty of the problem. In this paper, the effectiveness of stationary and nonstationary methods are compared on some portion of real web matrices for different choices of . We see that stationary methods are very reliable and more competitive when the problem is well conditioned, that is for small values of . However, for large values of the parameter the problem becomes more difficult and methods such as preconditioned BiCGStab or restarted preconditioned GMRES become competitive with stationary methods in terms of Mflops count as well as in number of iterations necessary to reach convergence.     

Implementation of a restarted Krylov subspace method for the evaluation of matrix functions

A new implementation of restarted Krylov subspace methods for evaluating f(A)b for a function f, a matrix A and a vector b is proposed. In contrast to an implementation proposed previously, it requires constant work and constant storage space per restart cycle. The convergence behavior of this scheme is discussed and a new stopping criterion based on an error indicator is given. The performance of the implementation is illustrated for three parabolic initial value problems, requiring the evaluation of exp(A)b.     

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.     

On the convergence of two‐level Krylov methods for singular symmetric systems

We discuss the convergence of a two‐level version of the multilevel Krylov method for solving linear systems of equations with symmetric positive semidefinite matrix of coefficients. The analysis is based on the convergence result of Brown and Walker for the Generalized Minimal Residual method (GMRES), with the left‐ and right‐preconditioning implementation of the method. Numerical results based on diffusion problems are presented to show the convergence.