Krylov subspaces and the analytic grade

Typical behaviour of the solution of a linear system of equations obtained iteratively by Krylov methods can be characterized by three stages. Initially the residual diminishes steadily; this is followed by stagnation and finally rapid convergence near the algebraic grade. This study examines this behaviour in terms of the concepts of approximately invariant subspace and what we have called the analytic grade of a Krylov sequence. It is shown how the small Ritz values play a vital role in the convergence and how this knowledge helps in the construction of an effective preconditioner. Copyright © 2004 John Wiley & Sons, Ltd.     

An augmented LSQR method

The LSQR iterative method for solving least-squares problems may require many iterations to determine an approximate solution with desired accuracy. This often depends on the fact that singular vector components of the solution associated with small singular values of the matrix require many iterations to be determined. Augmentation of Krylov subspaces with harmonic Ritz vectors often makes it possible to determine the singular vectors associated with small singular values with fewer iterations than without augmentation. This paper describes how Krylov subspaces generated by the LSQR iterative method can be conveniently augmented with harmonic Ritz vectors. Computed examples illustrate the competitiveness of the augmented LSQR method proposed.     

Generalized block Lanczos methods for large unsymmetric eigenproblems

Generalized block Lanczos methods for large unsymmetric eigenproblems are presented, which contain the block Arnoldi method, and the block Arnoldi algorithms are developed. The convergence of this class of methods is analyzed when the matrix A is diagonalizable. Upper bounds for the distances between normalized eigenvectors and a block Krylov subspace are derived, and a priori theoretical error bounds for Ritz elements are established. Compared with generalized Lanczos methods, which contain Arnoldi's method, the convergence analysis shows that the block versions have two advantages: First, they may be efficient for computing clustered eigenvalues; second, they are able to solve multiple eigenproblems. However, a deep analysis exposes that the approximate eigenvectors or Ritz vectors obtained by general orthogonal projection methods including generalized block methods may fail to converge theoretically for a general unsymmetric matrix A even if corresponding approximate eigenvalues or Ritz values do, since the convergence of Ritz vectors needs more sufficient conditions, which may be impossible to satisfy theoretically, than that of Ritz values does. The issues of how to restart and to solve multiple eigenproblems are addressed, and some numerical examples are reported to confirm the theoretical analysis. Received July 7, 1994 / Revised version received March 1, 1997     

Restarted block Lanczos bidiagonalization methods

The problem of computing a few of the largest or smallest singular values and associated singular vectors of a large matrix arises in many applications. This paper describes restarted block Lanczos bidiagonalization methods based on augmentation of Ritz vectors or harmonic Ritz vectors by block Krylov subspaces. Research supported in part by NSF grant DMS-0107858, NSF grant DMS-0311786, and an OBR Research Challenge Grant.     

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.     

Time integration of index 1 DAEs with Rosenbrock methods using Krylovsubspace techniques

The derivation of Rosenbrock‐Krylov methods for index 1 DAEs involves two well known techniques: a limit process which transforms a singular perturbed ODE to an index 1 DAE and the use of Krylov iterations instead of direct linear solvers for the stage equations. We show that our derived class of Rosenbrock‐Krylov schemes is independent of the order in which we apply these techniques. We also conclude that for convergence a rather accurate solution of the algebraic part is always needed.     

A-posteriori residual bounds for Arnoldi’s methods for nonsymmetric eigenvalue problems

Convergence of the implicitly restarted Arnoldi (IRA) method for nonsymmetric eigenvalue problems has often been studied by deriving bounds for the angle between a desired eigenvector and the Krylov projection subspace. Bounds for residual norms of approximate eigenvectors have been less studied and this paper derives a new a-posteriori residual bound for nonsymmetric matrices with simple eigenvalues. The residual vector is shown to be a linear combination of exact eigenvectors and a residual bound is obtained as the sum of the magnitudes of the coefficients of the eigenvectors. We numerically illustrate that the convergence of the residual norm to zero is governed by a scalar term, namely the last element of the wanted eigenvector of the projected matrix. Both cases of convergence and non-convergence are illustrated and this validates our theoretical results. We derive an analogous result for implicitly restarted refined Arnoldi (IRRA) and for this algorithm, we numerically illustrate that convergence is governed by two scalar terms appearing in the linear combination which drives the residual norm to zero. We provide a set of numerical results that validate the residual bounds for both variants of Arnoldi methods.     

