196 CHAPTER 10. RESTARTING ARNOLDI AND LANCZOS ALGORITHMS

Keeping the first set of Ritz vectors and purging the rest yields

AY1 − Y1T11 = βk+1qk+1s1.

In the thick-restart Lanczos procedure we have found an eigenpair as soon as βk+1|sik| is su ciently small. The determination of a converged subspace with the general Krylov– Schur procedure is not so easy. However, if we manage to bring s1 into the form

i.e.,

AY1′ = Y1′T11′

In most cases s′1 consists of a single small element or of two small elements in the case of a complex-conjugate eigenpair of a real nonsymmetric matrix [9]. These small elements are then declared zero and the columns in Y1′ are locked, i.e., they are not altered anymore in the future computations. Orthogonality against them has to be enforced in the continuation of the eigenvalue computation though.

10.9The rational Krylov space method

After having computed a number of eigenvalue–eigen/Schurvector pairs in the neighborhood of some shift σ1 with the shift-invert Lanczos, Arnoldi, or Krylov–Schur algorithm it may be advisable to restart with a changed shift σ2. This is in fact possible without discarding the available Krylov space [6]. In this section we consider the generalized eigenvalue problem Ax = λBx.

The rational Krylov space method starts out as a shift-invert Arnoldi iteration with shift σ1 and starting vector v1. It computes an orthonormal basis Vj using the basic recurrence,

We want to derive a Krylov–Schur relation for a new shift σ2 6= σ1 from (10.23) for the same space R(Yj+1) without accessing the matrices A or B. The tricky thing is to avoid discard all the information gathered in the basis Yj+1 that was computed with the old shift σ1. This is indeed possible if we replace the basis Yj+1 with a new basis Wj+1, which spans the same subspace as Yj+1 but can be interpreted as the orthonormal basis of a Krylov–Schur relation with the new shift σ2.

We rewrite the relation (10.23) as

To construct a Krylov–Schur relation we must get rid of the last non-zero row of the matrix in braces in (10.24). To that end we use the QR factorization

This equation can easily been transformed into an Arnoldi or Krylov–Schur relation.

All these transformations can be executed without performing any operations on the large sparse matrices A and B.

In a practical implementation, the mentioned procedure is combined with locking, purging, and implicit restart. First run shifted and inverted Arnoldi with the first shift σ1. When an appropriate number of eigenvalues around σ1 have converged, lock these converged eigenvalues and purge those that are altogether outside the interesting region, leaving an Arnoldi (10.22) or Krylov–Schur recursion (10.22) for the remaining vectors. Then introduce the new shift σ2 and perform the steps above to get a new basis Wj+1 that replaces Vj+1. Start at the new shift by operating on the last vector of this new basis

r := (A − σ2B)−1Bwj+1

and get the next basis vector wj+2 in the Arnoldi recurrence with the new shift σ2. Continue until we get convergence for a set of eigenvalues around σ2, and repeat the same procedure with new shifts until either all interesting eigenvalues have converged or all the shifts in the prescribed frequency range have been used.

Bibliography

[1]˚A. BJORCK¨ , Numerics of Gram–Schmidt orthogonalization, Linear Algebra Appl., 197/198 (1994), pp. 297–316.

[2]D. CALVETTI, L. REICHEL, AND D. C. SORENSEN, An implicitely restarted Lanczos method for large symmetric eigenvalue problems, Electron. Trans. Numer. Anal., 2 (1994), pp. 1–21.

[3]M. GENSEBERGER AND G. L. G. SLEIJPEN, Alternative correction equations in the Jacobi–Davidson method, Numer. Linear Algebra Appl., 6 (1999), pp. 235–253.

198CHAPTER 10. RESTARTING ARNOLDI AND LANCZOS ALGORITHMS

[4]R. B. LEHOUCQ, D. C. SORENSEN, AND C. YANG, ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems by Implicitely Restarted Arnoldi Methods, SIAM, Philadelphia, PA, 1998. (The software and this manual are available at URL http: //www.caam.rice.edu/software/ARPACK/).

[5]The Matrix Market. A repository of test data for use in comparative studies of algorithms for numerical linear algebra. Available at URL http://math.nist.gov/ MatrixMarket/.

[6]A. RUHE, Rational Krylov subspace method, in Templates for the solution of Algebraic Eigenvalue Problems: A Practical Guide, Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., SIAM, Philadelphia, PA, 2000, pp. 246–249.

[7]D. C. SORENSEN, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 357–385.

[8], Implicitly restarted Arnoldi/Lanczos methods for large scale eigenvalue calculations, in Parallel Numerical Algorithms, D. E. Keyes, A. Sameh, and V. Venkatakrishnan, eds., Kluwer, Dordrecht, 1997, pp. 119–165. (ICASE/LaRC Interdisciplinary Series in Science and Engineering, 4).

[9]G. W. STEWART, A Krylov–Schur algorithm for large eigenproblems, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 601–614.

[10], Matrix Algorithms II: Eigensystems, SIAM, Philadelphia, PA, 2001.

[11]K. WU AND H. D. SIMON, Thick-restart Lanczos method for large symmetric eigenvalue problems, SIAM J. Matrix Anal. Appl., 22 (2000), pp. 602–616.