Randomly sparsified Richardson iteration: A dimension-independent sparse linear solver
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909592599920640 |
|---|---|
| author | Weare, Jonathan Webber, Robert J. |
| author_facet | Weare, Jonathan Webber, Robert J. |
| contents | Recently, a class of algorithms combining classical fixed point iterations with repeated random sparsification of approximate solution vectors has been successfully applied to eigenproblems with matrices as large as $10^{108} \times 10^{108}$. So far, a complete mathematical explanation for their success has proven elusive.
The family of methods has not yet been extended to the important case of linear system solves. In this paper we propose a new scheme based on repeated random sparsification that is capable of solving sparse linear systems in arbitrarily high dimensions. We provide a complete mathematical analysis of this new algorithm. Our analysis establishes a faster-than-Monte Carlo convergence rate and justifies use of the scheme even when the solution vector itself is too large to store. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_17270 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Randomly sparsified Richardson iteration: A dimension-independent sparse linear solver Weare, Jonathan Webber, Robert J. Numerical Analysis Recently, a class of algorithms combining classical fixed point iterations with repeated random sparsification of approximate solution vectors has been successfully applied to eigenproblems with matrices as large as $10^{108} \times 10^{108}$. So far, a complete mathematical explanation for their success has proven elusive. The family of methods has not yet been extended to the important case of linear system solves. In this paper we propose a new scheme based on repeated random sparsification that is capable of solving sparse linear systems in arbitrarily high dimensions. We provide a complete mathematical analysis of this new algorithm. Our analysis establishes a faster-than-Monte Carlo convergence rate and justifies use of the scheme even when the solution vector itself is too large to store. |
| title | Randomly sparsified Richardson iteration: A dimension-independent sparse linear solver |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2309.17270 |