Resolvent Krylov subspace approximation to operator functions

We consider the approximation of operator functions in resolvent Krylov subspaces. Besides many other applications, such approximations are currently of high interest for the approximation of φ-functions that arise in the numerical solution of evolution equations by exponential integrators. It is well known that Krylov subspace methods for matrix functions without exponential decay show superlinear convergence behaviour if the number of steps is larger than the norm of the operator. Thus, Krylov approximations may fail to converge for unbounded operators. In this paper, we analyse a rational Krylov subspace method which converges not only for finite element or finite difference approximations to differential operators but even for abstract, unbounded operators whose field of values lies in the left half plane. In contrast to standard Krylov methods, the convergence will be independent of the norm of the discretised operator and thus of the spatial discretisation. We will discuss efficient implementations for finite element discretisations and illustrate our analysis with numerical experiments.     

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.     

Inexact Perturbed Newton Methods and Applications to a Class of Krylov Solvers

Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system (Ref. 1). The local convergence theory given by the authors of Ref. 1 and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals. We extend this local convergence theory to the general case, characterizing the rate of convergence in terms of the perturbations and residuals.The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton–Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton–Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method. At the end of the paper, the theoretical results are verified on some numerical examples.     

Analysis and Applications of Extended Kantorovich–Krylov Method

In our prior work, the two-dimensional bending and in-plane mode shape functions of isotropic rectangular plates were solved based on the extended Kantorovich–Krylov method. These plate modes were then applied to sandwich plate analysis using the assumed modes method. Numerical results has shown these two-dimensional plate modes improved our sandwich plate analysis. However, the rigorous mathematical convergence proof of the extended Kantorovich–Krylov method is lacking. In this article, we provide a rigorous mathematical convergence proof of the extended Kantorovich–Krylov method using the example of rectangular plate bending vibration, in which the governing equation is a biharmonic equation. The predictions of natural frequency and mode shape functions based on the extended Kantorovich–Krylov method were calculated and the results were numerically validated by other analyses. A similar convergence proof can be applied to other types of partial differential equations (PDEs) that govern vibration problems in engineering applications. Based on these results, the extended Kantorovich–Krylov method was proven to be a powerful tooi for the boundary value problems of partial differential equations in the structural vibrations.     

Further analysis of minimum residual iterations

The convergence behaviour of a number of algorithms based on minimizing residual norms over Krylov subspaces is not well understood. Residual or error bounds currently available are either too loose or depend on unknown constants that can be very large. In this paper we take another look at traditional as well as alternative ways of obtaining upper bounds on residual norms. In particular, we derive inequalities that utilize Chebyshev polynomials and compare them with standard inequalities. Copyright © 2000 John Wiley & Sons, Ltd.     

Rational approximation to trigonometric operators

We consider the approximation of trigonometric operator functions that arise in the numerical solution of wave equations by trigonometric integrators. It is well known that Krylov subspace methods for matrix functions without exponential decay show superlinear convergence behavior if the number of steps is larger than the norm of the operator. Thus, Krylov approximations may fail to converge for unbounded operators. In this paper, we propose and analyze a rational Krylov subspace method which converges not only for finite element or finite difference approximations to differential operators but even for abstract, unbounded operators. In contrast to standard Krylov methods, the convergence will be independent of the norm of the operator and thus of its spatial discretization. We will discuss efficient implementations for finite element discretizations and illustrate our analysis with numerical experiments. AMS subject classification (2000)  65F10, 65L60, 65M60, 65N22     

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.     

Conjugate gradient and minimal residual methods for solving symmetric indefinite systems

Norm-minimizing-type methods for solving large sparse linear systems with symmetric and indefinite coefficient matrices are considered. The Krylov subspace can be generated by either the Lanczos approach, such as the methods MINRES, GMRES and QMR, or by a conjugate-gradient approach. Here, we propose an algorithm based on the latter approach. Some relations among the search directions and the residuals, and how the search directions are related to the Krylov subspace are investigated. Numerical experiments are reported to verify the convergence properties.     

Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions

A superlinear convergence bound for rational Arnoldi approximations to functions of matrices is derived. This bound generalizes the well-known superlinear convergence bound for the conjugate gradient method to more general functions with finite singularities and to rational Krylov spaces. A constrained equilibrium problem from potential theory is used to characterize a max-min quotient of a nodal rational function underlying the rational Arnoldi approximation, where an additional external field is required for taking into account the poles of the rational Krylov space. The resulting convergence bound is illustrated at several numerical examples, in particular, the convergence of the extended Krylov method for the matrix square root.     

