Randomized Jacobi-Davidson method
Abstract
The Jacobi-Davidson method is a widely used subspace method for computing a few eigenpairs of a large, sparse, non-Hermitian matrix closest to a target. Like other subspace methods, it orthogonalizes each new expansion vector against the whole search basis, at a cost that grows quadratically with the subspace dimension and, in a distributed setting, requires a global synchronization at every iteration. We introduce a randomized Jacobi-Davidson method that replaces this orthogonalization with a much cheaper randomized orthogonalization process, which requires no inner products involving full-dimensional vectors. We prove that, under a uniform separation condition, the randomized method retains the local quadratic convergence of classical Jacobi-Davidson for non-Hermitian problems. The key step is showing that an exact solution of the randomized correction equation is one step of sketched inverse iteration for an arbitrary shift, which lets us extend the analysis to harmonic and refined variants of the sketched extraction, better suited to interior eigenvalues. Numerical experiments on real and synthetic non-Hermitian eigenvalue problems confirm the predicted convergence order and show that the randomized method matches the reliability of classical Jacobi-Davidson while reducing orthogonalization cost.
Related
- A High-Accuracy Numerical Homogenization Method for Quasiperiodic Hamilton--Jacobi Equations
- Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
- Asynchronous Jacobi and randomized Gauss--Seidel methods in shared and distributed memory: A unified convergence-rate analysis
- A nonstandard fractional Jacobi pseudospectral method for weakly regular right-sided Caputo terminal problems
- Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method
BibTeX
@misc{grigori2026randomized,
title = {{Randomized Jacobi-Davidson method}},
author = {Laura Grigori and Taejun Park and Igor Simunec},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29651},
eprint = {2609.29651},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05743949v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Randomized Jacobi-Davidson method
AU - Laura Grigori
AU - Taejun Park
AU - Igor Simunec
PY - 2026
DA - 2026/09/01
PB - HAL
DO - 10.48550/arxiv.2609.29651
UR - https://hal.science/hal-05743949v1
AB - The Jacobi-Davidson method is a widely used subspace method for computing a few eigenpairs of a large, sparse, non-Hermitian matrix closest to a target. Like other subspace methods, it orthogonalizes each new expansion vector against the whole search basis, at a cost that grows quadratically with the subspace dimension and, in a distributed setting, requires a global synchronization at every iteration. We introduce a randomized Jacobi-Davidson method that replaces this orthogonalization with a much cheaper randomized orthogonalization process, which requires no inner products involving full-dimensional vectors. We prove that, under a uniform separation condition, the randomized method retains the local quadratic convergence of classical Jacobi-Davidson for non-Hermitian problems. The key step is showing that an exact solution of the randomized correction equation is one step of sketched inverse iteration for an arbitrary shift, which lets us extend the analysis to harmonic and refined variants of the sketched extraction, better suited to interior eigenvalues. Numerical experiments on real and synthetic non-Hermitian eigenvalue problems confirm the predicted convergence order and show that the randomized method matches the reliability of classical Jacobi-Davidson while reducing orthogonalization cost.
ER -