A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity

A restarted Arnoldi algorithm is given that computes eigenvalues and eigenvectors. It is related to implicitly restarted Arnoldi, but has a simpler restarting approach. Harmonic and regular Rayleigh-Ritz versions are possible.For multiple eigenvalues, an approach is proposed that first computes eigenvalues with the new harmonic restarted Arnoldi algorithm, then uses random restarts to determine multiplicity. This avoids the need for a block method or for relying on roundoff error to produce the multiple copies.     

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.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

An Arnoldi Method for Nonlinear Eigenvalue Problems

For the nonlinear eigenvalue problem T()x=0 we propose an iterative projection method for computing a few eigenvalues close to a given parameter. The current search space is expanded by a generalization of the shift-and-invert Arnoldi method. The resulting projected eigenproblems of small dimension are solved by inverse iteration. The method is applied to a rational eigenvalue problem governing damped vibrations of a structure.     

The Use of Refined Harmonic Shifts in the Implicitly Restarted Refined Harmonic Arnoldi Method

This paper proposes a new shift scheme, called refined harmonic shifts, for use in the implicitly restarted refined harmonic Arnoldi method. Numerical experiments show that the implicitly restarted refined harmonic Arnoldi algorithm with refined harmonic shifts is better than the implicitly restarted harmonic Arnoldi algorithm with Morgan's harmonic shifts and the refined harmonic shifts are as efficient as Jia's refined shifts.     

Extracting partial canonical structure for large scale eigenvalue problems

We present methods for computing a nearby partial Jordan-Schur form of a given matrix and a nearby partial Weierstrass-Schur form of a matrix pencil. The focus is on the use and the interplay of the algorithmic building blocks – the implicitly restarted Arnoldi method with prescribed restarts for computing an invariant subspace associated with the dominant eigenvalue, the clustering method for grouping computed eigenvalues into numerically multiple eigenvalues and the staircase algorithm for computing the structure revealing form of the projected problem. For matrix pencils, we present generalizations of these methods. We introduce a new and more accurate clustering heuristic for both matrices and matrix pencils. Particular emphasis is placed on reliability of the partial Jordan-Schur and Weierstrass-Schur methods with respect to the choice of deflation parameters connecting the steps of the algorithm such that the errors are controlled. Finally, successful results from computational experiments conducted on problems with known canonical structure and varying ill-conditioning are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

The implicit application of a rational filter in the RKS method

The implicitly restarted Arnoldi method implicitly applies a polynomial filter to the Arnoldi vectors by use of orthogonal transformations. In this paper, an implicit filtering by rational functions is proposed for the rational Krylov method. This filtering is performed in an efficient way. Two applications are considered. The first one is the filtering of unwanted eigenvalues using exact shifts. This approach is related to the use of exact shifts in the implicitly restarted Arnoldi method. Second, eigenvalue problems can have an infinite eigenvalue without physical relevance. This infinite eigenvalue can corrupt the eigensolution. An implicit filtering is proposed for avoiding such corruptions. The work of Gorik De Samblanx and Adhemar Bultheel was supported by the National Fund for Scientific Research (NFWO), project Lanczos, grant #2.0042.93 and by the Human Capital and Mobility project ROLLS of the European Community under contract ERBCHRXCT930416. The research by Karl Meerbergen was supported by the Belgian programme on Interuniversity Poles of Attraction (IUAP 17), initiated by the Belgian State—Prime Minister's Service—Federal Office for Scientific, Technical and Cultural Affairs and the project Iterative Methods in Scientific Computing, contract number HCM network CHRCCT93-0420, coordinated by CERFACS, Toulouse, France.     

隐式重启精化全局Lanczos方法

The numerical methods for solving large symmetric eigenvalue problems are considered in this paper.Based on the global Lanczos process,a global Lanczos method for solving large symmetric eigenvalue problems is presented.In order to accelerate the convergence of the F-Ritz vectors,the refined global Lanczos method is developed.Combining the implicitly restarted strategy with the deflation technique,an implicitly restarted and refined global Lanczos method for computing some eigenvalues of large symmetric matrices is proposed.Numerical results show that the proposed methods are efficient.     

