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

Approximate eigensolution of Laplacian matrices for locally modified graph products

Laplacian matrices and their spectrum are of great importance in algebraic graph theory. There exist efficient formulations for eigensolutions of the Laplacian matrices associated with a special class of graphs called product graphs. In this paper, the problem of determining a few approximate smallest eigenvalues and eigenvectors of large scale product graphs modified through the addition or deletion of some nodes and/or members, is investigated. The eigenproblem associated with a modified graph model is reduced using the set of master eigenvectors and linear approximated slave eigenvectors from the original model. Implicitly restarted Lanczos method is employed to obtain the required eigenpairs of the reduced problem. Examples of large scale models are included to demonstrate the efficiency of the proposed method compared to the direct application of the IRL method.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

Restarted generalized Krylov subspace methods for solving large-scale polynomial eigenvalue problems

In this paper, we introduce a generalized Krylov subspace based on a square matrix sequence {A _j } and a vector sequence {u _j }. Next we present a generalized Arnoldi procedure for generating an orthonormal basis of . By applying the projection and the refined technique, we derive a restarted generalized Arnoldi method and a restarted refined generalized Arnoldi method for solving a large-scale polynomial eigenvalue problem (PEP). These two methods are applied to solve the PEP directly. Hence they preserve essential structures and properties of the PEP. Furthermore, restarting reduces the storage requirements. Some theoretical results are presented. Numerical tests report the effectiveness of these methods. Yimin Wei is supported by the National Natural Science Foundation of China and Shanghai Education Committee.     

On the Krylov subspace methods based on tensor format for positive definite Sylvester tensor equations

This paper deals with studying some of well‐known iterative methods in their tensor forms to solve a Sylvester tensor equation. More precisely, the tensor form of the Arnoldi process and full orthogonalization method are derived by using a product between two tensors. Then tensor forms of the conjugate gradient and nested conjugate gradient algorithms are also presented. Rough estimation of the required number of operations for the tensor form of the Arnoldi process is obtained, which reveals the advantage of handling the algorithms based on tensor format over their classical forms in general. Some numerical experiments are examined, which confirm the feasibility and applicability of the proposed algorithms in practice. Copyright © 2016 John Wiley & Sons, Ltd.     

A rank‐exploiting infinite Arnoldi algorithm for nonlinear eigenvalue problems

We consider the nonlinear eigenvalue problem M(λ)x = 0, where M(λ) is a large parameter‐dependent matrix. In several applications, M(λ) has a structure where the higher‐order terms of its Taylor expansion have a particular low‐rank structure. We propose a new Arnoldi‐based algorithm that can exploit this structure. More precisely, the proposed algorithm is equivalent to Arnoldi's method applied to an operator whose reciprocal eigenvalues are solutions to the nonlinear eigenvalue problem. The iterates in the algorithm are functions represented in a particular structured vector‐valued polynomial basis similar to the construction in the infinite Arnoldi method [Jarlebring, Michiels, and Meerbergen, Numer. Math., 122 (2012), pp. 169–195]. In this paper, the low‐rank structure is exploited by applying an additional operator and by using a more compact representation of the functions. This reduces the computational cost associated with orthogonalization, as well as the required memory resources. The structure exploitation also provides a natural way in carrying out implicit restarting and locking without the need to impose structure in every restart. The efficiency and properties of the algorithm are illustrated with two large‐scale problems. Copyright © 2016 John Wiley & Sons, Ltd.     

Remarks on Non-Linear Spectral Perturbation

We are interested in some aspects of the perturbation effects in the spectrum of a real nonnormal matrix A under linear perturbations. We discuss some known results and we use them to justify some recent experimental observations. Moreover, we demonstrate that the qualitative behavior of the eigenvalues of A under linear perturbations may be predicted by inspecting the spectral radius of a related matrix. Then, we show how this information can be used to analyze the quality of the approximation of a projection method and to justify the presence of unexpected approximate eigenvalues.     

Implicitly restarted and deflated GMRES

We introduce a deflation method that takes advantage of the IRA method, by extracting a GMRES solution from the Krylov basis computed within the Arnoldi process of the IRA method itself. The deflation is well-suited because it is done with eigenvectors associated to the eigenvalues that are closest to zero, which are approximated by IRA very quickly. By a slight modification, we adapt it to the FOM algorithm, and then to GMRES enhanced by imposing constraints within the minimization condition. The use of IRA enables us to reduce the number of matrix-vector products, while keeping a low storage. This revised version was published online in June 2006 with corrections to the Cover Date.     

Arnoldi and Crank–Nicolson methods for integration in time of the transport equation

A comparison is made between the Arnoldi reduction method and the Crank–Nicolson method for the integration in time of the advection–diffusion equation. This equation is first discretized in space by the classic finite element (FE) approach, leading to an unsymmetric first‐order differential system, which is then solved by the aforementioned methods. Arnoldi reduces the native FE equations to a much smaller set to be efficiently integrated in the Arnoldi vector space by the Crank–Nicolson scheme, with the solution recovered back by a standard Rayleigh–Ritz procedure. Crank–Nicolson implements a time marching scheme directly on the original first‐order differential system. The computational performance of both methods is investigated in two‐ and three‐dimensional sample problems with a size up 30 000. The results show that in advection‐dominated problems less then 100 Arnoldi vectors generally suffice to give results with a 10⁻³–10⁻⁴ difference relative to the direct Crank–Nicolson solution. However, while the CPU time with the Crank–Nicolson starts from zero and increases linearly with the number of time steps used in the simulation, the Arnoldi requires a large initial cost to generate the Arnoldi vectors with subsequently much less expensive dynamics for the time integration. The break‐even point is problem‐dependent at a number of time steps which may be for some problems up to one order of magnitude larger than the number of Arnoldi vectors. A serious limitation of Arnoldi is the requirement of linearity and time independence of the flow field. It is concluded that Arnoldi can be cheaper than Crank–Nicolson in very few instances, i.e. when the solution is needed for a large number of time values, say several hundreds or even 1000, depending on the problem. Copyright © 2001 John Wiley & Sons, Ltd.