A Subspace Iteration for Calculating a Cluster of Exterior Eigenvalues
Author(s)
Achiya Dax*
ABSTRACT
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.
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.
KEYWORDS
Exterior Eigenvalues, Symmetric Matrices, Subspace Iterations, Interlacing, Restarted Krylov Methods
Exterior Eigenvalues, Symmetric Matrices, Subspace Iterations, Interlacing, Restarted Krylov Methods
Cite this paper
Dax, A. (2015) A Subspace Iteration for Calculating a Cluster of Exterior Eigenvalues. Advances in Linear Algebra & Matrix Theory, 5, 76-89. doi: 10.4236/alamt.2015.53008.
Dax, A. (2015) A Subspace Iteration for Calculating a Cluster of Exterior Eigenvalues. Advances in Linear Algebra & Matrix Theory, 5, 76-89. doi: 10.4236/alamt.2015.53008.
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 [13] Stewart, G.W. (2001) Matrix Algorithms, Volume II: Eigensystems. SIAM, Philadelphia. [14] 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
[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 [13] Stewart, G.W. (2001) Matrix Algorithms, Volume II: Eigensystems. SIAM, Philadelphia. [14] 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