Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913998327250944 |
|---|---|
| author | Epperly, Ethan N. Meier, Maike Nakatsukasa, Yuji |
| author_facet | Epperly, Ethan N. Meier, Maike Nakatsukasa, Yuji |
| contents | One of the greatest success stories of randomized algorithms for linear algebra has been the development of fast, randomized algorithms for highly overdetermined linear least-squares problems. However, none of the existing algorithms is backward stable, preventing them from being deployed as drop-in replacements for existing QR-based solvers. This paper introduces sketch-and-precondition with iterative refinement (SPIR) and FOSSILS, two provably backward stable randomized least-squares solvers. SPIR and FOSSILS combine iterative refinement with a preconditioned iterative method applied to the normal equations and converge at the same rate as existing randomized least-squares solvers. This work offers the promise of incorporating randomized least-squares solvers into existing software libraries while maintaining the same level of accuracy and stability as classical solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03468 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers Epperly, Ethan N. Meier, Maike Nakatsukasa, Yuji Numerical Analysis 65F10, 65F20, 65G50, 65K10, 68W20 One of the greatest success stories of randomized algorithms for linear algebra has been the development of fast, randomized algorithms for highly overdetermined linear least-squares problems. However, none of the existing algorithms is backward stable, preventing them from being deployed as drop-in replacements for existing QR-based solvers. This paper introduces sketch-and-precondition with iterative refinement (SPIR) and FOSSILS, two provably backward stable randomized least-squares solvers. SPIR and FOSSILS combine iterative refinement with a preconditioned iterative method applied to the normal equations and converge at the same rate as existing randomized least-squares solvers. This work offers the promise of incorporating randomized least-squares solvers into existing software libraries while maintaining the same level of accuracy and stability as classical solvers. |
| title | Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers |
| topic | Numerical Analysis 65F10, 65F20, 65G50, 65K10, 68W20 |
| url | https://arxiv.org/abs/2406.03468 |