A block Arnoldi-type contour integral spectral projection method for solving generalized eigenvalue problems

For generalized eigenvalue problems, we consider computing all eigenvalues located in a certain region and their corresponding eigenvectors. Recently, contour integral spectral projection methods have been proposed for solving such problems. In this study, from the analysis of the relationship between the contour integral spectral projection and the Krylov subspace, we conclude that the Rayleigh–Ritz-type of the contour integral spectral projection method is mathematically equivalent to the Arnoldi method with the projected vectors obtained from the contour integration. By this Arnoldi-based interpretation, we then propose a block Arnoldi-type contour integral spectral projection method for solving the eigenvalue problem.     

Rational Krylov for Nonlinear Eigenproblems,an Iterative Projection Method

In recent papers Ruhe suggested a rational Krylov method for nonlinear eigenproblems knitting together a secant method for linearizing the nonlinear problem and the Krylov method for the linearized problem. In this note we point out that the method can be understood as an iterative projection method. Similarly to the Arnoldi method the search space is expanded by the direction from residual inverse iteration. Numerical methods demonstrate that the rational Krylov method can be accelerated considerably by replacing an inner iteration by an explicit solver of projected problems.     

Using implicitly filtered RKS for generalised eigenvalue problems

The rational Krylov sequence (RKS) method can be seen as a generalisation of Arnoldi's method. It projects a matrix pencil onto a smaller subspace; this projection results in a small upper Hessenberg pencil. As for the Arnoldi method, RKS can be restarted implicitly, using the QR decomposition of a Hessenberg matrix. This restart comes with a projection of the subspace using a rational function. In this paper, it is shown how the restart can be worked out in practice. In a second part, it is shown when the filtering of the subspace basis can fail and how this failure can be handled by deflating a converged eigenvector from the subspace, using a Schur-decomposition.     

A new framework for implicit restarting of the Krylov–Schur algorithm

This paper introduces a new framework for implicit restarting of the Krylov–Schur algorithm. It is shown that restarting with arbitrary polynomial filter is possible by reassigning some of the eigenvalues of the Rayleigh quotient through a rank‐one correction, implemented using only the elementary transformations (translation and similarity) of the Krylov decomposition. This framework includes the implicitly restarted Arnoldi (IRA) algorithm and the Krylov–Schur algorithm with implicit harmonic restart as special cases. Further, it reveals that the IRA algorithm can be turned into an eigenvalue assignment method. Copyright © 2014 John Wiley & Sons, Ltd.     

Linear system solution by null‐space approximation and projection (SNAP)

Solutions of large sparse linear systems of equations are usually obtained iteratively by constructing a smaller dimensional subspace such as a Krylov subspace. The convergence of these methods is sometimes hampered by the presence of small eigenvalues, in which case, some form of deflation can help improve convergence. The method presented in this paper enables the solution to be approximated by focusing the attention directly on the ‘small’ eigenspace (‘singular vector’ space). It is based on embedding the solution of the linear system within the eigenvalue problem (singular value problem) in order to facilitate the direct use of methods such as implicitly restarted Arnoldi or Jacobi–Davidson for the linear system solution. The proposed method, called ‘solution by null‐space approximation and projection’ (SNAP), differs from other similar approaches in that it converts the non‐homogeneous system into a homogeneous one by constructing an annihilator of the right‐hand side. The solution then lies in the null space of the resulting matrix. We examine the construction of a sequence of approximate null spaces using a Jacobi–Davidson style singular value decomposition method, called restarted SNAP‐JD, from which an approximate solution can be obtained. Relevant theory is discussed and the method is illustrated by numerical examples where SNAP is compared with both GMRES and GMRES‐IR. Copyright © 2006 John Wiley & Sons, Ltd.     

A periodic Krylov-Schur algorithm for large matrix products