The block grade of a block Krylov space

The aim of the paper is to compile and compare basic theoretical facts on Krylov subspaces and block Krylov subspaces. Many Krylov (sub)space methods for solving a linear system Ax=b have the property that in exact computer arithmetic the true solution is found after ν iterations, where ν is the dimension of the largest Krylov subspace generated by A from r₀, the residual of the initial approximation x₀. This dimension is called the grade of r₀ with respect to A. Though the structure of block Krylov subspaces is more complicated than that of ordinary Krylov subspaces, we introduce here a block grade for which an analogous statement holds when block Krylov space methods are applied to linear systems with multiple, say s, right-hand sides. In this case, the s initial residuals are bundled into a matrix R₀ with s columns. The possibility of linear dependence among columns of the block Krylov matrix , which in practical algorithms calls for the deletion (or, deflation) of some columns, requires extra care. Relations between grade and block grade are also established, as well as relations to the corresponding notions of a minimal polynomial and its companion matrix.     

On IGMRES: An incomplete generalized minimal residual method for large unsymmetric linear systems

The truncated version of the generalized minimal residual method (GMRES), the incomplete generalized minimal residual method (IGMRES), is studied. It is based on an incomplete orthogonalization of the Krylov vectors in question, and gives an approximate or quasi-minimum residual solution over the Krylov subspace. A convergence analysis of this method is given, showing that in the non-restarted version IGMRES can behave like GMRES once the basis vectors of Krylov subspace generated by the incomplete orthogonalization are strongly linearly independent. Meanwhile, some relationships between the residual norms for IOM and IGMRES are established. Numerical experiments are reported to show convergence behavior of IGMRES and of its restarted version IGMRES(m). Project supported by the China State Key Basic Researches, the National Natural Science Foundation of China (Grant No. 19571014), the Doctoral Program (97014113), the Foundation of Returning Scholars of China and the Natural Science Foundation of Liaoning Province.     

Projection acceleration of Krylov solvers

In many applications it appears that the initial convergence of preconditioned Krylov solvers is slow. The reason for this is that a number of small eigenvalues are present. After these bad eigenvector components are approximated, the fast superlinear convergence sets in. A way to have fast convergence from the start is to remove these components by a projection. In this paper we give a comparison of some of these projection operators. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A note on constraint preconditioners for nonsymmetric saddle point problems

A class of constraint preconditioners for solving two‐by‐two block linear equations with the (1,2)‐block being the transpose of the (2,1)‐block and the (2,2)‐block being zero was investigated in a recent paper of Cao (Numer. Math. 2006; 103 :47–61). In this short note, we extend his idea by allowing the (1,2)‐block to be not equal to the transpose of the (2,1)‐block. Results concerning the spectrum, the form of the eigenvectors and the convergence behaviour of a Krylov subspace method, such as GMRES are presented. Copyright © 2007 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     

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.     

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     

Newton‐Krylov iterative matrix representative spectrum

The concept of a representative spectrum is introduced in the context of Newton‐Krylov methods. This concept allows a better understanding of convergence rate accelerating techniques for Krylov‐subspace iterative methods in the context of CFD applications of the Newton‐Krylov approach to iteratively solve sets of non‐linear equations. The dependence of the representative spectrum on several parameters such as mesh, Mach number or discretization techniques is studied and analyzed. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

GPU implementation of a Helmholtz Krylov solver preconditioned by a shifted Laplace multigrid method

A Helmholtz equation in two dimensions discretized by a second order finite difference scheme is considered. Krylov methods such as Bi-CGSTAB and IDR(s) have been chosen as solvers. Since the convergence of the Krylov solvers deteriorates with increasing wave number, a shifted Laplace multigrid preconditioner is used to improve the convergence. The implementation of the preconditioned solver on CPU (Central Processing Unit) is compared to an implementation on GPU (Graphics Processing Units or graphics card) using CUDA (Compute Unified Device Architecture). The results show that preconditioned Bi-CGSTAB on GPU as well as preconditioned IDR(s) on GPU is about 30 times faster than on CPU for the same stopping criterion.     

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.