计算大规模矩阵最大最小奇异值和奇异向量的两个精化Lanczos算法

1.引言 在科学工程计算中经常需要计算大规模矩阵的少数最大或最小的奇异值及其所对应的奇异子空间。例如图像处理中要计算矩阵端部奇异值之比作为图像的分辨率,诸如此类的问题还存在于最小二乘问题、控制理论、量子化学中等等。然而大多实际问题中的矩阵是大型稀疏矩阵,且需要的是矩阵的部分奇异对。如果计算A的完全奇异值分解(SVD),则运算量和存储量极大,甚至不可能。因此必须寻求其它有效可靠的算法。 假设A的SVD为     

Restarted FOM Augmented with Ritz Vectors for Shifted Linear Systems

The restarted FOM method presented by Simoncini[7]according to the natural collinearity of all residuals is an efficient method for solving shifted systems,which generates the same Krylov subspace when the shifts are handled simultaneously.However,restarting slows down the convergence.We present a practical method for solving the shifted systems by adding some Ritz vectors into the Krylov subspace to form an augmented Krylov subspace. Numerical experiments illustrate that the augmented FOM approach(restarted version)can converge more quickly than the restarted FOM method.     

Penalty-combined approaches to the Ritz-Galerkin and finite element methods for singularity problems of elliptic equations

Penlty coupling techniques on an interface boundary, artificial or material, are first presented for combining the Ritz–Galerkin and finite element methods. An optimal convergence rate first is proved in the Sobolev norms. Moreover, a significant coupling strategy, L + 1 = O(|ln h|), between these two methods are derived for the Laplace equation with singularities, where L + 1 is the total number of particular solutions used in the Ritz–Galerkin method, and h is the maximal boundary length of quasiuniform elements used in the linear finite element method. Numreical experiments have been carried out for solving the benchmark model: Motz's problem. Both theoretical analysis and numreical experiments clearly display the importance of penalty-combined methods is solving elliptic equations with singularities.     

Iterative methods for solvingAx=b,GMRES/FOM versus QMR/BiCG

We study the convergence of the GMRES/FOM and QMR/BiCG methods for solving nonsymmetric systems of equationsAx=b. We prove, in exact arithmetic, that any type of residual norm convergence obtained using BiCG can also be obtained using FOM but on a different system of equations. We consider practical comparisons of these procedures when they are applied to the same matrices. We use a unitary invariance shared by both methods, to construct test matrices where we can vary the nonnormality of the test matrix by variations in simplified eigenvector matrices. We used these test problems in two sets of numerical experiments. The first set of experiments was designed to study effects of increasing nonnormality on the convergence of GMRES and QMR. The second set of experiments was designed to track effects of the eigenvalue distribution on the convergence of QMR. In these tests the GMRES residual norms decreased significantly more rapidly than the QMR residual norms but without corresponding decreases in the error norms. Furthermore, as the nonnormality ofA was increased, the GMRES residual norms decreased more rapidly. This led to premature termination of the GMRES procedure on highly nonnormal problems. On the nonnormal test problems the QMR residual norms exhibited less sensitivity to changes in the nonnormality. The convergence of either type of procedure, as measured by the error norms, was delayed by the presence of large or small outliers and affected by the type of eigenvalues, real or complex, in the eigenvalue distribution ofA. For GMRES this effect can be seen only in the error norm plots.In honor of the 70th birthday of Ted RivlinThis work was supported by NSF grant GER-9450081.     

