In this
paper we present a new subspace iteration for calculating eigenvalues of symmetric
matrices. The method is designed to compute a cluster of k exterior eigenvalues. For example, k eigenvalues with the largest absolute values, the k algebraically largest eigenvalues, or
the k algebraically smallest
eigenvalues. The new iteration applies a Restarted Krylov method to collect
information on the desired cluster. It is shown that the estimated eigenvalues
proceed monotonically toward their limits. Another innovation regards the
choice of starting points for the Krylov subspaces, which leads to fast rate of
convergence. Numerical experiments illustrate the viability of the proposed
ideas.
References
[1]
Bai, Z., Demmel, J., Dongarra, J., Ruhe, A. and van der Vorst, H. (1999) Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM, Philadelphia.
[2]
Bauer, F.L. (1957) Das Verfahren der Treppeniteration und verwandte Verfahren zur Losung algebraischers Eigenwertprobleme. Zeitschrift für angewandte Mathematik und Physik ZAMP, 8, 214-235. http://dx.doi.org/10.1007/BF01600502
[3]
Dax, A. Restarted Krylov Methods for Calculating Exterior Eigenvalues of Large Matrices. Tech. Rep., Hydrological Service of Israel, in Preparation.
[4]
Demmel, J.W. (1997) Applied Numerical Linear Algebra. SIAM, Philadelphia. http://dx.doi.org/10.1137/1.9781611971446
[5]
Golub, G.H. and Van Loan, C.F. (1983) Matrix Computations. Johns Hopkins University Press, Baltimore.
[6]
Horn, R.A. and Johnson, C.R. (1985) Matrix Analysis. Cambridge University Press, Cambridge. http://dx.doi.org/10.1017/CBO9780511810817
[7]
Parlett, B.N. (1980) The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs.
[8]
Reinsch, C.H. (1971) Simultaneous Iteration Method for Symmetric Matrices. In: Wilkinson, J.H. and Reinsch, C.H., Eds., Handbook for Automatic Computation (Linear Algebra), Springer-Verlag, New York, 284-302.
[9]
Rutishauer, H. (1969) Computational Aspects of F. L. Bauer’s Simultaneous Iteration Method. Numerische Mathematik, 13, 4-13. http://dx.doi.org/10.1007/BF02165269
[10]
Rutishauser, H. (1970) Simultaneous Iteration Method for Symmetric Matrices. Numerische Mathematik, 16, 205-223. http://dx.doi.org/10.1007/BF02219773
[11]
Sorensen, D.C. (1992) Implicit Application of Polynomial Filters in a k-Step Arnoldi Method. SIAM Journal on Matrix Analysis and Applications, 13, 357-385. http://dx.doi.org/10.1137/0613025
[12]
Stewart, G.W. (1969) Accelerating the Orthogonal Iteration for the Eigenvalues of a Hermitian Matrix. Numerische Mathematik, 13, 362-376. http://dx.doi.org/10.1007/BF02165413
Trefethen, L.N. and Bau III, D. (1997) Numerical Linear Algebra. SIAM, Philadelphia. http://dx.doi.org/10.1137/1.9780898719574
[15]
Watkins, D.S. (2007) The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. SIAM, Philadelphia. http://dx.doi.org/10.1137/1.9780898717808
[16]
Wilkinson, J.H. (1965) The Algebraic Eigenvalue Problem. Clarendon Press, Oxford.
[17]
Wu, K. and Simon, H. (2000) Thick-Restarted Lanczos Method for Large Symmetric Eigenvalue Problems. SIAM Journal on Matrix Analysis and Applications, 22, 602-616. http://dx.doi.org/10.1137/S0895479898334605
[18]
Yamazaki, I., Bai, Z., Simon, H., Wang, L. and Wu, K. (2010) Adaptive Projection Subspace Dimension for the Thick-Restart Lanczos Method. ACM Transactions on Mathematical Software, 37, 1-18. http://dx.doi.org/10.1145/1824801.1824805
[19]
Zhang, F. (1999) Matrix Theory: Basic Results and Techniques. Springer-Verlag, New York. http://dx.doi.org/10.1007/978-1-4757-5797-2
