Randomized Jacobi-Davidson method
TL;DR
A randomized Jacobi-Davidson method is introduced that replaces this orthogonalization with a much cheaper randomized orthogonalization process, which requires no inner products involving full-dimensional vectors and matches the reliability of classical Jacobi-Davidson while reducing orthogonalization cost.
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.