Relaxed Krylov subspace approximation

Recent computational and theoretical studies have shown that the matrix-vector product occurring at each step of a Krylov subspace method can be relaxed as the iterations proceed, i.e., it can be computed in a less exact manner, without degradation of the overall performance. In the present paper a general operator treatment of this phenomenon is provided and a new result further explaining its behavior is presented. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The approximation of generalized turning points\newline by Krylov subspace methods

Summary. Certain types of singular solutions of nonlinear parameter-dependent operator equations were characterized by Griewank and Reddien [5, 6] as regular solutions of suitable augmented systems. For their numerical approximation an approach based on the use of Krylov subspaces is here presented. The application to boundary value problems is illustrated by numerical examples. Received March 8, 1993 / Revised version received December 13, 1993     

Data-sparse approximation to the operator-valued functions of elliptic operator

In previous papers the arithmetic of hierarchical matrices has been described, which allows us to compute the inverse, for instance, of finite element stiffness matrices discretising an elliptic operator The required computing time is up to logarithmic factors linear in the dimension of the matrix. In particular, this technique can be used for the computation of the discrete analogue of a resolvent

In the present paper, we consider various operator functions, the operator exponential negative fractional powers , the cosine operator function and, finally, the solution operator of the Lyapunov equation. Using the Dunford-Cauchy representation, we get integrals which can be discretised by a quadrature formula which involves the resolvents mentioned above. We give error estimates which are partly exponentially, partly polynomially decreasing.

     

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.     

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.     

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.     

Alternatives for parallel Krylov subspace basis computation

Numerical methods related to Krylov subspaces are widely used in large sparse numerical linear algebra. Vectors in these subspaces are manipulated via their representation onto orthonormal bases. Nowadays, on serial computers, the method of Arnoldi is considered as a reliable technique for constructing such bases. However, although easily parallelizable, this technique is not as scalable as expected for communications. In this work we examine alternative methods aimed at overcoming this drawback. Since they retrieve upon completion the same information as Arnoldi's algorithm does, they enable us to design a wide family of stable and scalable Krylov approximation methods for various parallel environments. We present timing results obtained from their implementation on two distributed-memory multiprocessor supercomputers: the Intel Paragon and the IBM Scalable POWERparallel SP2. © 1997 John Wiley & Sons, Ltd.     

Three-dimensional eddy-current computation using Krylov subspace methods

This paper considers the numerical solution of a transmissionboundary-value problem for the time-harmonic Maxwell equationswith the help of a special finite-volume discretization. Applyingthis technique to several three-dimensional test problems, weobtain large, sparse, complex linear systems, which are solvedby four types of algorithm, using biconjugate gradients, squaredconjugate gradients, stabilized conjugate gradients, and generalizedminimal residuals, respectively. Wecombine these methods withsuitably chosen preconditioning matrices and compare the speedof convergence.     

Krylov type subspace methods for matrix polynomials

We consider solving eigenvalue problems or model reduction problems for a quadratic matrix polynomial Iλ² − Aλ − B with large and sparse A and B. We propose new Arnoldi and Lanczos type processes which operate on the same space as A and B live and construct projections of A and B to produce a quadratic matrix polynomial with the coefficient matrices of much smaller size, which is used to approximate the original problem. We shall apply the new processes to solve eigenvalue problems and model reductions of a second order linear input-output system and discuss convergence properties. Our new processes are also extendable to cover a general matrix polynomial of any degree.     

Recent advances in Krylov subspace spectral methods

This paper reviews the main properties, and most recent developments, of Krylov subspace spectral (KSS) methods for time-dependent variable-coefficient PDE. These methods use techniques developed by Golub and Meurant for approximating elements of functions of matrices by Gaussian quadrature in the spectral domain in order to achieve high-order accuracy in time and stability characteristic of implicit time-stepping schemes, even though KSS methods themselves are explicit. In fact, for certain problems, 1-node KSS methods are unconditionally stable. Furthermore, these methods are equivalent to high-order operator splittings, thus offering another perspective for further analysis and enhancement. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fast generalized cross validation using Krylov subspace methods

The task of fitting smoothing spline surfaces to meteorological data such as temperature or rainfall observations is computationally intensive. The generalized cross validation (GCV) smoothing algorithm, if implemented using direct matrix techniques, is O(n ³) computationally, and memory requirements are O(n ²). Thus, for data sets larger than a few hundred observations, the algorithm is prohibitively slow. The core of the algorithm consists of solving series of shifted linear systems, and iterative techniques have been used to lower the computational complexity and facilitate implementation on a variety of supercomputer architectures. For large data sets though, the execution time is still quite high. In this paper we describe a Lanczos based approach that avoids explicitly solving the linear systems and dramatically reduces the amount of time required to fit surfaces to sets of data.      

Recursion relations for the extended Krylov subspace method

The evaluation of matrix functions of the form f(A)v, where A is a large sparse or structured symmetric matrix, f is a nonlinear function, and v is a vector, is frequently subdivided into two steps: first an orthonormal basis of an extended Krylov subspace of fairly small dimension is determined, and then a projection onto this subspace is evaluated by a method designed for small problems. This paper derives short recursion relations for orthonormal bases of extended Krylov subspaces of the type K^m,mi+1(A)=span{A^-m+1v,…,A^-1v,v,Av,…,A^miv}, m=1,2,3,…, with i a positive integer, and describes applications to the evaluation of matrix functions and the computation of rational Gauss quadrature rules.     

Linearized Krylov subspace Bregman iteration with nonnegativity constraint

Numerical Algorithms - Bregman-type iterative methods have received considerable attention in recent years due to their ease of implementation and the high quality of the computed solutions they...     

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.     

Multisplitting for regularized least squares with Krylov subspace recycling

The method of multisplitting (MS), implemented as a restricted additive Schwarz type algorithm, is extended for the solution of regularized least squares problems. The presented non‐stationary version of the algorithm uses dynamic updating of the weights applied to the subdomains in reconstituting the global solution. Standard convergence results follow from extensive prior literature on linear MS schemes. Additional convergence results on nonstationary iterations yield convergence conditions for the presented nonstationary MS algorithm. The global iteration uses repeated solves of local problems with changing right hand sides but a fixed system matrix. These problems are solved inexactly using a conjugate gradient least squares algorithm which provides a seed Krylov subspace. Recycling of the seed system Krylov subspace to obtain the solutions of subsequent nearby systems of equations improves the overall efficiency of the MS algorithm, and is apparently novel in this context. The obtained projected solution is not always of sufficient accuracy to satisfy a reasonable inner convergence condition on the local solution. Improvements to accuracy may be achieved by reseeding the solution space either every few steps, or when the successive right hand sides are sufficiently close as measured by a provided tolerance. Restarting and augmenting the solution space are also discussed. Any time a new space is generated it is used for subsequent steps. Numerical simulations validate the use of the recycling algorithm. These numerical experiments use the standard reconstruction of the two dimensional Shepp–Logan phantom, as well as a two dimensional problem from seismic tomography. Copyright © 2011 John Wiley & Sons, Ltd.     

Convergence analysis of the one-step iterative Krylov subspace methods

The paper suggests a new way of definition of the iteration parameter for the one-step Krylov subspace method, which is based on some geometrical extremal problem. An equivalent renorming of the underlying space speeds up the convergence rate.     

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.