All Title Author
Keywords Abstract

Publish in OALib Journal
ISSN: 2333-9721
APC: Only $99

ViewsDownloads

Relative Articles

More...

A Compact Heart Iteration for Large Eigenvalues Problems

DOI: 10.4236/alamt.2022.121002, PP. 24-38

Keywords: Large Sparse Matrices, Restarted Krylov Methods, Exterior Eigenvalues, Symmetric Matrices, Monotonicity, Starting Vectors

Full-Text   Cite this paper   Add to My Lib

Abstract:

In this paper, we present a compact version of the Heart iteration. One that requires less matrix-vector products per iteration and attains faster convergence. The Heart iteration is a new type of Restarted Krylov methods for calculating peripheral eigenvalues of symmetric matrices. The new framework avoids the Lanczos tridiagonalization process and the use of implicit restarts. This simplifies the restarting mechanism and allows the introduction of several modifications. Convergence is assured by a monotonicity property that pushes the computed Ritz values toward their limits. Numerical experiments illustrate the usefulness of the proposed approach.

References

[1]  Baglama, J., Calvetti, D. and Reichel, L. (2003) IRBL: An Implicitly Restarted Block Lanczos Method for Large-Scale Hermitian Eigen Problems. SIAM Journal on Scientific Computing, 24, 1650-1677.
https://doi.org/10.1137/S1064827501397949
[2]  Bai, A., Demmel, J., Dongarra, J., Ruhe, A. and van der Vorst, H. (1999) Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Society for Industrial and Applied Mathematics, Philadelphia.
https://doi.org/10.1137/1.9780898719581
[3]  Calvetti, D., Reichel, L. and Sorenson, D.C. (1994) An Implicitly Restarted Lanczos Method for Large Symmetric Eigenvalue Problems. Electronic Transactions on Numerical Analysis, 2, 1-21.
[4]  Dax, A. (2017) The Numerical Rank of Krylov Matrices. Linear Algebra and Its Applications, 528, 185-205.
https://doi.org/10.1016/j.laa.2016.07.022
[5]  Dax, A. (2017) A New Type of Restarted Krylov Methods. Advances in Linear Algebra & Matrix Theory, 7, 18-28.
https://doi.org/10.4236/alamt.2017.71003
[6]  Dax, A. (2019) A Restarted Krylov Method with Inexact Inversions. Numerical Linear Algebra with Applications, 26, Article No. e2213.
https://doi.org/10.1002/nla.2213
[7]  Dax, A. (2019) Computing the Smallest Singular Triplets of a Large Matrix. Results in Applied Mathematic, 3, Article ID: 100006.
https://doi.org/10.1016/j.rinam.2019.100006
[8]  Dax, A. (2019) A Cross-Product Approach for Low-Rank Approximations of Large Matrices. Journal of Computational and Applied Mathematics, 369, Article ID: 112576.
https://doi.org/10.1016/j.cam.2019.112576
[9]  Demmel, J.W. (1997) Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia.
https://doi.org/10.1137/1.9781611971446
[10]  Golub, G.H. and Van Loan, C.F. (2013) Matrix Computations. 4th Edition, Johns Hopkins University Press, Baltimore.
[11]  Horn, R.A. and Johnson, C.R. (1985) Matrix Analysis. Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511810817
[12]  Larsen, R.M. (2001) Combining Implicit Restarts and Partial Reorthogonalization in Lanczos Bidiagonalization. Technical Report, Stanford University.
[13]  Li, R., Xi, Y., Vecharynski, E., Yang, C. and Saad, Y. (2016) A Thick-Restart Lanczos Algorithm with Polynomial Filtering for Hermitian Eigenvalue Problems. SIAM Journal on Scientific Computing, 38, A2512-A2534.
https://doi.org/10.1137/15M1054493
[14]  Morgan, R.B. (1996) On Restarting the Arnoldi Method for Large Non-Symmetric Eigenvalues Problems. Mathematics of Computation, 65, 1213-1230.
https://doi.org/10.1090/S0025-5718-96-00745-4
[15]  Parlett, B.N. (1980) The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs.
[16]  Saad, Y. (2011) Numerical Methods for Large Eigenvalue Problems. Revised Edition, Society for Industrial and Applied Mathematics, Philadelphia.
https://doi.org/10.1137/1.9781611970739
[17]  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.
https://doi.org/10.1137/0613025
[18]  Stewart, G.W. (2001) Matrix Algorithms, Vol. II: Eigensystems. SIAM, Philadelphia.
https://doi.org/10.1137/1.9780898718058
[19]  Trefethen, L.N. and Bau III, D. (1997) Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia.
[20]  Watkins, D.S. (2007) The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. Society for Industrial and Applied Mathematics, Philadelphia.
https://doi.org/10.1137/1.9780898717808
[21]  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.
https://doi.org/10.1137/S0895479898334605
[22]  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, 47, Article No. 27.
https://doi.org/10.1145/1824801.1824805
[23]  Zhang, F. (1999) Matrix Theory: Basic Results and Techniques. Springer-Verlag, New York.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133