Sketched and truncated polynomial Krylov methods: Evaluation of matrix functions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916341943894016 |
|---|---|
| author | Palitta, Davide Schweitzer, Marcel Simoncini, Valeria |
| author_facet | Palitta, Davide Schweitzer, Marcel Simoncini, Valeria |
| contents | Among randomized numerical linear algebra strategies, so-called sketching procedures are emerging as effective reduction means to accelerate the computation of Krylov subspace methods for, e.g., the solution of linear systems, eigenvalue computations, and the approximation of matrix functions. While there is plenty of experimental evidence showing that sketched Krylov solvers may dramatically improve performance over standard Krylov methods, many features of these schemes are still unexplored. We derive a new sketched Arnoldi-type relation that allows us to obtain several different new theoretical results. These lead to an improvement of our understanding of sketched Krylov methods, in particular by explaining why the frequently occurring sketched Ritz values far outside the spectral region of A do not negatively influence the convergence of sketched Krylov methods for f (A)b. Our findings also help to identify, among several possible equivalent formulations, the most suitable sketched approximations according to their numerical stability properties. These results are also employed to analyze the error of sketched Krylov methods in the approximation of the action of matrix functions, significantly contributing to the theory available in the current literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_06481 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sketched and truncated polynomial Krylov methods: Evaluation of matrix functions Palitta, Davide Schweitzer, Marcel Simoncini, Valeria Numerical Analysis 68W20, 65F25, 65F50, 65F60 Among randomized numerical linear algebra strategies, so-called sketching procedures are emerging as effective reduction means to accelerate the computation of Krylov subspace methods for, e.g., the solution of linear systems, eigenvalue computations, and the approximation of matrix functions. While there is plenty of experimental evidence showing that sketched Krylov solvers may dramatically improve performance over standard Krylov methods, many features of these schemes are still unexplored. We derive a new sketched Arnoldi-type relation that allows us to obtain several different new theoretical results. These lead to an improvement of our understanding of sketched Krylov methods, in particular by explaining why the frequently occurring sketched Ritz values far outside the spectral region of A do not negatively influence the convergence of sketched Krylov methods for f (A)b. Our findings also help to identify, among several possible equivalent formulations, the most suitable sketched approximations according to their numerical stability properties. These results are also employed to analyze the error of sketched Krylov methods in the approximation of the action of matrix functions, significantly contributing to the theory available in the current literature. |
| title | Sketched and truncated polynomial Krylov methods: Evaluation of matrix functions |
| topic | Numerical Analysis 68W20, 65F25, 65F50, 65F60 |
| url | https://arxiv.org/abs/2306.06481 |