TRPL+K: Thick-Restart Preconditioned Lanczos+K Method for Large Symmetric Eigenvalue Problems
From MaRDI portal
Publication:4632005
DOI10.1137/17M1157568zbMATH Open1431.65047arXiv1711.10128OpenAlexW2964305349WikidataQ128085717 ScholiaQ128085717MaRDI QIDQ4632005FDOQ4632005
Author name not available (Why is that?)
Publication date: 25 April 2019
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: The Lanczos method is one of the standard approaches for computing a few eigenpairs of a large, sparse, symmetric matrix. It is typically used with restarting to avoid unbounded growth of memory and computational requirements. Thick-restart Lanczos is a popular restarted variant because of its simplicity and numerically robustness. However, convergence can be slow for highly clustered eigenvalues so more effective restarting techniques and the use of preconditioning is needed. In this paper, we present a thick-restart preconditioned Lanczos method, TRPL+K, that combines the power of locally optimal restarting (+K) and preconditioning techniques with the efficiency of the thick-restart Lanczos method. TRPL+K employs an inner-outer scheme where the inner loop applies Lanczos on a preconditioned operator while the outer loop augments the resulting Lanczos subspace with certain vectors from the previous restart cycle to obtain eigenvector approximations with which it thick restarts the outer subspace. We first identify the differences from various relevant methods in the literature. Then, based on an optimization perspective, we show an asymptotic global quasi-optimality of a simplified TRPL+K method compared to an unrestarted global optimal method. Finally, we present extensive experiments showing that TRPL+K either outperforms or matches other state-of-the-art eigenmethods in both matrix-vector multiplications and computational time.
Full work available at URL: https://arxiv.org/abs/1711.10128
Recommendations
- Thick-restart Lanczos method for large symmetric eigenvalue problems
- An implicit restarted Lanczos method for large symmetric eigenvalue problems
- Robust preconditioning of large, sparse, symmetric eigenvalue problems
- A thick-restart Lanczos type method for Hermitian \(J\)-symmetric eigenvalue problems
- Preconditioning the Lanczos Algorithm for Sparse Symmetric Eigenvalue Problems
- A scalable eigenvalue solver for symmetric tridiagonal matrices
- scientific article; zbMATH DE number 1507105
- Lanczos algorithms for large scale symmetric and nonsymmetric matrix eigenvalue problems
- Block Krylov-Schur method for large symmetric eigenvalue problems
- Exploiting the Laguerre iteration for solving the symmetric tridiagonal eigenproblem
Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)
Cites Work
- An Inverse Free Preconditioned Krylov Subspace Method for Symmetric Generalized Eigenvalue Problems
- Implicit Application of Polynomial Filters in a k-Step Arnoldi Method
- SYM-ILDL
- A Preconditioned Hybrid SVD Method for Accurately Computing Singular Triplets of Large Matrices
- PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations
- Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method
- Title not available (Why is that?)
- The Geometry of Algorithms with Orthogonality Constraints
- Augmented Implicitly Restarted Lanczos Bidiagonalization Methods
- Truncation Strategies for Optimal Krylov Subspace Methods
- Data mining. Concepts and techniques
- Numerical methods for large eigenvalue problems
- Nested Krylov methods based on GCR
- Thick-restart Lanczos method for large symmetric eigenvalue problems
- Deflated and Augmented Krylov Subspace Techniques
- A Jacobi--Davidson Iteration Method for Linear Eigenvalue Problems
- Title not available (Why is that?)
- Error Analysis of the Lanczos Algorithm for Tridiagonalizing a Symmetric Matrix
- On restarting the Arnoldi method for large nonsymmetric eigenvalue problems
- Computational Variants of the Lanczos Method for the Eigenproblem
- The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices
- Generalized Preconditioned Locally Harmonic Residual Method for Non-Hermitian Eigenproblems
- Spectral Schur complement techniques for symmetric eigenvalue problems
- An implicit restarted Lanczos method for large symmetric eigenvalue problems
- Limited memory block Krylov subspace optimization for computing dominant singular value decompositions
- Generalizations of Davidson’s Method for Computing Eigenvalues of Sparse Symmetric Matrices
- Computational methods for large eigenvalue problems
- A projected preconditioned conjugate gradient algorithm for computing many extreme eigenpairs of a Hermitian matrix
- Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) in Hypre and PETSc
- State-of-the-art eigensolvers for electronic structure calculations of large scale nano-systems
- The Davidson Method
- Dynamic Thick Restarting of the Davidson, and the Implicitly Restarted Arnoldi Methods
- Improved algorithms for the lowest few eigenvalues and associated eigenvectors of large matrices
- Restarting techniques for the (Jacobi-)Davidson symmetric eigenvalue method
- Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem
- Nearly Optimal Preconditioned Methods for Hermitian Eigenproblems under Limited Memory. Part I: Seeking One Eigenvalue
- Preconditioning the Lanczos Algorithm for Sparse Symmetric Eigenvalue Problems
- A Davidson program for finding a few selected extreme eigenpairs of a large, sparse, real, symmetric matrix
- Estimating the trace of the matrix inverse by interpolating from the diagonal of an approximate inverse
- A thick-restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems
- Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. I. Extreme eigenvalues
Cited In (5)
- Convergence rates of individual Ritz values in block preconditioned gradient-type eigensolvers
- Hybrid Iterative Refined Method for Computing a Few Extreme Eigenpairs of a Symmetric Matrix
- Hybrid Iterative Refined Method for Computing a Few Extreme Eigenpairs of a Symmetric Matrix
- Preconditioners for Krylov subspace methods: An overview
- A Chebyshev locally optimal block preconditioned conjugate gradient method for product and standard symmetric eigenvalue problems
Uses Software
This page was built for publication: TRPL+K: Thick-Restart Preconditioned Lanczos+K Method for Large Symmetric Eigenvalue Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632005)