Stopping Criterion in Order Reduction of Large Scale Systems Using Krylov Subspace Methods

We show that order reduction by a two‐sided Krylov subspace method is equivalent to an approximate TBR in the sense of Galerkin type conditions. The Hankel Singular Values of the original system are thereby approximated by the Hankel singular values of the Krylov reduced model which are used as a stopping criterion to find a suitable order of the reduced model. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multistep matrix splitting iteration preconditioning for singular linear systems

Multistep matrix splitting iterations serve as preconditioning for Krylov subspace methods for solving singular linear systems. The preconditioner is applied to the generalized minimal residual (GMRES) method and the flexible GMRES (FGMRES) method. We present theoretical and practical justifications for using this approach. Numerical experiments show that the multistep generalized shifted splitting (GSS) and Hermitian and skew-Hermitian splitting (HSS) iteration preconditioning are more robust and efficient compared to standard preconditioners for some test problems of large sparse singular linear systems.     

Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices

We present a probabilistic analysis of two Krylov subspace methods for solving linear systems. We prove a central limit theorem for norms of the residual vectors that are produced by the conjugate gradient and MINRES algorithms when applied to a wide class of sample covariance matrices satisfying some standard moment conditions. The proof involves establishing a four-moment theorem for the so-called spectral measure, implying, in particular, universality for the matrix produced by the Lanczos iteration. The central limit theorem then implies an almost-deterministic iteration count for the iterative methods in question. © 2022 Wiley Periodicals LLC.     

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.     

A Krylov–Schur approach to the truncated SVD

Computing a small number of singular values is required in many practical applications and it is therefore desirable to have efficient and robust methods that can generate such truncated singular value decompositions. A method based on the Lanczos bidiagonalization and the Krylov–Schur method is presented. It is shown that deflation strategies can be easily implemented in this method and possible stopping criteria are discussed. Numerical experiments show the efficiency of the Krylov–Schur method.     

Numerical experiments on a flexible variant of GMRES-DR

The Flexible GMRES (FGMRES [1]) and the GMRES with deflated restarting (GMRES-DR [2]) methods are two algorithms derived from GMRES [3], that are considered as powerful when solving large non hermitian systems of linear equations. GMRES-DR is a variant of GMRES with an improved restarting technique that maintains in the Krylov subspace harmonic Ritz vector from the previous restart. In situations where the convergence of restarted GMRES is slow and where the matrix has few eigenvalues close to the origin, this technique has proved very efficient. The new method that we propose is the Flexible GMRES with deflated restarting (FGMRES-DR [6]), which combines the two above mentioned algorithms in order to yield better performance. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Arnoldi-Extrapolation algorithm for computing PageRank

The Arnoldi-type algorithm proposed by Golub and Greif [G. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT 46 (2006) 759-771] is a restarted Krylov subspace method for computing PageRank. However, this algorithm may not be efficient when the damping factor is high and the dimension of the search subspace is small. In this paper, we first develop an extrapolation method based on Ritz values. We then consider how to periodically knit this extrapolation method together with the Arnoldi-type algorithm. The resulting algorithm is the Arnoldi-Extrapolation algorithm. The convergence of the new algorithm is analyzed. Numerical experiments demonstrate the numerical behavior of this algorithm.     

IMPROVING EIGENVECTORS IN ARNOLDI''''S METHOD

1. IntroductionArnoldi's method [1, 12] is used for computing.,a few selected eigenpairs of largeunsymmetric matrices. It hajs been investigated since the 1980s; see, e-g., [3--15].It is well known that the m--step Arnoldi processt as described in detail in Section 2,generates an orthonormal basis {yi}7=1 of the Krylov subspace Km(vi, A) spanned byvil Avi,... 5 Am--'v,. Here yi is an initial unit norm vector. The projected matrix ofA onto Km(vi, A) is represented by an m x m upper Hessenb…