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.     

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.     

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.     

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.     

A reflection on the implicitly restarted Arnoldi method for computing eigenvalues near a vertical line

In this article, we will study the link between a method for computing eigenvalues closest to the imaginary axis and the implicitly restarted Arnoldi method. The extension to computing eigenvalues closest to a vertical line is straightforward, by incorporating a shift. Without loss of generality we will restrict ourselves here to computing eigenvalues closest to the imaginary axis.In a recent publication, Meerbergen and Spence discussed a new approach for detecting purely imaginary eigenvalues corresponding to Hopf bifurcations, which is of interest for the stability of dynamical systems. The novel method is based on inverse iteration (inverse power method) applied on a Lyapunov-like eigenvalue problem. To reduce the computational overhead significantly a projection was added.This method can also be used for computing eigenvalues of a matrix pencil near a vertical line in the complex plane. We will prove in this paper that the combination of inverse iteration with the projection step is equivalent to Sorensen’s implicitly restarted Arnoldi method utilizing well-chosen shifts.     

The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: Complex shifts for real matrices

A new algorithm for the computation of eigenvalues of a nonsymmetric matrix pencil is described. It is a generalization of the shifted and inverted Lanczos (or Arnoldi) algorithm, in which several shifts are used in one run. It computes an orthogonal basis and a small Hessenberg pencil. The eigensolution of the Hessenberg pencil, gives Ritz approximations to the solution of the original pencil. It is shown how complex shifts can be used to compute a real block Hessenberg pencil to a real matrix pair.Two applicationx, one coming from an aircraft stability problem and the other from a hydrodynamic bifurcation, have been tested and results are reported.Dedicated to Carl-Erik Fröberg on the occasion of his 75th birthday.     

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.     

On Restarting the Arnoldi Method for Large Nonsymmetric Eigenvalue Problems

The Arnoldi method computes eigenvalues of large nonsymmetric matrices. Restarting is generally needed to reduce storage requirements and orthogonalization costs. However, restarting slows down the convergence and makes the choice of the new starting vector difficult if several eigenvalues are desired. We analyze several approaches to restarting and show why Sorensen's implicit QR approach is generally far superior to the others. Ritz vectors are combined in precisely the right way for an effective new starting vector. Also, a new method for restarting Arnoldi is presented. It is mathematically equivalent to the Sorensen approach but has additional uses.

     

A refined iterative algorithm based on the block arnoldi process for large unsymmetric eigenproblems

When the matrix in question is unsymmetric, the approximate eigenvectors or Ritz vectors obtained by orthogonal projection methods including Arnoldi's method and the block Arnoldi method cannot be guaranteed to converge in theory even if the corresponding approximate eigenvalues or Ritz values do. In order to circumvent this danger, a new strategy has been proposed by the author for Arnoldi's method. The strategy used is generalized to the block Arnoldi method in this paper. It discards Ritz vectors and instead computes refined approximate eigenvectors by small-sized singular-value decompositions. It is proved that the new strategy can guarantee the convergence of refined approximate eigenvectors if the corresponding Ritz values do. The resulting refined iterative algorithm is realized by the block Arnoldi process. Numerical experiments show that the refined algorithm is much more efficient than the iterative block Arnoldi algorithm.     

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

A modified harmonic block Arnoldi algorithm with adaptive shifts for large interior eigenproblems

The harmonic block Arnoldi method can be used to find interior eigenpairs of large matrices. Given a target point or shift τ$\tau$ to which the needed interior eigenvalues are close, the desired interior eigenpairs are the eigenvalues nearest τ$\tau$ and the associated eigenvectors. However, it has been shown that the harmonic Ritz vectors may converge erratically and even may fail to do so. To do a better job, a modified harmonic block Arnoldi method is coined that replaces the harmonic Ritz vectors by some modified harmonic Ritz vectors. The relationships between the modified harmonic block Arnoldi method and the original one are analyzed. Moreover, how to adaptively adjust shifts during iterations so as to improve convergence is also discussed. Numerical results on the efficiency of the new algorithm are reported.     

Extending the eigCG algorithm to nonsymmetric Lanczos for linear systems with multiple right‐hand sides

The technique that was used to build the eigCG algorithm for sparse symmetric linear systems is extended to the nonsymmetric case using the BiCG algorithm. We show that, similar to the symmetric case, we can build an algorithm that is capable of computing a few smallest magnitude eigenvalues and their corresponding left and right eigenvectors of a nonsymmetric matrix using only a small window of the BiCG residuals while simultaneously solving a linear system with that matrix. For a system with multiple right‐hand sides, we give an algorithm that computes incrementally more eigenvalues while solving the first few systems and then uses the computed eigenvectors to deflate BiCGStab for the remaining systems. Our experiments on various test problems, including Lattice QCD, show the remarkable ability of eigBiCG to compute spectral approximations with accuracy comparable with that of the unrestarted, nonsymmetric Lanczos. Furthermore, our incremental eigBiCG followed by appropriately restarted and deflated BiCGStab provides a competitive method for systems with multiple right‐hand sides. Copyright © 2013 John Wiley & Sons, Ltd.     

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     

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…     

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.     

A Power–Arnoldi algorithm for computing PageRank

The PageRank algorithm plays an important role in modern search engine technology. It involves using the classical power method to compute the principle eigenvector of the Google matrix representing the web link graph. However, when the largest eigenvalue is not well separated from the second one, the power method may perform poorly. This happens when the damping factor is sufficiently close to 1. Therefore, it is worth developing new techniques that are more sophisticated than the power method. The approach presented here, called Power–Arnoldi, is based on a periodic combination of the power method with the thick restarted Arnoldi algorithm. The justification for this new approach is presented. Numerical tests illustrate the efficiency and convergence behaviour of the new algorithm. Copyright © 2007 John Wiley & Sons, Ltd.     

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.     

Heavy Ball Flexible GMRES Method for Nonsymmetric Linear Systems

Flexible GMRES (FGMRES) is a variant of preconditioned GMRES, which changes preconditioners at every Arnoldi step. GMRES often has to be restarted in order to save storage and reduce orthogonalization cost in the Arnoldi process. Like restarted GMRES, FGMRES may also have to be restarted for the same reason. A major disadvantage of restarting is the loss of convergence speed. In this paper, we present a heavy ball flexible GMRES method, aiming to recoup some of the loss in convergence speed in the restarted flexible GMRES while keep the benefit of limiting memory usage and controlling orthogonalization cost. Numerical tests often demonstrate superior performance of the proposed heavy ball FGMRES to the restarted FGMRES.     

Augmented Block Householder Arnoldi Method

Computing the eigenvalues and eigenvectors of a large sparse nonsymmetric matrix arises in many applications and can be a very computationally challenging problem. In this paper we propose the Augmented Block Householder Arnoldi (ABHA) method that combines the advantages of a block routine with an augmented Krylov routine. A public domain MATLAB code ahbeigs has been developed and numerical experiments indicate that the code is competitive with other publicly available codes.