Randomized-Accelerated FEAST: A Hybrid Approach for Large-Scale Eigenvalue Problems
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912740416684032 |
|---|---|
| author | Nadiger, Ayush |
| author_facet | Nadiger, Ayush |
| contents | We present Randomized-Accelerated FEAST (RA-FEAST), a hybrid algorithm that combines contour-integration-based eigensolvers with randomized numerical linear algebra techniques for efficiently computing partial eigendecompositions of large-scale matrices arising in statistical applications. By incorporating randomized subspace initialization to enable aggressive quadrature reduction and truncated refinement iterations, our method achieves significant computational speedups (up to 38x on sparse graph Laplacian benchmarks at n = 8000) while maintaining high-accuracy approximations to the target eigenspace. We provide a probabilistic error bound for the randomized warmstart, a stability result for inexact FEAST iterations under general perturbations, and a simple complexity model characterizing the trade-off between initialization cost and solver speedup. Empirically, we demonstrate that RA-FEAST can be more than an order of magnitude faster than standard FEAST while preserving accuracy on sparse Laplacian problems representative of modern spectral methods in statistics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01257 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Randomized-Accelerated FEAST: A Hybrid Approach for Large-Scale Eigenvalue Problems Nadiger, Ayush Numerical Analysis Computation 65F15, 65F50 G.1.3; G.3 We present Randomized-Accelerated FEAST (RA-FEAST), a hybrid algorithm that combines contour-integration-based eigensolvers with randomized numerical linear algebra techniques for efficiently computing partial eigendecompositions of large-scale matrices arising in statistical applications. By incorporating randomized subspace initialization to enable aggressive quadrature reduction and truncated refinement iterations, our method achieves significant computational speedups (up to 38x on sparse graph Laplacian benchmarks at n = 8000) while maintaining high-accuracy approximations to the target eigenspace. We provide a probabilistic error bound for the randomized warmstart, a stability result for inexact FEAST iterations under general perturbations, and a simple complexity model characterizing the trade-off between initialization cost and solver speedup. Empirically, we demonstrate that RA-FEAST can be more than an order of magnitude faster than standard FEAST while preserving accuracy on sparse Laplacian problems representative of modern spectral methods in statistics. |
| title | Randomized-Accelerated FEAST: A Hybrid Approach for Large-Scale Eigenvalue Problems |
| topic | Numerical Analysis Computation 65F15, 65F50 G.1.3; G.3 |
| url | https://arxiv.org/abs/2512.01257 |