Stewart's recently introduced Krylov-Schur algorithm is a modification of the implicitly restarted Arnoldi algorithm which employs reordered Schur decompositions to perform restarts and deflations in a numerically reliable manner. This paper describes a variant of the Krylov-Schur algorithm suitable for addressing eigenvalue problems associated with products of large and sparse matrices. It performs restarts and deflations via reordered periodic Schur decompositions and, by taking the product structure into account, it is capable of achieving qualitatively better approximations to eigenvalues of small magnitude. Supported by DFG Research Center Matheon, Mathematics for key technologies, in Berlin.     

An Implicitly Restarted Block Arnoldi Method in a Vector-Wise Fashion

In this paper, we develop an implicitly restarted block Arnoldi algorithm in a vector-wise fashion. The vector-wise construction greatly simplifies both the detection of necessary deflation and the actual deflation itself, so it is preferable to the block-wise construction. The numerical experiment shows that our algorithm is effective.     

计算部分奇异值分解的隐式重新启动的双对角化Lanczos方法和精化的双对角化Lanczos方法

The singular value decomposition problem is mathematically equivalent to the eigenproblem of an argumented matrix. Golub et al. give a bidiagonalization Lanczos method for computing a number of largest or smallest singular values and corresponding singular vertors, but the method may encounter some convergence problems. In this paper we analyse the convergence of the method and show why it may fail to converge. To correct this possible nonconvergence, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique to it, and we then present an implicitly restarted bidiagonalization Lanczos algorithm(IRBL) and an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). A new implicitly restarting scheme and a reliable and efficient algorithm for computing refined shifts are developed for this special structure eigenproblem.Theoretical analysis and numerical experiments show that IRRBL performs much better than IRBL.     

Nested Lanczos: implicitly restarting an unsymmetric Lanczos algorithm

In this text, we present a generalization of the idea of the Implicitly Restarted Arnoldi method to the unsymmetric Lanczos algorithm, using the two-sided Gram-Schmidt process or using a full Lanczos tridiagonalization. The resulting implicitly restarted Lanczos method is called Nested Lanczos. Nested Lanczos can be combined with an implicit filter. It can also be used in case of breakdown and offers an alternative for look-ahead. This revised version was published online in August 2006 with corrections to the Cover Date.     

Increasing efficiency of inverse iteration

Inverse iteration is simple but not very efficient method for computing few eigenvalues with minimal absolute values and corresponding eigenvectors of a symmetric matrix. The idea is to increase its efficiency by technique similar to multigrid methods used for solving linear systems. This approach is not new, but until now multigrid was mostly used for solving linear system which appear in Rayleigh quotient iteration, inverse iteration and related iterative methods. Instead of choosing appropriate coordinates (grids), our algorithm performs inverse iteration on a sequence of subspaces with decreasing dimensions (multispace). Block Lanczos method is used for the selection of a smaller subspace. This will produce a banded matrix, which makes inverse iteration even faster in the smaller dimensions.      

Arnoldi and Jacobi-Davidson methods for generalized eigenvalue problems

In many physical situations, a few specific eigenvalues of a large sparse generalized eigenvalue problem are needed. If exact linear solves with are available, implicitly restarted Arnoldi with purification is a common approach for problems where is positive semidefinite. In this paper, a new approach based on implicitly restarted Arnoldi will be presented that avoids most of the problems due to the singularity of . Secondly, if exact solves are not available, Jacobi-Davidson QZ will be presented as a robust method to compute a few specific eigenvalues. Results are illustrated by numerical experiments.

     

A PROCESS FOR SOLVING A FEW EXTREME EIGENPAIRS OF LARGE SPARSE POSITIVE DEFINITE GENERALIZED EIGENVALUE PROBLEM

1. IntroductionWe are concerned in this work with finding a few extreme eigenvalues and theircorresponding eigenvectors of a generalized large scale eigenvalue problem in which thematrices are sparse and symmetric positive definite.Although finding a few extreme eigenpairs is of interest both in theory and practice,there are only few usable and efficient methods up to now. Reinsch and Baner ([12]),suggested a oR algorithm with Newton shift for the standard eigenproblem which included an ingen…