Fast and accurate randomized algorithms for linear systems and eigenvalue problems
This paper develops a class of algorithms for general linear systems and eigenvalue problems. These algorithms apply fast randomized dimension reduction (``sketching"") to accelerate standard subspace projection methods, such as GMRES and Rayleigh--Ritz. This modification makes it possible...
| Päätekijät: | , |
|---|---|
| Aineistotyyppi: | Journal article |
| Kieli: | English |
| Julkaistu: |
Society for Industrial and Applied Mathematics
2024
|
| _version_ | 1826314662435618816 |
|---|---|
| author | Nakatsukasa, Y Tropp, JA |
| author_facet | Nakatsukasa, Y Tropp, JA |
| author_sort | Nakatsukasa, Y |
| collection | OXFORD |
| description | This paper develops a class of algorithms for general linear systems and eigenvalue problems. These algorithms apply fast randomized dimension reduction (``sketching"") to accelerate standard subspace projection methods, such as GMRES and Rayleigh--Ritz. This modification makes it possible to incorporate nontraditional bases for the approximation subspace that are easier to construct. When the basis is numerically full rank, the new algorithms have accuracy similar to classic methods but run faster and may use less storage. For model problems, numerical experiments show large advantages over the optimized MATLAB routines, including a 70\times speedup over gmres and a 10\times speedup over eigs. |
| first_indexed | 2024-03-07T08:27:00Z |
| format | Journal article |
| id | oxford-uuid:f9cc82d9-3ee9-4a9d-8c9d-8874afdffa2b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:35:55Z |
| publishDate | 2024 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:f9cc82d9-3ee9-4a9d-8c9d-8874afdffa2b2024-09-18T12:31:31ZFast and accurate randomized algorithms for linear systems and eigenvalue problemsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f9cc82d9-3ee9-4a9d-8c9d-8874afdffa2bEnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2024Nakatsukasa, YTropp, JAThis paper develops a class of algorithms for general linear systems and eigenvalue problems. These algorithms apply fast randomized dimension reduction (``sketching"") to accelerate standard subspace projection methods, such as GMRES and Rayleigh--Ritz. This modification makes it possible to incorporate nontraditional bases for the approximation subspace that are easier to construct. When the basis is numerically full rank, the new algorithms have accuracy similar to classic methods but run faster and may use less storage. For model problems, numerical experiments show large advantages over the optimized MATLAB routines, including a 70\times speedup over gmres and a 10\times speedup over eigs. |
| spellingShingle | Nakatsukasa, Y Tropp, JA Fast and accurate randomized algorithms for linear systems and eigenvalue problems |
| title | Fast and accurate randomized algorithms for linear systems and eigenvalue problems |
| title_full | Fast and accurate randomized algorithms for linear systems and eigenvalue problems |
| title_fullStr | Fast and accurate randomized algorithms for linear systems and eigenvalue problems |
| title_full_unstemmed | Fast and accurate randomized algorithms for linear systems and eigenvalue problems |
| title_short | Fast and accurate randomized algorithms for linear systems and eigenvalue problems |
| title_sort | fast and accurate randomized algorithms for linear systems and eigenvalue problems |
| work_keys_str_mv | AT nakatsukasay fastandaccuraterandomizedalgorithmsforlinearsystemsandeigenvalueproblems AT troppja fastandaccuraterandomizedalgorithmsforlinearsystemsandeigenvalueproblems |