PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Jacobi-Davidson method

Laura Grigori, Taejun Park, Igor Simunec

arXiv:2609.29651v1math.NAcs.NA

TL;DR

Classical Jacobi-Davidson incurs growing orthogonalization costs and distributed synchronization as its search basis expands. This paper replaces that step with sketch-based orthogonalization and proves local quadratic convergence under a uniform separation condition. Experiments report comparable reliability to classical Jacobi-Davidson while reducing orthogonalization cost.

  • Problem

    Jacobi-Davidson orthogonalizes each expansion vector against the full search basis, with cost growing quadratically in subspace dimension and global synchronization in distributed settings.

    Source: §1 · p. 2

  • Method

    The randomized method uses a sketch-orthonormal basis, sketched Galerkin extraction, and a sketch-orthogonal correction equation.

    Source: §1 · p. 2

  • Results

    Under a uniform separation condition, randomized Jacobi-Davidson has local quadratic convergence for general non-Hermitian problems.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Experiments on real and synthetic problems report predicted convergence order and reliability comparable to classical Jacobi-Davidson while reducing orthogonalization cost.

    Source: §7 · p. 23

    For Hermitian problems, the method is not recommended because sketching makes the projected problem non-Hermitian and its increased cost outweighs orthogonalization savings.

    Source: §4.4 · p. 16

Abstract

from arXiv · show

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.

1. Introduction.

Classical Jacobi-Davidson becomes costly as its search subspace grows, motivating a randomized variant that replaces full-vector orthogonalization with sketch-based operations. The paper establishes local quadratic convergence under a uniform separation condition and develops extraction variants for interior eigenvalues.

1. Introduction.

  • Full-basis orthogonalization costs O(nm^2) after m iterations, while periodic restarts can discard information and slow convergence.In distributed memory, full-length inner products require global synchronization at every iteration.Source: §1 · p. 2
  • The randomized method uses a sketch-orthonormal search basis, sketched Galerkin extraction, and a sketch-orthogonal correction projector to reduce orthogonalization cost.The analysis establishes quadratic convergence for non-Hermitian problems.Source: §1 · p. 2
  • An exact randomized correction solve is one step of sketched inverse iteration for an arbitrary shift, supporting the convergence analysis and harmonic and refined extraction variants.These variants are developed for approximating interior eigenvalues.Source: §1 · pp. 2–3
  • The convergence result applies under a uniform separation condition, and the paper also reports quadratic convergence for normal matrices, with cubic convergence for a specified shift.The cubic case uses the standard Rayleigh quotient of the sketched Ritz vector.Source: §1 · p. 3
  • Earlier work suggested combining sketched extraction with Jacobi-Davidson but did not develop or analyze that combination; sketching here leaves deflation, restarting, and preconditioning strategies unchanged.The authors frame their contribution as orthogonal to those existing developments.Source: §1 · p. 3

2. Preliminaries.

The preliminaries recap classical Jacobi-Davidson and introduce sketching as a way to maintain a well-conditioned search basis using cheaper sketched inner products. They also state the embedding requirement used by the randomized method.

2.1. Jacobi-Davidson method.

  • Classical Jacobi-Davidson builds a subspace for the target right eigenvector through Ritz extraction, residual evaluation, a correction solve, and orthogonalized expansion.Under uniform separation, local convergence is typically quadratic for non-Hermitian matrices and cubic for Hermitian matrices.Source: §2.1 · p. 4

2.2. Sketching.

  • A subspace embedding approximately preserves norms and inner products, allowing a sketch-orthonormal, well-conditioned basis to support modified projection methods.Randomized Gram-Schmidt computes such a basis with reduced communication and computational cost.Source: §2.2 · pp. 4–5
  • The analysis requires the sketch to embed the combined search and image spaces; the paper uses a sparsestack of four independent CountSketch matrices.Because the search space depends on the sketch, this embedding requirement is an assumption, not a consequence of obliviousness.Source: §2.2 · pp. 4–5

3. Randomized Jacobi-Davidson method.

