Gradient-type subspace iteration methods for the symmetric eigenvalue problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910443477401600 |
|---|---|
| author | Alimisis, Foivos Saad, Yousef Vandereycken, Bart |
| author_facet | Alimisis, Foivos Saad, Yousef Vandereycken, Bart |
| contents | This paper explores variants of the subspace iteration algorithm for computing approximate invariant subspaces. The standard subspace iteration approach is revisited and new variants that exploit gradient-type techniques combined with a Grassmann manifold viewpoint are developed. A gradient method as well as a nonlinear conjugate gradient technique are described. Convergence of the gradient-based algorithm is analyzed and a few numerical experiments are reported, indicating that the proposed algorithms are sometimes superior to standard algorithms. This includes the Chebyshev-based subspace iteration and the locally optimal block conjugate gradient method, when compared in terms of number of matrix vector products and computational time, resp. The new methods, on the other hand, do not require estimating optimal parameters. An important contribution of this paper to achieve this good performance is the accurate and efficient implementation of an exact line search. In addition, new convergence proofs are presented for the non-accelerated gradient method that includes a locally exponential convergence if started in a $\mathcal{O(\sqrtδ)}$ neighbourhood of the dominant subspace with spectral gap $δ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_10379 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Gradient-type subspace iteration methods for the symmetric eigenvalue problem Alimisis, Foivos Saad, Yousef Vandereycken, Bart Numerical Analysis Optimization and Control 15A69, 15A18 This paper explores variants of the subspace iteration algorithm for computing approximate invariant subspaces. The standard subspace iteration approach is revisited and new variants that exploit gradient-type techniques combined with a Grassmann manifold viewpoint are developed. A gradient method as well as a nonlinear conjugate gradient technique are described. Convergence of the gradient-based algorithm is analyzed and a few numerical experiments are reported, indicating that the proposed algorithms are sometimes superior to standard algorithms. This includes the Chebyshev-based subspace iteration and the locally optimal block conjugate gradient method, when compared in terms of number of matrix vector products and computational time, resp. The new methods, on the other hand, do not require estimating optimal parameters. An important contribution of this paper to achieve this good performance is the accurate and efficient implementation of an exact line search. In addition, new convergence proofs are presented for the non-accelerated gradient method that includes a locally exponential convergence if started in a $\mathcal{O(\sqrtδ)}$ neighbourhood of the dominant subspace with spectral gap $δ$. |
| title | Gradient-type subspace iteration methods for the symmetric eigenvalue problem |
| topic | Numerical Analysis Optimization and Control 15A69, 15A18 |
| url | https://arxiv.org/abs/2306.10379 |