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.     

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.     

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.     

Backward error bounds for approximate Krylov subspaces

Let A be a matrix of order n and let be a subspace of dimension k. In this note, we determine a matrix E of minimal norm such that is a Krylov subspace of A+E.     

A Krylov subspace algorithm for multiquadric interpolation in many dimensions

We consider the version of multiquadric interpolation wherethe interpolation conditions are the equations s(x_i) = f_i, i= 1,2,..., n, and where the interpolant has the form s(x) =_j=1ⁿ _j (||x – x_j ||² + c²)^1/2 + x R^d, subject to theconstraint _j=1ⁿ _j = 0. The points x_i R^d, the right-hand sidesf_i, i = 1,2,...,n, and the constant c are data. The equationsand the constraint define the parameters _j, j = 1,2,...,n, and. The resultant approximation s f is useful in many applications,but the calculation of the parameters by direct methods requiresO (n³) operations, and n may be large. Therefore iterative proceduresfor this calculation have been studied at Cambridge since 1993,the main task of each iteration being the computation of s(x_i),i = 1,2,...,n, for trial values of the required parameters.These procedures are based on approximations to Lagrange functions,and often they perform very well. For example, ten iterationsusually provide enough accuracy in the case d = 2 and c = 0,for general positions of the data points, but the efficiencydeteriorates if d and c are increased. Convergence can be guaranteedby the inclusion of a Krylov subspace technique that employsthe native semi-norm of multiquadric functions. An algorithmof this kind is specified, its convergence is proved, and carefulattention is given to the choice of the operator that definesthe Krylov subspace, which is analogous to pre-conditioningin the conjugate gradient method. Finally, some numerical resultsare presented and discussed, for values of d and n from theintervals [2,40] and [200,10 000], respectively.     

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.     

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.     

Deflated Krylov subspace methods for nearly singular linear systems

This paper concerns the use of Krylov subspace methods for the solution of nearly singular nonsymmetric linear systems. We show that the incomplete orthogonalization methods (IOM) in conjunction with certain deflation techniques of Stewart, Chan, and Saad can be used to solve large nonsymmetric linear systems which are nearly singular.This work was supported by the National Science Foundation, Grants DMS-8403148 and DCR-81-16779, and by the Office of Naval Research, Contract N00014-85-K-0725.     

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.     

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     

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].     

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.     

Krylov subspace methods for eigenvalues with special properties and their analysis for normal matrices

In this paper we propose a general approach by which eigenvalues with a special property of a given matrix A can be obtained. In this approach we first determine a scalar function ψ: C → C whose modulus is maximized by the eigenvalues that have the special property. Next, we compute the generalized power iterations uinj + 1 = ψ(A)u_j, j = 0, 1,…, where u₀ is an arbitrary initial vector. Finally, we apply known Krylov subspace methods, such as the Arnoldi and Lanczos methods, to the vector u_n for some sufficiently large n. We can also apply the simultaneous iteration method to the subspace span{x⁽ⁿ⁾₁,…,x⁽ⁿ⁾_k} with some sufficiently large n, where x^(j+1)_m = ψ(A)x^(j)_m, j = 0, 1,…, m = 1,…, k. In all cases the resulting Ritz pairs are approximations to the eigenpairs of A with the special property. We provide a rather thorough convergence analysis of the approach involving all three methods as n → ∞ for the case in which A is a normal matrix. We also discuss the connections and similarities of our approach with the existing methods and approaches in the literature.     

积分算子作用下的亚纯多叶函数

令∑_p表示形如f(z)=z~(-p)+∑m=1∞(p∈N={1,2,3…})且在去心单位开圆盘D=U\{0}={z∶z∈C且0|z|1}上解析的亚纯多叶函数类.利用一个作用在∑_p上的乘积算子定义了几个新的亚纯函数的子类,并考虑这些函数类在积分算子作用下的性质.     

The Uniqueness Problem for Subordinate Resolvents with Potential Theoretical Methods

We present an analytic version of the following uniqueness problem for Markov processes: if two subprocesses of a given transient, Borel right process have the same excessive functions then they coincide. Our treatment is given in terms of subordinate sub-Markovian resolvents of kernels in the sense of P. A. Mayer and uses essentially the subordination operators introduced by G. Mokobodzki.      

与Dziok-Srivastava算子相关的正系数亚纯多叶函数类

利用Dziok-Srivastava算子定义了单位圆盘内以原点为极点的具有正系数的p叶亚纯函数的子类Wp+,q,s(α1,α),考察它们的各种性质,并将解析函数的邻域概念运用于此亚纯多叶函数类.     

Bounds to eigenvalues of the Laplacian on L-shaped domain by variational methods

In this study, the bounds for eigenvalues of the Laplacian operator on an L-shaped domain are determined. By adopting some special functions in Goerisch method for lower bounds and in traditional Rayleigh–Ritz method for upper bounds, very accurate bounds to eigenvalues for the problem are obtained. Numerical results show that these functions can also be successfully used to solve the problem on the region with other reentrant angle.     

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.     

Expressions and Bounds for the GMRES Residual

Expressions and bounds are derived for the residual norm in GMRES. It is shown that the minimal residual norm is large as long as the Krylov basis is well-conditioned. For scaled Jordan blocks the minimal residual norm is expressed in terms of eigenvalues and departure from normality. For normal matrices the minimal residual norm is expressed in terms of products of relative eigenvalue differences.