The randomized method replaces Euclidean orthogonalization and inner products with sketched counterparts in extraction, correction, and basis updates. An exact correction solve has an inverse-iteration interpretation, which underpins the convergence analysis and supports cost savings.

3. Randomized Jacobi-Davidson method.

  • The method uses sketched residuals and a sketch-orthogonal projector in its correction equation, and accepts Ritz pairs using a residual threshold adjusted for embedding distortion.An exact correction solve produces iterates equivalent to sketched inverse iteration, for arbitrary shifts.Source: §3 · p. 6

3.1. Derivation of the randomized correction equation.

  • The exact correction solution satisfies u + t = α(A − θI)^−1u, with α chosen to make the updated vector sketch-normalized.This equivalence holds for any shift θ outside the spectrum when the stated nonzero condition is met.Source: §3.1 · pp. 6–7

3.2. Computational cost.

  • At subspace dimension m, the randomized iteration costs approximately 6nm + 3TS versus 12nm operations classically, replacing full-length inner products with sketched ones.In distributed memory, sketched vectors can be replicated, reducing synchronization costs; sketching distortion ϵ is a convergence trade-off.Source: §3.2 · pp. 7–8
  • The convergence analysis assumes no restarting and exact correction solves, while practical solves may use a few preconditioned Krylov iterations.The paper notes mixed-precision potential but does not pursue it.Source: §4 · p. 8, §3.2 · p. 8

4. Convergence analysis.

The analysis establishes local quadratic convergence for randomized Jacobi-Davidson under a uniform separation condition, linking the correction step to sketched inverse iteration. It also identifies why standard sketched extraction is less suited to interior targets and how harmonic and refined variants address that issue.

4.1. The sketched Ritz value.

  • The sketched Ritz-value error is bounded in terms of the Ritz-vector angle, the embedding error, and the adjoint residual; for normal A, the bound simplifies.When left and right eigenvectors coincide, the bound is |θ_m − λ| ≤ s_m(s_m + ϵ).Source: §4.1 · pp. 9–10

4.2. The sketched Ritz vector.

  • Sketched Galerkin extraction needs uniform separation to ensure Ritz-vector convergence, a condition that may be unfavorable for interior targets; harmonic and refined variants address this limitation differently.Harmonic extraction changes the shift-transformed problem, while refined extraction minimizes the residual over the trial subspace and removes the separation requirement.Source: §4.2 · p. 10

4.3. Sketched inverse iteration.

  • An exact solution of the correction equation yields an inverse-iteration direction for an arbitrary shift, so the next search space contains a vector no worse aligned with the target eigenvector.The accuracy result requires the shift to be closer to the target eigenvalue than the separation parameter and a sufficiently small current Ritz-vector angle.Source: §4.3 · p. 12

4.4. Local quadratic convergence.

  • Under exact correction solves, an embedding condition, uniform separation, and a sufficiently accurate initial subspace, RJD converges locally at least quadratically for non-Hermitian problems.Both the search-space angle and the Ritz-vector angle converge at that rate.Source: §4.4 · p. 14
  • For normal A, the local contraction is quadratic, and using the standard Rayleigh quotient as the shift makes it cubic.The cubic rate comes at the cost of two additional length-n inner products per iteration.Source: §4.4 · pp. 15–16
  • The authors do not recommend this algorithm for Hermitian problems because sketching makes the projected problem non-Hermitian and its added cost outweighs orthogonalization savings.Maintaining Hermitian projected matrices instead reintroduces length-n inner products.Source: §4.4 · p. 16

5. Harmonic and refined extraction.

Harmonic extraction recasts sketched extraction through shift-invert for interior eigenvalues, while refined extraction improves vector behavior. In the refined harmonic variant, local quadratic convergence holds with separation required only for the value, not the vector.

5.1. Harmonic extraction.

  • The harmonic pencil and refined-vector SVD reuse stored sketched quantities, requiring no new products with A or new sketch.Source: §5.1 · p. 16, §5.2 · p. 18
  • Harmonic extraction is sketched Rayleigh–Ritz for (A − τI)^−1 on the transformed subspace, where the wanted interior eigenvalue becomes dominant, but separation is still required.The harmonic pencil can be assembled from stored quantities without new products with A or a new sketch.Source: §5.1 · pp. 16–17
  • The harmonic value is as accurate as the standard Rayleigh quotient up to shift-invert factors, while its vector needs an additional separation condition and is more fragile.The value’s locality condition includes a κ2(A − τI) factor.Source: §5.1 · p. 17

5.2. Refined extraction.

  • The sketched refined Ritz vector minimizes the sketched residual in the search subspace and converges whenever the minimal residual does, without a uniform separation condition.Its trailing right singular vector is computed by a thin SVD from stored quantities.Source: §5.2 · pp. 17–18

5.3. Refined harmonic extraction.

  • For interior eigenvalues, the refined harmonic variant has local quadratic convergence; separation is required for the value, but not the vector.The refined vector is combined with the harmonic Ritz value.Source: §5.3 · p. 18
  • When τ is very close to λ, the harmonic-value guarantee can be lost; the refined vector’s Rayleigh quotient converges regardless of |λ − τ| once the vector converges, at two extra length-n inner products per iteration.Source: §5.3 · pp. 18–19
  • The synthetic exact-solve test fitted local orders of 2.26 for JD and 2.34 for RJD, consistent with the theoretical slope-2 reference.Source: Figure 1 · p. 19

6. Numerical Experiments.

Across synthetic and real non-Hermitian problems, randomized Jacobi-Davidson (RJD) tracked classical JD’s convergence and reliability while reducing orthogonalization cost. The experiments also tested multiple eigenvalues and extraction strategies for interior targets.

6.1. Inexact solves for correction equation and order of convergence.

  • On the synthetic matrix with exact correction solves, fitted local orders were 2.26 for JD and 2.34 for RJD, consistent with predicted quadratic convergence.For garon2, fitted order was close to 1 with fixed GMRES budgets of 5, 10, or 20 iterations for both methods, increasing with correction accuracy; exact solves were superlinear.Source: §6.1 · pp. 19–20, Table 1 · p. 20
  • On garon2, JD and RJD tracked closely across exact and inexact correction solves, with neither consistently ahead.The figure plots angle and residual against outer iteration for GMRES budgets of 5, 10, and 20.Source: Figure 2 · p. 20, §6.1 · p. 20

6.3. Extraction strategies for interior eigenvalues.

  • Across 1,000 starts per extraction on a clustered non-normal matrix, RJD had higher success rates for all four strategies, with very similar median iteration counts.The authors conclude that sketching did not degrade reliability across the extraction strategies tested, not that RJD is intrinsically more reliable.Source: Table 2 · p. 21, §6.3 · p. 21
  • For the interior-target extraction experiment, harmonic and harmonic-refined methods did not consistently outperform standard or refined extraction.The authors leave a fuller explanation of this result to future work.Source: §6.3 · p. 21

6.2. Multiple eigenvalues.

  • Across three real matrices, both methods found the six target eigenvalues with comparable outer iterations; RJD needed slightly more, while its lower orthogonalization cost may offset that difference.The comparison uses 5 GMRES iterations for each correction solve.Source: §6.2 · p. 21, Figure 3 · p. 22

7. Conclusion.

The paper concludes that randomized Jacobi-Davidson retains local quadratic convergence under the stated condition while reducing orthogonalization cost. Experiments support comparable reliability, while several theoretical and practical extensions remain open.

7. Conclusion.

  • RJD uses a sketch-orthonormal search basis, sketched Galerkin extraction, and a modified correction equation, retaining local quadratic convergence for non-Hermitian problems under uniform separation at roughly half the classical orthogonalization cost.Experiments confirmed predicted convergence order and comparable reliability across real and synthetic problems, including inexact solves and interior extraction strategies.Source: §7 · p. 23
  • Open directions include two-sided formulations, generalized and nonlinear problems, JDQR-type methods, inexact-solve convergence theory, and mixed-precision implementation.The authors note that a two-sided formulation may yield cubic local convergence.Source: §7 · p. 23

Related papers

Loading 2609.29651v1…