Skip to main content

xingo_statla/
eigs.rs

1//! # Chapter 12.6 — `eigsh` and `eigs`: Krylov–Schur restarted Lanczos and Arnoldi with ARPACK's contract
2//!
3//! ## Purpose
4//! *`k` eigenpairs at one end of the spectrum of a large sparse or implicit
5//! operator.* [`eigsh()`] (symmetric) and [`eigs()`] (general real) take
6//! ARPACK's vocabulary — the two-letter `which` codes, `ncv`, the relative
7//! convergence test, scipy's defaults — and restart by the Krylov–Schur
8//! method of Stewart (2001) instead of ARPACK's implicit QR shifts
9//! (decision S7 of D-0127): with exact shifts both keep the same subspace,
10//! and in Schur form locking and purging are deletions of rows and columns.
11//!
12//! ## Notation
13//! `A ∈ R^{n×n}` the operator; `m = ncv`; `V = [v_1 … v_{m+1}] ∈ T^{n×(m+1)}`
14//! orthonormal; `H̄ ∈ T^{(m+1)×m}` with rows `0..m` the projected `H` and row
15//! `m` the *coupling row* `bᵀ`. The **Krylov decomposition** kept throughout
16//! is
17//!
18//! ```text
19//! A V_j = V_j H_j + v_{j+1} b_jᵀ          (KS)
20//! ```
21//!
22//! with `b_j = β_j e_j` after an Arnoldi step and a full vector after a
23//! restart. The first `n_L` columns are **locked**: their part of `b` is
24//! zero and `H = [S_LL H_LA; 0 H_AA]` is block upper triangular, so the
25//! eigenvalues of `H` are those of `S_LL` (quasi-triangular, fixed) and of
26//! the *active* block `H_AA`. In the symmetric case `H_LA = 0` and `S_LL`
27//! is diagonal. `τ` is the tolerance ([`EigsOptions::tol`], `0` meaning
28//! `ε_T`), `ε^{2/3}` ARPACK's floor of the test, `‖A‖_est = max_j ‖A v_j‖`.
29//! A Ritz pair `(θ, y = V z)` of `H` has residual `‖A y − θ y‖ = |bᵀ z|` by
30//! (KS) (`‖z‖ = 1`).
31//!
32//! ## Algorithm KS (Krylov–Schur, one engine for both drivers)
33//! KS1. \[Start.\] `v_1 ← v0/‖v0‖` (`v0` from the options or `n` Gaussian
34//!      deviates of the seed's stream, Algorithm G); `j ← 0`; `n_L ← 0`.
35//! KS2. \[Expand.\] For `j, …, m − 1`: `w ← A v_{j+1}` (checked finite);
36//!      `‖A‖_est ← max(‖A‖_est, ‖w‖)`; Gram–Schmidt against **all** of
37//!      `V_{j+1}` with a DGKS second pass, the coefficients of both passes
38//!      forming column `j` of `H`; `β ← ‖w‖`; if `β ≤ ε_T‖A‖_est`, an
39//!      invariant subspace: `v_{j+2}` is drawn from the seed's stream and
40//!      orthogonalized, `β ← 0` (Algorithm E of Chapter 12.0.7). `h_{j+1,j} ←
41//!      β`. In `eigsh` (KS2′) the strict upper part of the new column is
42//!      then overwritten by the mirror of its row (`β_{j−1}`, or the
43//!      arrowhead `b` after a restart), so that `H` is exactly symmetric and
44//!      the tiny couplings of converged Ritz vectors stay tiny: the
45//!      Gram–Schmidt coefficients there are those couplings plus rounding
46//!      `O(ε‖A‖)`, which only orthogonalize `w` (as in Lanczos, where they
47//!      are not stored).
48//! KS3. \[Schur.\] Decompose the active block `H_AA = Z_A T_A Z_Aᵀ`: in
49//!      `eigsh`, `T_A` diagonal by the Jacobi method of the symmetrized
50//!      block (Algorithm SJ of 12.6.1); in `eigs`, the standardized real
51//!      Schur form by Hessenberg reduction and Francis double-shift QR
52//!      (HR + FQ). Then `b_A ← b_Aᵀ Z_A`, `H_LA ← H_LA Z_A`.
53//! KS4. \[Ritz.\] The eigenvalues `θ` of the locked blocks and of `T_A`;
54//!      for an active block the eigenvector `x` of `T_A` (Algorithm EV) gives
55//!      the estimate `ρ = |b_Aᵀ x|/‖x‖` (≥ the true one: the locked
56//!      components of the eigenvector of `H` are left out). The candidates
57//!      are ordered by `which` (a conjugate pair counts as two values,
58//!      adjacent, `+i` first; `BE` alternates the high and the low end,
59//!      high first; ties are broken by ARPACK's secondary key — `LM`↔`LR`,
60//!      `SM`↔`SR`, `LI`→`LM`, `SI`→`SM` — then by position); the
61//!      **wanted** are the first `k`.
62//! KS5. \[Test.\] A wanted value is converged when it is locked, or when
63//!      `ρ ≤ τ·max(ε^{2/3}, |θ|)` (ARPACK's test, `|θ|` the modulus). If all
64//!      `k` are converged, go to KS8; if the restart limit is reached,
65//!      [`StatlaError::NoConvergence`] (or KS8 with the converged ones when
66//!      `allow_partial`).
67//! KS6. \[Reorder and lock.\] `k′ ←` Algorithm K of Chapter 12.0.7 (`n_conv` the
68//!      converged wanted). Reorder `T_A` (Algorithm RO, the rotations
69//!      accumulated into `Z_A`, `b_A` recomputed) so that the converged
70//!      wanted lead, then the other wanted, then the rest, each group in
71//!      `which` order. **Lock** the leading active blocks, in order, while
72//!      they are converged wanted and their entries of `b_A` satisfy the
73//!      test of KS5 (for a symmetric `T_A` that is the estimate itself):
74//!      their entries of `b` become `0` — a perturbation of `A` of norm `≤
75//!      τ·max(ε^{2/3}, |θ|)` — and their vectors are never rotated again.
76//! KS7. \[Truncate (purge).\] Round `k′` so that no `2 × 2` block is split
77//!      (up if there is room, else down), keep `k′ ≥ n_L`. `V ← [V_L, V_A
78//!      Z_A[:, :k′−n_L], v_{m+1}]`, `H ← [S_LL, H_LA Z_A; 0, T_A]` restricted
79//!      to `k′`, coupling row `(0, b_A[:k′−n_L])` with the locked entries
80//!      zeroed: the unwanted Ritz values beyond `k′` (converged or not) are
81//!      purged with their vectors. Count a restart; `j ← k′`; go to KS2.
82//! KS7′. \[Re-orthonormalize.\] One Gram–Schmidt sweep (DGKS) of the new
83//!      active columns and of the residual vector against the columns before
84//!      them, locked ones untouched. `V ← V Z_A` in floating point loses
85//!      `O(u)` of orthogonality per restart, and the loss accumulates
86//!      (measured: `1.9·10⁻¹⁴ = 85u` after 30 restarts at `m = 20`, against
87//!      `≤ 4u` with the sweep); the sweep perturbs (KS) by the loss it
88//!      removes, `O(m u ‖A‖)`.
89//! KS8. \[Vectors.\] For each wanted value the eigenvector `x` of the whole
90//!      quasi-triangular `T = [S_LL, H_LA Z_A; 0, T_A]` (Algorithm EV), `y ←
91//!      V blockdiag(I, Z_A) x`, normalized to unit 2-norm in `Cⁿ` with its
92//!      largest entry real and positive (the conjugate for the `−i` member).
93//!
94//! **Algorithm L** of the contract (thick-restart Lanczos, Wu & Simon 2000)
95//! *is* Algorithm KS with a symmetric `T_A`: after a restart `H` is
96//! `diag(θ)` plus the arrowhead `b` (row `k′`) and its mirror (column `k′`,
97//! the Gram–Schmidt coefficients of the first new step), and the reordering
98//! is a permutation. Both drivers therefore share one engine (two Krylov
99//! engines in the crate instead of three: this and the bidiagonalization
100//! of 12.5).
101//!
102//! **Reorthogonalization policy:** full (KS2 against all of `V`, locked
103//! vectors included), at most two classical Gram–Schmidt passes — the
104//! policy of 12.5. Cost per step: one application plus `≈ 4nj` flops; per
105//! restart `O(n m k′ + m³)`.
106//!
107//! ## Invariants
108//! (K1) `‖V_jᵀV_j − I‖ ≤ c_K · j · u` — debug-asserted after every restart
109//!      (`c_K` = [`C_K`]).
110//! (K2) `‖A V_j − V_j H_j − v_{j+1} b_jᵀ‖ ≤ c_K · j · u · ‖A‖_est` after every
111//!      expansion — computed by the unit tests (`paranoid` runs; it costs `j`
112//!      extra applications).
113//! (K3) After a restart `H̄` is zero outside `[S_LL H_LA; 0 T_A]` (top `k′`
114//!      rows) and the coupling row `k′`, whose locked entries are zero;
115//!      `T_A` is quasi-triangular (diagonal in `eigsh`) — debug-asserted.
116//! (K4) Every returned pair passed the test of KS5 at the moment it was
117//!      locked or returned; locked columns of `V` are never modified again.
118//!
119//! ## Guarantee
120//! A returned pair `(θ, y)` has, in exact arithmetic on the computed
121//! decomposition, `‖A y − θ y‖ ≤ ρ + Σ_locked |b_dropped|·|x_L|`, each term
122//! `≤ τ·max(ε^{2/3}, |θ|)`; rounding adds `c_K·m·u·‖A‖_est` by (K1)–(K2).
123//! Hence the acceptance form `‖A y − θ y‖ ≤ (τ + c_K·m·u)·‖A‖` (when `‖A‖ ≥
124//! ε^{2/3}`). For symmetric `A` this bounds the distance of `θ` to the
125//! spectrum (Parlett, Thm. 4.5.1); for a general `A` the eigenvalue error
126//! is that times its condition number.
127//!
128//! **The constant** `c_K = C_K = 8` (measured in task L3.4, `l34-tables.md`):
129//! the largest recomputed `(‖r‖/‖A‖ − τ)/(m u)` over the Matrix Market
130//! fixtures was `2.44` in `f64` (margin 3.3), (K2) at most `1.8`, (K1)
131//! debug-asserted with `c_K` in every test run. In double-double, whose
132//! operations round to a few `u` (Chapter 11 of `xingo-extprec`), (K2)
133//! reached `7.5` and the residual `19.4`: its smoke tests use `64`
134//! (question Q-L34-7).
135//!
136//! ## Acceptance (L3.4, S9; tests/eigs.rs)
137//! On Matrix Market matrices the `k` wanted eigenvalues agree with
138//! `scipy.sparse.linalg.eigsh`/`eigs` (ARPACK; fixtures committed) to
139//! `1e-10` relative where the gap to the rest of the spectrum is `≥
140//! 10⁻⁶‖A‖`, and every pair has `‖Ay − θy‖ ≤ (τ + c_K·m·u)‖A‖` (with `τ =
141//! 0` the literal `τ‖A‖` is below the rounding of the residual itself; see
142//! question Q-L34-2).
143//!
144//! ## Divergences from the references
145//! * Restart by Krylov–Schur, not implicit QR (S7). Results are compared
146//!   with ARPACK, not traces.
147//! * The symmetric small solver is cyclic Jacobi, not tridiagonal QL (the
148//!   projected matrix after a restart is an arrowhead, not tridiagonal; and
149//!   Jacobi gives orthogonal eigenvectors to `O(ε)` in every case).
150//! * Exactly `k` values are returned, as scipy does: when the `k`-th value
151//!   is the first member of a conjugate pair, its conjugate is omitted
152//!   (question Q-L34-1).
153//! * `BE` returns the values in its own wanted order (high, low, high, …).
154//!
155//! ## References
156//! Stewart, "A Krylov–Schur algorithm for large eigenproblems", SIMAX 23
157//! (2001); Wu & Simon, "Thick-restart Lanczos method for large symmetric
158//! eigenvalue problems", SIMAX 22 (2000); Lehoucq, Sorensen & Yang, *ARPACK
159//! Users' Guide*, SIAM (1998) (`dsaupd`/`dnaupd`: `which`, `ncv`, the test
160//! `‖r‖ ≤ tol·max(ε^{2/3}, |θ|)`, `nev′`); Sorensen, SIMAX 13 (1992);
161//! Parlett, *The Symmetric Eigenvalue Problem* (1998); Daniel, Gragg,
162//! Kaufman & Stewart (1976). Cited from memory.
163
164use xingo_sparse::{DenseBlock, Real};
165
166use crate::StatlaError;
167use crate::error::op_err;
168use crate::krylov::{expand_arnoldi, kept_dimension};
169use crate::operator::LinearOperator;
170use crate::random::Rng;
171use crate::real::{is_exact_zero, le_exact, lt};
172use crate::schur::{
173    Cx, SchurOptions, block_value, blocks, hypot, identity, real_schur, reorder, schur_eigvec,
174    sym_eig,
175};
176use crate::small::{check_finite, check_len, dot, norm2, orthogonalize_against};
177
178/// The constant `c_K` of invariants (K1)–(K2) and of the residual guarantee
179/// (measured in task L3.4, with a margin).
180pub(crate) const C_K: f64 = 8.0;
181
182/// A pair `re + i·im` (eigenvalues of a real nonsymmetric operator). No
183/// arithmetic: a value type for results, not a complex scalar (complex
184/// matrices are out of scope).
185#[derive(Clone, Copy, Debug, Default, PartialEq)]
186pub struct Complex<T: Real = f64> {
187    /// Real part.
188    pub re: T,
189    /// Imaginary part.
190    pub im: T,
191}
192
193/// Which part of the spectrum, with ARPACK's two-letter codes
194/// ([`Which::from_arpack`]) so that R and Python pass their strings
195/// through `xingo-ffi` unchanged. [`eigsh()`] accepts `LM SM LA SA BE`;
196/// [`eigs()`] accepts `LM SM LR SR LI SI`; any other combination is
197/// [`StatlaError::InvalidArgument`].
198#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
199#[non_exhaustive]
200pub enum Which {
201    /// `LM`: largest `|λ|` (default of ARPACK, scipy, RSpectra).
202    LargestMagnitude,
203    /// `SM`: smallest `|λ|` (slow without shift-invert: prefer
204    /// [`crate::eigsh_near`] with `σ = 0`).
205    SmallestMagnitude,
206    /// `LA`: largest algebraic (symmetric).
207    LargestAlgebraic,
208    /// `SA`: smallest algebraic (symmetric).
209    SmallestAlgebraic,
210    /// `BE`: half from each end, the extra one from the high end, as
211    /// ARPACK (symmetric).
212    BothEnds,
213    /// `LR`: largest real part (general).
214    LargestReal,
215    /// `SR`: smallest real part (general).
216    SmallestReal,
217    /// `LI`: largest imaginary part in magnitude (general).
218    LargestImag,
219    /// `SI`: smallest imaginary part in magnitude (general).
220    SmallestImag,
221}
222
223impl Which {
224    /// The value of an ARPACK code (`"LM"`, …), case-sensitive as ARPACK.
225    #[must_use]
226    pub fn from_arpack(code: &str) -> Option<Self> {
227        Some(match code {
228            "LM" => Self::LargestMagnitude,
229            "SM" => Self::SmallestMagnitude,
230            "LA" => Self::LargestAlgebraic,
231            "SA" => Self::SmallestAlgebraic,
232            "BE" => Self::BothEnds,
233            "LR" => Self::LargestReal,
234            "SR" => Self::SmallestReal,
235            "LI" => Self::LargestImag,
236            "SI" => Self::SmallestImag,
237            _ => return None,
238        })
239    }
240
241    /// The ARPACK code.
242    #[must_use]
243    pub fn arpack_code(self) -> &'static str {
244        match self {
245            Self::LargestMagnitude => "LM",
246            Self::SmallestMagnitude => "SM",
247            Self::LargestAlgebraic => "LA",
248            Self::SmallestAlgebraic => "SA",
249            Self::BothEnds => "BE",
250            Self::LargestReal => "LR",
251            Self::SmallestReal => "SR",
252            Self::LargestImag => "LI",
253            Self::SmallestImag => "SI",
254        }
255    }
256
257    fn symmetric_ok(self) -> bool {
258        matches!(
259            self,
260            Self::LargestMagnitude
261                | Self::SmallestMagnitude
262                | Self::LargestAlgebraic
263                | Self::SmallestAlgebraic
264                | Self::BothEnds
265        )
266    }
267
268    fn general_ok(self) -> bool {
269        matches!(
270            self,
271            Self::LargestMagnitude
272                | Self::SmallestMagnitude
273                | Self::LargestReal
274                | Self::SmallestReal
275                | Self::LargestImag
276                | Self::SmallestImag
277        )
278    }
279}
280
281/// Options of [`eigs()`] and [`eigsh()`]. Defaults are scipy's
282/// (`scipy.sparse.linalg.eigs`/`eigsh`) where it has one.
283#[derive(Clone, Debug, PartialEq)]
284pub struct EigsOptions<T: Real = f64> {
285    /// Krylov dimension; `None` = `min(n, max(2k + 1, 20))`. Must satisfy
286    /// `k < ncv ≤ n`.
287    pub ncv: Option<usize>,
288    /// Relative tolerance of the convergence test (ARPACK's): a Ritz pair
289    /// `(θ, y)` is converged when `‖f‖ |e_jᵀ s| ≤ tol · max(ε^{2/3}, |θ|)`;
290    /// `0` (default) means `T::EPSILON`.
291    pub tol: f64,
292    /// Restart limit; `None` = `10 n` (scipy's `maxiter`).
293    pub max_restarts: Option<usize>,
294    /// Starting vector; `None` = Gaussian from [`EigsOptions::seed`]
295    /// (Algorithm G), so runs are reproducible.
296    pub v0: Option<Vec<T>>,
297    /// Seed of the starting vector and of restarts after an invariant
298    /// subspace is found (default 0).
299    pub seed: u64,
300    /// DGKS threshold (default `1/√2`).
301    pub reorth_eta: f64,
302    /// Compute eigenvectors (default `true`; scipy's
303    /// `return_eigenvectors`).
304    pub vectors: bool,
305    /// On non-convergence return the converged pairs (`Ok`, fewer than
306    /// `k`) instead of [`StatlaError::NoConvergence`] (default `false`;
307    /// S10).
308    pub allow_partial: bool,
309}
310
311impl<T: Real> Default for EigsOptions<T> {
312    fn default() -> Self {
313        Self {
314            ncv: None,
315            tol: 0.0,
316            max_restarts: None,
317            v0: None,
318            seed: 0,
319            reorth_eta: core::f64::consts::FRAC_1_SQRT_2,
320            vectors: true,
321            allow_partial: false,
322        }
323    }
324}
325
326/// Work counters of the Krylov drivers.
327#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
328#[non_exhaustive]
329pub struct EigsStats {
330    /// Restarts performed.
331    pub restarts: usize,
332    /// Operator applications.
333    pub applies: usize,
334    /// Second Gram–Schmidt passes (DGKS) triggered.
335    pub reorthogonalizations: usize,
336    /// Pairs converged (`= k` unless `allow_partial`).
337    pub converged: usize,
338}
339
340/// Symmetric eigenpairs, most wanted first (in the order of `which`).
341#[derive(Clone, Debug)]
342#[non_exhaustive]
343pub struct SymEigen<T: Real = f64> {
344    /// Eigenvalues.
345    pub values: Vec<T>,
346    /// Eigenvectors as columns (`n × values.len()`), orthonormal; `None`
347    /// when [`EigsOptions::vectors`] is off.
348    pub vectors: Option<DenseBlock<T>>,
349    /// Counters.
350    pub stats: EigsStats,
351}
352
353/// Eigenpairs of a real nonsymmetric operator, most wanted first; complex
354/// conjugate pairs are adjacent, positive imaginary part first (exactly
355/// `k` values: the conjugate of a `k`-th value with positive imaginary
356/// part is omitted, as scipy does).
357#[derive(Clone, Debug)]
358#[non_exhaustive]
359pub struct Eigen<T: Real = f64> {
360    /// Eigenvalues.
361    pub values: Vec<Complex<T>>,
362    /// Real parts of the eigenvectors (`n × values.len()`), unit 2-norm
363    /// in `C^n` per column; `None` when vectors are off.
364    pub vectors_re: Option<DenseBlock<T>>,
365    /// Imaginary parts (zero columns for real eigenvalues).
366    pub vectors_im: Option<DenseBlock<T>>,
367    /// Counters.
368    pub stats: EigsStats,
369}
370
371/// The validated parameters of one run.
372struct Params<T> {
373    ncv: usize,
374    tol: T,
375    eta: T,
376    eps23: T,
377    max_restarts: usize,
378}
379
380fn invalid(what: &'static str) -> StatlaError {
381    StatlaError::InvalidArgument { what }
382}
383
384/// `ε_T^{2/3}` by Newton's iteration on `y³ = ε²` (only `+ − · /`, a fixed
385/// number of steps: the same bits everywhere).
386fn eps23<T: Real>() -> T {
387    let a = T::EPSILON * T::EPSILON;
388    let (two, three) = (T::from_f64(2.0), T::from_f64(3.0));
389    let mut y = T::ONE;
390    for _ in 0..300 {
391        y = (two * y + a / (y * y)) / three;
392    }
393    y
394}
395
396/// Check the arguments (in the order of the error conventions, 12.0.1).
397fn validate<T: Real>(
398    rows: usize,
399    cols: usize,
400    k: usize,
401    which: Which,
402    o: &EigsOptions<T>,
403    symmetric: bool,
404) -> Result<Params<T>, StatlaError> {
405    if rows != cols {
406        return Err(invalid("eigs/eigsh: the operator is not square"));
407    }
408    let n = rows;
409    if symmetric && !which.symmetric_ok() {
410        return Err(invalid("eigsh: which must be one of LM SM LA SA BE"));
411    }
412    if !symmetric && !which.general_ok() {
413        return Err(invalid("eigs: which must be one of LM SM LR SR LI SI"));
414    }
415    if symmetric && (k == 0 || k >= n) {
416        return Err(invalid("eigsh: k must satisfy 1 <= k < n"));
417    }
418    if !symmetric && (k == 0 || k + 1 >= n) {
419        return Err(invalid("eigs: k must satisfy 1 <= k < n - 1"));
420    }
421    let ncv = o.ncv.unwrap_or_else(|| n.min((2 * k + 1).max(20)));
422    if ncv <= k || ncv > n {
423        return Err(invalid("eigs/eigsh: ncv must satisfy k < ncv <= n"));
424    }
425    if !o.tol.is_finite() || lt(o.tol, 0.0) {
426        return Err(invalid("eigs/eigsh: tol must be finite and >= 0"));
427    }
428    if !o.reorth_eta.is_finite() || !lt(0.0, o.reorth_eta) || !lt(o.reorth_eta, 1.0) {
429        return Err(invalid("eigs/eigsh: reorth_eta must lie in (0, 1)"));
430    }
431    if let Some(v0) = &o.v0 {
432        check_len("v0", n, v0.len())?;
433        check_finite("v0", v0)?;
434        if is_exact_zero(norm2(v0)) {
435            return Err(invalid("eigs/eigsh: v0 is the zero vector"));
436        }
437    }
438    let tol = if is_exact_zero(o.tol) {
439        T::EPSILON
440    } else {
441        T::from_f64(o.tol)
442    };
443    Ok(Params {
444        ncv,
445        tol,
446        eta: T::from_f64(o.reorth_eta),
447        eps23: eps23::<T>(),
448        max_restarts: o.max_restarts.unwrap_or_else(|| n.saturating_mul(10)),
449    })
450}
451
452/// The argument checks of [`eigsh()`]/[`eigs()`], for the shift-invert
453/// drivers (which validate before factorizing).
454pub(crate) fn validate_for<T: Real>(
455    rows: usize,
456    cols: usize,
457    k: usize,
458    which: Which,
459    o: &EigsOptions<T>,
460    symmetric: bool,
461) -> Result<(), StatlaError> {
462    validate(rows, cols, k, which, o, symmetric).map(|_| ())
463}
464
465/// `a` before `b` in the order of `which` (strict), on representatives with
466/// `im ≥ 0`.
467fn before<T: Real>(which: Which, a: (T, T), b: (T, T)) -> bool {
468    match which {
469        Which::LargestMagnitude => lt(hypot(b.0, b.1), hypot(a.0, a.1)),
470        Which::SmallestMagnitude => lt(hypot(a.0, a.1), hypot(b.0, b.1)),
471        Which::LargestAlgebraic | Which::LargestReal | Which::BothEnds => lt(b.0, a.0),
472        Which::SmallestAlgebraic | Which::SmallestReal => lt(a.0, b.0),
473        Which::LargestImag => lt(b.1.abs(), a.1.abs()),
474        Which::SmallestImag => lt(a.1.abs(), b.1.abs()),
475    }
476}
477
478/// The tie-break of `which`: ARPACK's `dngets` pre-sorts by this key
479/// before the stable sort by `which` (`LM`↔`LR`, `SM`↔`SR`, `LI`→`LM`,
480/// `SI`→`SM`), so that equal keys (a spectrum of real values under `LI`,
481/// `±λ` under `LM`) are resolved the same way at every restart.
482fn tie_break(which: Which) -> Which {
483    match which {
484        Which::LargestMagnitude => Which::LargestReal,
485        Which::SmallestMagnitude => Which::SmallestReal,
486        Which::LargestReal | Which::LargestImag | Which::LargestAlgebraic | Which::BothEnds => {
487            Which::LargestMagnitude
488        }
489        Which::SmallestReal | Which::SmallestImag | Which::SmallestAlgebraic => {
490            Which::SmallestMagnitude
491        }
492    }
493}
494
495/// KS4: the order of the blocks with values `vals` (representatives), most
496/// wanted first; ties by [`tie_break`], then the input order (locked
497/// blocks come first).
498fn rank_blocks<T: Real>(which: Which, vals: &[(T, T)]) -> Vec<usize> {
499    let mut idx: Vec<usize> = (0..vals.len()).collect();
500    let key = if which == Which::BothEnds {
501        Which::LargestAlgebraic
502    } else {
503        which
504    };
505    let second = tie_break(which);
506    let cmp = |w: Which, a: (T, T), b: (T, T)| {
507        if before(w, a, b) {
508            core::cmp::Ordering::Less
509        } else if before(w, b, a) {
510            core::cmp::Ordering::Greater
511        } else {
512            core::cmp::Ordering::Equal
513        }
514    };
515    idx.sort_by(|&i, &j| cmp(key, vals[i], vals[j]).then_with(|| cmp(second, vals[i], vals[j])));
516    if which != Which::BothEnds {
517        return idx;
518    }
519    // BE: alternate the high end (front) and the low end (back), high first.
520    let mut out = Vec::with_capacity(idx.len());
521    let (mut lo, mut hi) = (0usize, idx.len());
522    let mut high = true;
523    while lo < hi {
524        if high {
525            out.push(idx[lo]);
526            lo += 1;
527        } else {
528            hi -= 1;
529            out.push(idx[hi]);
530        }
531        high = !high;
532    }
533    out
534}
535
536/// One block of `T` at the time of a test.
537#[derive(Clone, Copy, Debug)]
538struct Blk<T> {
539    /// Start row in `T` (full coordinates).
540    start: usize,
541    size: usize,
542    re: T,
543    im: T,
544    locked: bool,
545    converged: bool,
546}
547
548/// The state of Algorithm KS.
549struct Engine<T: Real> {
550    n: usize,
551    m: usize,
552    sym: bool,
553    /// `V`, `n × (m + 1)`.
554    v: Vec<T>,
555    /// `H̄`, `(m + 1) × m`.
556    h: DenseBlock<T>,
557    /// Locked count `n_L`.
558    nl: usize,
559    /// `‖A‖_est`.
560    anorm: T,
561    rng: Rng,
562    stats: EigsStats,
563    #[cfg(test)]
564    k2: Option<f64>,
565}
566
567/// The result of KS3 on the active block.
568struct ActiveSchur<T: Real> {
569    /// `T_A`, `na × na`.
570    t: DenseBlock<T>,
571    /// `Z_A`.
572    z: DenseBlock<T>,
573    /// The coupling row before KS3 (`H̄[m, n_L..m]`).
574    c0: Vec<T>,
575    /// `H_LA` before KS3 (`n_L × na`).
576    hla0: DenseBlock<T>,
577}
578
579impl<T: Real> ActiveSchur<T> {
580    /// `b_A = c0ᵀ Z_A`.
581    fn coupling(&self) -> Vec<T> {
582        let na = self.z.rows;
583        (0..na)
584            .map(|c| dot(&self.c0, &self.z.data[c * na..(c + 1) * na]))
585            .collect()
586    }
587    /// `H_LA Z_A`.
588    fn hla(&self) -> DenseBlock<T> {
589        let (nl, na) = (self.hla0.rows, self.z.rows);
590        let mut out = DenseBlock::zeros(nl, na);
591        for c in 0..na {
592            for t in 0..na {
593                let f = self.z.data[t + c * na];
594                if is_exact_zero(f) {
595                    continue;
596                }
597                for r in 0..nl {
598                    out.data[r + c * nl] += self.hla0.data[r + t * nl] * f;
599                }
600            }
601        }
602        out
603    }
604}
605
606impl<T: Real> Engine<T> {
607    #[inline]
608    fn hi(&self, i: usize, j: usize) -> usize {
609        i + j * (self.m + 1)
610    }
611
612    /// KS2 for `j = from, …, m − 1`.
613    fn expand_from<O: LinearOperator<T> + ?Sized>(
614        &mut self,
615        op: &mut O,
616        from: usize,
617        eta: T,
618    ) -> Result<(), StatlaError> {
619        let (n, m) = (self.n, self.m);
620        let mut w = vec![T::ZERO; n];
621        let mut col = vec![T::ZERO; m + 1];
622        for j in from..m {
623            op.apply(&self.v[j * n..(j + 1) * n], &mut w)
624                .map_err(op_err)?;
625            self.stats.applies += 1;
626            check_finite("operator output", &w)?;
627            self.anorm = self.anorm.max(norm2(&w));
628            col.fill(T::ZERO);
629            let floor = T::EPSILON * self.anorm;
630            let beta = expand_arnoldi(
631                &self.v,
632                n,
633                j + 1,
634                &mut w,
635                &mut col[..=j],
636                eta,
637                floor,
638                &mut self.rng,
639                &mut self.stats.reorthogonalizations,
640            );
641            for i in 0..=j {
642                let at = self.hi(i, j);
643                self.h.data[at] = col[i];
644            }
645            for i in j + 1..=m {
646                let at = self.hi(i, j);
647                self.h.data[at] = T::ZERO;
648            }
649            let at = self.hi(j + 1, j);
650            self.h.data[at] = beta;
651            if self.sym {
652                // KS2′: the strict upper part of column j is the mirror of
653                // row j (`β_{j−1}`, or the arrowhead `b` right after a
654                // restart); the Gram–Schmidt coefficients there only
655                // orthogonalized `w` (Lanczos: they are `b_i` plus rounding).
656                for i in 0..j {
657                    let (up, low) = (self.hi(i, j), self.hi(j, i));
658                    self.h.data[up] = self.h.data[low];
659                }
660            }
661            self.v[(j + 1) * n..(j + 2) * n].copy_from_slice(&w);
662        }
663        Ok(())
664    }
665
666    /// (K2), unit tests only: `max ‖A v_j − V H̄ e_j‖ / ‖A‖_est`.
667    #[cfg(test)]
668    fn relations<O: LinearOperator<T> + ?Sized>(&self, op: &mut O) -> f64 {
669        let (n, m) = (self.n, self.m);
670        let mut worst = 0.0f64;
671        let mut y = vec![T::ZERO; n];
672        for j in 0..m {
673            op.apply(&self.v[j * n..(j + 1) * n], &mut y).unwrap();
674            for i in 0..=m {
675                let f = self.h.data[self.hi(i, j)];
676                crate::small::axpy_sub(f, &self.v[i * n..(i + 1) * n], &mut y);
677            }
678            worst = worst.max(norm2(&y).to_f64());
679        }
680        worst / self.anorm.to_f64().max(f64::MIN_POSITIVE)
681    }
682
683    /// KS3.
684    fn active_schur(&self, so: &SchurOptions<T>) -> Result<ActiveSchur<T>, StatlaError> {
685        let (m, nl) = (self.m, self.nl);
686        let na = m - nl;
687        let mut ha = DenseBlock::zeros(na, na);
688        for j in 0..na {
689            for i in 0..na {
690                ha.data[i + j * na] = self.h.data[self.hi(nl + i, nl + j)];
691            }
692        }
693        let c0: Vec<T> = (0..na).map(|j| self.h.data[self.hi(m, nl + j)]).collect();
694        let mut hla0 = DenseBlock::zeros(nl, na);
695        if !self.sym {
696            for j in 0..na {
697                for i in 0..nl {
698                    hla0.data[i + j * nl] = self.h.data[self.hi(i, nl + j)];
699                }
700            }
701        }
702        let (t, z) = if self.sym {
703            let (d, z) = sym_eig(&ha, so)?;
704            let mut t = DenseBlock::zeros(na, na);
705            for (i, &di) in d.iter().enumerate() {
706                t.data[i + i * na] = di;
707            }
708            (t, z)
709        } else {
710            let mut z = identity::<T>(na);
711            real_schur(&mut ha, &mut z, so)?;
712            (ha, z)
713        };
714        Ok(ActiveSchur { t, z, c0, hla0 })
715    }
716
717    /// The locked block `S_LL`.
718    fn s_ll(&self) -> DenseBlock<T> {
719        let nl = self.nl;
720        let mut s = DenseBlock::zeros(nl, nl);
721        for j in 0..nl {
722            for i in 0..nl {
723                s.data[i + j * nl] = self.h.data[self.hi(i, j)];
724            }
725        }
726        s
727    }
728
729    /// The whole quasi-triangular `T = [S_LL, H_LA Z_A; 0, T_A]` (`m × m`).
730    fn full_t(&self, a: &ActiveSchur<T>) -> DenseBlock<T> {
731        let (m, nl) = (self.m, self.nl);
732        let na = m - nl;
733        let mut t = DenseBlock::zeros(m, m);
734        let s = self.s_ll();
735        for j in 0..nl {
736            for i in 0..nl {
737                t.data[i + j * m] = s.data[i + j * nl];
738            }
739        }
740        if !self.sym {
741            let hla = a.hla();
742            for j in 0..na {
743                for i in 0..nl {
744                    t.data[i + (nl + j) * m] = hla.data[i + j * nl];
745                }
746            }
747        }
748        for j in 0..na {
749            for i in 0..na {
750                t.data[nl + i + (nl + j) * m] = a.t.data[i + j * na];
751            }
752        }
753        t
754    }
755
756    /// (K1), debug builds: `max |V_jᵀV_j − I|` over the first `j` columns.
757    fn orthogonality(&self, j: usize) -> f64 {
758        let n = self.n;
759        let mut e = 0.0f64;
760        for a in 0..j {
761            for c in 0..=a {
762                let d = dot(&self.v[a * n..(a + 1) * n], &self.v[c * n..(c + 1) * n]);
763                if a == c && is_exact_zero(d) {
764                    continue; // the no-room zero vector of Algorithm E
765                }
766                let t = if a == c { d - T::ONE } else { d };
767                e = e.max(t.abs().to_f64());
768            }
769        }
770        e
771    }
772
773    /// (K3), debug builds, right after a restart to `kp`.
774    fn restart_shape(&self, kp: usize) -> bool {
775        let (m, nl) = (self.m, self.nl);
776        for j in 0..m {
777            for i in 0..=m {
778                let v = self.h.data[self.hi(i, j)];
779                if is_exact_zero(v) {
780                    continue;
781                }
782                let ok = if j >= kp || (i > kp) || (i != kp && i > j + 1) {
783                    false
784                } else if i == kp {
785                    j >= nl
786                } else if i == j + 1 {
787                    !self.sym
788                } else {
789                    !self.sym || i == j
790                };
791                if !ok {
792                    return false;
793                }
794            }
795        }
796        true
797    }
798}
799
800/// The test of KS5 for a value of modulus `abs`.
801fn passes<T: Real>(rho: T, abs: T, p: &Params<T>) -> bool {
802    le_exact(rho, p.tol * p.eps23.max(abs))
803}
804
805/// The raw result of Algorithm KS: values (in wanted order, `im` with its
806/// sign) and the complex vectors.
807struct Raw<T: Real> {
808    values: Vec<Complex<T>>,
809    vectors: Option<(DenseBlock<T>, DenseBlock<T>)>,
810    stats: EigsStats,
811    #[cfg_attr(not(test), allow(dead_code))]
812    k2: f64,
813    #[cfg_attr(not(test), allow(dead_code))]
814    locked: usize,
815}
816
817/// Algorithm KS (`sym` selects the symmetric small solver of KS3).
818#[allow(clippy::too_many_lines)] // steps KS1–KS8 in order, as in the chapter
819fn run<T, O>(
820    op: &mut O,
821    k: usize,
822    which: Which,
823    opts: &EigsOptions<T>,
824    sym: bool,
825    paranoid: bool,
826) -> Result<Raw<T>, StatlaError>
827where
828    T: Real,
829    O: LinearOperator<T> + ?Sized,
830{
831    let par = validate(op.nrows(), op.ncols(), k, which, opts, sym)?;
832    let n = op.nrows();
833    let m = par.ncv;
834    let so = SchurOptions::<T>::new();
835    let _ = paranoid;
836    // KS1.
837    let mut rng = Rng::new(opts.seed);
838    let mut v = vec![T::ZERO; n * (m + 1)];
839    match &opts.v0 {
840        Some(v0) => v[..n].copy_from_slice(v0),
841        None => rng.fill(crate::Sketch::Gaussian, &mut v[..n]),
842    }
843    let nv = norm2(&v[..n]);
844    for x in &mut v[..n] {
845        *x = *x / nv;
846    }
847    let mut e = Engine {
848        n,
849        m,
850        sym,
851        v,
852        h: DenseBlock::zeros(m + 1, m),
853        nl: 0,
854        anorm: T::ZERO,
855        rng,
856        stats: EigsStats::default(),
857        #[cfg(test)]
858        k2: None,
859    };
860    let mut from = 0;
861    loop {
862        // KS2.
863        e.expand_from(op, from, par.eta)?;
864        #[cfg(test)]
865        if paranoid {
866            let g = e.relations(op);
867            e.k2 = Some(e.k2.map_or(g, |h: f64| h.max(g)));
868        }
869        // KS3.
870        let mut act = e.active_schur(&so)?;
871        let nl = e.nl;
872        let na = m - nl;
873        // KS4.
874        let s_ll = e.s_ll();
875        let mut cands: Vec<Blk<T>> = Vec::new();
876        for (q, s) in blocks(&s_ll) {
877            let (re, im) = block_value(&s_ll, (q, s));
878            cands.push(Blk {
879                start: q,
880                size: s,
881                re,
882                im,
883                locked: true,
884                converged: true,
885            });
886        }
887        let bl_a = blocks(&act.t);
888        let b_a = act.coupling();
889        for (bi, &(q, s)) in bl_a.iter().enumerate() {
890            let (re, im) = block_value(&act.t, (q, s));
891            let x = schur_eigvec(&act.t, &bl_a, bi);
892            let mut acc = Cx::new(T::ZERO, T::ZERO);
893            let mut xn2 = T::ZERO;
894            for (i, xi) in x.iter().enumerate() {
895                acc = Cx::new(acc.re + b_a[i] * xi.re, acc.im + b_a[i] * xi.im);
896                xn2 += xi.re * xi.re + xi.im * xi.im;
897            }
898            let rho = hypot(acc.re, acc.im) / xn2.sqrt();
899            cands.push(Blk {
900                start: nl + q,
901                size: s,
902                re,
903                im,
904                locked: false,
905                converged: passes(rho, hypot(re, im), &par),
906            });
907        }
908        let vals: Vec<(T, T)> = cands.iter().map(|c| (c.re, c.im)).collect();
909        let order = rank_blocks(which, &vals);
910        // The wanted: the first k values (a pair counts two).
911        let mut wanted: Vec<(usize, bool)> = Vec::with_capacity(k); // (cand, conj)
912        for &ci in &order {
913            if wanted.len() == k {
914                break;
915            }
916            wanted.push((ci, false));
917            if cands[ci].size == 2 && wanted.len() < k {
918                wanted.push((ci, true));
919            }
920        }
921        // KS5.
922        let n_conv = wanted.iter().filter(|w| cands[w.0].converged).count();
923        let limit = e.stats.restarts >= par.max_restarts;
924        if n_conv == k || limit {
925            if n_conv < k && !opts.allow_partial {
926                return Err(StatlaError::NoConvergence {
927                    requested: k,
928                    converged: n_conv,
929                    restarts: e.stats.restarts,
930                });
931            }
932            // KS8.
933            let take: Vec<(usize, bool)> = wanted
934                .iter()
935                .copied()
936                .filter(|w| cands[w.0].converged)
937                .collect();
938            let values: Vec<Complex<T>> = take
939                .iter()
940                .map(|&(ci, conj)| Complex {
941                    re: cands[ci].re,
942                    im: if conj { -cands[ci].im } else { cands[ci].im },
943                })
944                .collect();
945            let vectors = if opts.vectors {
946                Some(e.vectors(&act, &cands, &take))
947            } else {
948                None
949            };
950            let mut stats = e.stats;
951            stats.converged = values.len();
952            #[cfg(test)]
953            let k2 = e.k2.unwrap_or(0.0);
954            #[cfg(not(test))]
955            let k2 = 0.0;
956            return Ok(Raw {
957                values,
958                vectors,
959                stats,
960                k2,
961                locked: e.nl,
962            });
963        }
964        // KS6.
965        e.stats.restarts += 1;
966        let n_conv_active = wanted
967            .iter()
968            .filter(|w| !cands[w.0].locked && cands[w.0].converged)
969            .count();
970        let kp0 = kept_dimension(k, m, n_conv, nl + n_conv_active);
971        // Ranks of the active blocks: converged wanted, other wanted, rest.
972        let mut group = vec![2usize; cands.len()];
973        for &(ci, _) in &wanted {
974            group[ci] = usize::from(!cands[ci].converged);
975        }
976        let mut pos_in_order = vec![0usize; cands.len()];
977        for (r, &ci) in order.iter().enumerate() {
978            pos_in_order[ci] = r;
979        }
980        let n_locked_blocks = cands.iter().filter(|c| c.locked).count();
981        let rank: Vec<usize> = (n_locked_blocks..cands.len())
982            .map(|ci| group[ci] * cands.len() + pos_in_order[ci])
983            .collect();
984        let (bl_r, _) = reorder(&mut act.t, &mut act.z, &rank, kp0.saturating_sub(nl), &so);
985        let b_a = act.coupling();
986        // Lock the leading converged wanted blocks whose couplings pass.
987        let mut nl_new = nl;
988        for &(q, s, r) in &bl_r {
989            if r >= cands.len() {
990                break; // group ≥ 1: not converged-wanted
991            }
992            let (re, im) = block_value(&act.t, (q, s));
993            let bn = if s == 1 {
994                b_a[q].abs()
995            } else {
996                hypot(b_a[q], b_a[q + 1])
997            };
998            if !passes(bn, hypot(re, im), &par) {
999                break;
1000            }
1001            nl_new += s;
1002        }
1003        // KS7.
1004        let mut kp = kp0.max(nl_new).min(m - 1);
1005        if kp > nl {
1006            let last = kp - 1 - nl;
1007            if let Some(&(q, s, _)) = bl_r.iter().find(|b| b.0 <= last && last < b.0 + b.1)
1008                && s == 2
1009                && q == last
1010            {
1011                if kp + 1 < m {
1012                    kp += 1;
1013                } else {
1014                    kp -= 1;
1015                }
1016            }
1017        }
1018        let kp = kp.max(nl_new);
1019        let q = kp - nl;
1020        let mut vn = vec![T::ZERO; n * q];
1021        for c in 0..q {
1022            for t in 0..na {
1023                let f = act.z.data[t + c * na];
1024                if is_exact_zero(f) {
1025                    continue;
1026                }
1027                let src = &e.v[(nl + t) * n..(nl + t + 1) * n];
1028                for (o, &x) in vn[c * n..(c + 1) * n].iter_mut().zip(src) {
1029                    *o += x * f;
1030                }
1031            }
1032        }
1033        let last = e.v[m * n..(m + 1) * n].to_vec();
1034        e.v[nl * n..kp * n].copy_from_slice(&vn);
1035        e.v[kp * n..(kp + 1) * n].copy_from_slice(&last);
1036        // KS7′: one Gram–Schmidt sweep over the kept and the residual vectors.
1037        for c in nl..=kp {
1038            let (done, rest) = e.v.split_at_mut(c * n);
1039            let col = &mut rest[..n];
1040            let (nu, _) = orthogonalize_against(done, n, c, col, par.eta);
1041            if !is_exact_zero(nu) {
1042                for x in col.iter_mut() {
1043                    *x = *x / nu;
1044                }
1045            }
1046        }
1047        let hla = if sym { None } else { Some(act.hla()) };
1048        let mut hn = DenseBlock::zeros(m + 1, m);
1049        let ld = m + 1;
1050        for j in 0..nl {
1051            for i in 0..nl {
1052                hn.data[i + j * ld] = e.h.data[e.hi(i, j)];
1053            }
1054        }
1055        if let Some(hla) = &hla {
1056            for c in 0..q {
1057                for i in 0..nl {
1058                    hn.data[i + (nl + c) * ld] = hla.data[i + c * nl];
1059                }
1060            }
1061        }
1062        for c in 0..q {
1063            for i in 0..q {
1064                hn.data[nl + i + (nl + c) * ld] = act.t.data[i + c * na];
1065            }
1066            if nl + c >= nl_new {
1067                hn.data[kp + (nl + c) * ld] = b_a[c];
1068            }
1069        }
1070        e.h = hn;
1071        e.nl = nl_new;
1072        from = kp;
1073        debug_assert!(e.restart_shape(kp), "(K3) after a restart");
1074        #[allow(clippy::cast_precision_loss)]
1075        let k1 = C_K * (m as f64) * T::EPSILON.to_f64() / 2.0;
1076        debug_assert!(
1077            e.orthogonality(kp + 1) <= k1,
1078            "(K1) after a restart: {}",
1079            e.orthogonality(kp + 1)
1080        );
1081    }
1082}
1083
1084impl<T: Real> Engine<T> {
1085    /// KS8: the eigenvectors of the values `take` (candidate, conjugate?).
1086    fn vectors(
1087        &self,
1088        act: &ActiveSchur<T>,
1089        cands: &[Blk<T>],
1090        take: &[(usize, bool)],
1091    ) -> (DenseBlock<T>, DenseBlock<T>) {
1092        let (n, m, nl) = (self.n, self.m, self.nl);
1093        let na = m - nl;
1094        let t = self.full_t(act);
1095        let bl = blocks(&t);
1096        let mut yr = DenseBlock::zeros(n, take.len());
1097        let mut yi = DenseBlock::zeros(n, take.len());
1098        for (col, &(ci, conj)) in take.iter().enumerate() {
1099            let bi = bl.iter().position(|b| b.0 == cands[ci].start).unwrap_or(0);
1100            let x = schur_eigvec(&t, &bl, bi);
1101            // z = blockdiag(I, Z_A) x.
1102            let mut z = vec![Cx::new(T::ZERO, T::ZERO); m];
1103            z[..nl].copy_from_slice(&x[..nl]);
1104            for r in 0..na {
1105                let mut acc = Cx::new(T::ZERO, T::ZERO);
1106                for c in 0..na {
1107                    let f = act.z.data[r + c * na];
1108                    acc = Cx::new(acc.re + f * x[nl + c].re, acc.im + f * x[nl + c].im);
1109                }
1110                z[nl + r] = acc;
1111            }
1112            let (re, im) = (
1113                &mut yr.data[col * n..(col + 1) * n],
1114                &mut yi.data[col * n..(col + 1) * n],
1115            );
1116            for (j, zj) in z.iter().enumerate() {
1117                let vj = &self.v[j * n..(j + 1) * n];
1118                if !is_exact_zero(zj.re) {
1119                    for (o, &x) in re.iter_mut().zip(vj) {
1120                        *o += x * zj.re;
1121                    }
1122                }
1123                if !is_exact_zero(zj.im) {
1124                    for (o, &x) in im.iter_mut().zip(vj) {
1125                        *o += x * zj.im;
1126                    }
1127                }
1128            }
1129            // Normalize in Cⁿ, largest entry real positive, conjugate if asked.
1130            let nr = hypot(norm2(re), norm2(im));
1131            let mut big = 0;
1132            let mut bm = T::ZERO;
1133            for i in 0..n {
1134                let a = hypot(re[i], im[i]);
1135                if lt(bm, a) {
1136                    bm = a;
1137                    big = i;
1138                }
1139            }
1140            let ph = if is_exact_zero(bm) {
1141                Cx::new(T::ONE, T::ZERO)
1142            } else {
1143                Cx::new(re[big] / bm, -im[big] / bm)
1144            };
1145            for i in 0..n {
1146                let w = Cx::new(re[i], im[i]).mul(ph);
1147                re[i] = w.re / nr;
1148                im[i] = if conj { -(w.im / nr) } else { w.im / nr };
1149            }
1150            // A real eigenvalue has a real eigenvector: drop the rounding.
1151            if is_exact_zero(cands[ci].im) {
1152                im.fill(T::ZERO);
1153            }
1154        }
1155        (yr, yi)
1156    }
1157}
1158
1159/// `k` eigenpairs of a symmetric operator (the caller asserts the
1160/// symmetry; it is not checked).
1161///
1162/// Algorithm KS of Chapter 12.6 with the symmetric small solver — the
1163/// thick-restart Lanczos method (Algorithm L of the contract): full DGKS
1164/// reorthogonalization, Jacobi on the projected arrowhead, Krylov–Schur
1165/// truncation with locking, ARPACK's test `ρ ≤ tol·max(ε^{2/3}, |θ|)`.
1166///
1167/// **Acceptance (L3.4):** on symmetric Matrix Market matrices the `k`
1168/// extreme eigenvalues agree with `scipy.sparse.linalg.eigsh` (ARPACK) to
1169/// `1e-10` relative where the eigenvalue gap is `≥ 1e-6 ‖A‖` (S9), and
1170/// every pair has `‖Ay − θy‖ ≤ (tol + c_K·ncv·u) ‖A‖` (`c_K = 8`).
1171///
1172/// # Errors
1173/// [`StatlaError::InvalidArgument`] (not square; `which` not symmetric; `k
1174/// = 0`; `k ≥ n`; `ncv ∉ (k, n]`; `tol < 0` or not finite; `reorth_eta ∉
1175/// (0, 1)`; `v0 = 0`), [`StatlaError::Dimension`] (`v0`),
1176/// [`StatlaError::NonFinite`] (`v0`, or the operator returned NaN/∞),
1177/// [`StatlaError::Operator`], [`StatlaError::NoConvergence`].
1178pub fn eigsh<T, O>(
1179    op: &mut O,
1180    k: usize,
1181    which: Which,
1182    opts: &EigsOptions<T>,
1183) -> Result<SymEigen<T>, StatlaError>
1184where
1185    T: Real,
1186    O: LinearOperator<T> + ?Sized,
1187{
1188    let raw = run(op, k, which, opts, true, false)?;
1189    Ok(sym_result(raw))
1190}
1191
1192fn sym_result<T: Real>(raw: Raw<T>) -> SymEigen<T> {
1193    SymEigen {
1194        values: raw.values.iter().map(|c| c.re).collect(),
1195        vectors: raw.vectors.map(|(r, _)| r),
1196        stats: raw.stats,
1197    }
1198}
1199
1200/// `k` eigenpairs of a general real operator.
1201///
1202/// Algorithm KS of Chapter 12.6 (Krylov–Schur, Stewart 2001; S7): Arnoldi
1203/// with DGKS, real Schur form of the projected matrix by Francis
1204/// double-shift QR, reordering by Bai–Demmel swaps so that the wanted lead
1205/// (conjugate pairs never split), locking and purging by truncation,
1206/// eigenvectors by back substitution in the quasi-triangular form.
1207///
1208/// # Errors
1209/// As [`eigsh()`], with `k ≥ n − 1` invalid (ARPACK's `dnaupd` rule) and the
1210/// `which` set `LM SM LR SR LI SI`.
1211pub fn eigs<T, O>(
1212    op: &mut O,
1213    k: usize,
1214    which: Which,
1215    opts: &EigsOptions<T>,
1216) -> Result<Eigen<T>, StatlaError>
1217where
1218    T: Real,
1219    O: LinearOperator<T> + ?Sized,
1220{
1221    let raw = run(op, k, which, opts, false, false)?;
1222    Ok(gen_result(raw))
1223}
1224
1225fn gen_result<T: Real>(raw: Raw<T>) -> Eigen<T> {
1226    let (vr, vi) = match raw.vectors {
1227        Some((r, i)) => (Some(r), Some(i)),
1228        None => (None, None),
1229    };
1230    Eigen {
1231        values: raw.values,
1232        vectors_re: vr,
1233        vectors_im: vi,
1234        stats: raw.stats,
1235    }
1236}
1237
1238#[cfg(test)]
1239#[allow(clippy::cast_precision_loss, clippy::float_cmp)]
1240mod tests {
1241    use super::*;
1242    use crate::operator::from_fn;
1243    use xingo_extprec::DoubleDouble as Dd;
1244
1245    /// A symmetric `n × n` matrix `Q diag(d) Qᵀ` with three random reflectors.
1246    fn sym_matrix<T: Real>(d: &[f64], seed: u64) -> DenseBlock<T> {
1247        let n = d.len();
1248        let mut a = DenseBlock::<T>::zeros(n, n);
1249        for (i, &x) in d.iter().enumerate() {
1250            a.data[i + i * n] = T::from_f64(x);
1251        }
1252        let mut rng = Rng::new(seed);
1253        for _ in 0..3 {
1254            let w: Vec<T> = (0..n).map(|_| T::from_f64(rng.gaussian())).collect();
1255            let ww = dot(&w, &w);
1256            let two = T::from_f64(2.0);
1257            // A ← H A H.
1258            for j in 0..n {
1259                let col = &mut a.data[j * n..(j + 1) * n];
1260                let f = two * dot(col, &w) / ww;
1261                crate::small::axpy_sub(f, &w, col);
1262            }
1263            for i in 0..n {
1264                let s: T = (0..n).map(|j| a.data[i + j * n] * w[j]).sum();
1265                let f = two * s / ww;
1266                for j in 0..n {
1267                    a.data[i + j * n] -= f * w[j];
1268                }
1269            }
1270        }
1271        // Exact symmetry.
1272        for j in 0..n {
1273            for i in 0..j {
1274                let s = (a.data[i + j * n] + a.data[j + i * n]) * T::from_f64(0.5);
1275                a.data[i + j * n] = s;
1276                a.data[j + i * n] = s;
1277            }
1278        }
1279        a
1280    }
1281
1282    fn residual<T: Real>(a: &DenseBlock<T>, y: &[T], yi: &[T], th: Complex<T>) -> f64 {
1283        let n = a.rows;
1284        let mut r = 0.0f64;
1285        for i in 0..n {
1286            let (mut sr, mut si) = (T::ZERO, T::ZERO);
1287            for j in 0..n {
1288                sr += a.data[i + j * n] * y[j];
1289                si += a.data[i + j * n] * yi[j];
1290            }
1291            let er = sr - (th.re * y[i] - th.im * yi[i]);
1292            let ei = si - (th.re * yi[i] + th.im * y[i]);
1293            r += (er * er + ei * ei).to_f64();
1294        }
1295        r.sqrt()
1296    }
1297
1298    /// (K2) holds after every expansion; restarts and locking happen.
1299    #[test]
1300    fn krylov_relation_holds_after_every_expansion() {
1301        fn k2_of<T: Real>(sym: bool, u: f64) -> f64 {
1302            let d: Vec<f64> = (0..80).map(|j| 1.0 / (1.0 + 0.1 * f64::from(j))).collect();
1303            let mut a = sym_matrix::<T>(&d, 3);
1304            if !sym {
1305                // A nonsymmetric perturbation with complex eigenvalues.
1306                for j in 0..80 {
1307                    for i in 0..j {
1308                        a.data[i + j * 80] += T::from_f64(0.01 * ((i * 7 + j * 3) % 5) as f64);
1309                    }
1310                }
1311            }
1312            let raw = run(
1313                &mut a,
1314                6,
1315                Which::LargestMagnitude,
1316                &EigsOptions::default(),
1317                sym,
1318                true,
1319            )
1320            .unwrap();
1321            assert!(raw.stats.restarts > 0, "the test must restart");
1322            assert!(raw.locked > 0, "the test must lock");
1323            raw.k2 / (20.0 * u)
1324        }
1325        let u64_ = f64::EPSILON / 2.0;
1326        let udd = Dd::EPSILON.to_f64() / 2.0;
1327        let r = [
1328            k2_of::<f64>(true, u64_),
1329            k2_of::<f64>(false, u64_),
1330            k2_of::<Dd>(true, udd),
1331            k2_of::<Dd>(false, udd),
1332        ];
1333        eprintln!("(K2) / (ncv u): {r:.3?}");
1334        assert!(r.iter().all(|&x| x <= C_K), "{r:?}");
1335    }
1336
1337    /// The prescribed spectrum is found, in every `which`, to `ε‖A‖`.
1338    #[test]
1339    fn symmetric_which_set() {
1340        let d: Vec<f64> = (0..60).map(|j| -3.0 + 0.1 * f64::from(j)).collect();
1341        let mut a = sym_matrix::<f64>(&d, 7);
1342        let mut sorted = d.clone();
1343        sorted.sort_by(f64::total_cmp);
1344        let cases: [(Which, Vec<f64>); 5] = [
1345            (Which::LargestAlgebraic, vec![2.9, 2.8, 2.7, 2.6]),
1346            (Which::SmallestAlgebraic, vec![-3.0, -2.9, -2.8, -2.7]),
1347            (Which::LargestMagnitude, vec![-3.0, 2.9, -2.9, 2.8]),
1348            (Which::SmallestMagnitude, vec![0.0, -0.1, 0.1, -0.2]),
1349            (Which::BothEnds, vec![2.9, -3.0, 2.8, -2.9]),
1350        ];
1351        for (w, want) in cases {
1352            let f = eigsh(&mut a, 4, w, &EigsOptions::default()).unwrap();
1353            // Ties in |λ| (±0.1, ±2.9) may come in either order: compare sorted.
1354            let (mut got_s, mut want_s) = (f.values.clone(), want.clone());
1355            if matches!(w, Which::LargestMagnitude | Which::SmallestMagnitude) {
1356                got_s.sort_by(f64::total_cmp);
1357                want_s.sort_by(f64::total_cmp);
1358            }
1359            for (got, exp) in got_s.iter().zip(&want_s) {
1360                assert!((got - exp).abs() < 1e-13, "{w:?}: {:?}", f.values);
1361            }
1362            let y = f.vectors.as_ref().unwrap();
1363            for (c, &th) in f.values.iter().enumerate() {
1364                let col = &y.data[c * 60..(c + 1) * 60];
1365                let r = residual(&a, col, &[0.0; 60], Complex { re: th, im: 0.0 });
1366                assert!(r < 1e-13, "{w:?} {c}: {r}");
1367            }
1368        }
1369    }
1370
1371    /// A block-diagonal matrix of rotations-and-scalings: conjugate pairs,
1372    /// `+i` first, adjacent; residuals small; every `which`.
1373    #[test]
1374    fn general_which_set_and_pairs() {
1375        let n = 40;
1376        let mut a = DenseBlock::<f64>::zeros(n, n);
1377        // Blocks [r cosφ, −r sinφ; r sinφ, r cosφ] and real diagonal entries.
1378        let mut exact: Vec<(f64, f64)> = Vec::new();
1379        let mut i = 0;
1380        let mut t = 0;
1381        while i < n {
1382            if t % 3 == 0 && i + 1 < n {
1383                let (re, im) = (0.5 + 0.07 * f64::from(t), 0.2 + 0.05 * f64::from(t));
1384                a.data[i + i * n] = re;
1385                a.data[(i + 1) + (i + 1) * n] = re;
1386                a.data[i + (i + 1) * n] = -im;
1387                a.data[(i + 1) + i * n] = im;
1388                exact.push((re, im));
1389                exact.push((re, -im));
1390                i += 2;
1391            } else {
1392                let re = -1.0 + 0.09 * f64::from(t);
1393                a.data[i + i * n] = re;
1394                exact.push((re, 0.0));
1395                i += 1;
1396            }
1397            t += 1;
1398        }
1399        // Similarity by a fixed orthogonal-ish mixing (a reflector).
1400        let w: Vec<f64> = (0..n).map(|j| 1.0 + (j % 7) as f64).collect();
1401        let ww = dot(&w, &w);
1402        for j in 0..n {
1403            let col = &mut a.data[j * n..(j + 1) * n];
1404            let f = 2.0 * dot(col, &w) / ww;
1405            crate::small::axpy_sub(f, &w, col);
1406        }
1407        for r in 0..n {
1408            let s: f64 = (0..n).map(|j| a.data[r + j * n] * w[j]).sum();
1409            let f = 2.0 * s / ww;
1410            for j in 0..n {
1411                a.data[r + j * n] -= f * w[j];
1412            }
1413        }
1414        for which in [
1415            Which::LargestMagnitude,
1416            Which::SmallestMagnitude,
1417            Which::LargestReal,
1418            Which::SmallestReal,
1419            Which::LargestImag,
1420            Which::SmallestImag,
1421        ] {
1422            let f = eigs(&mut a, 5, which, &EigsOptions::default()).unwrap();
1423            assert_eq!(f.values.len(), 5);
1424            let yr = f.vectors_re.as_ref().unwrap();
1425            let yi = f.vectors_im.as_ref().unwrap();
1426            for (c, th) in f.values.iter().enumerate() {
1427                let r = residual(
1428                    &a,
1429                    &yr.data[c * n..(c + 1) * n],
1430                    &yi.data[c * n..(c + 1) * n],
1431                    *th,
1432                );
1433                assert!(r < 1e-12, "{which:?} {c}: {r}");
1434                assert!(
1435                    exact
1436                        .iter()
1437                        .any(|e| (e.0 - th.re).abs() < 1e-12 && (e.1 - th.im).abs() < 1e-12),
1438                    "{which:?}: {th:?}"
1439                );
1440                if th.im > 0.0 && c + 1 < f.values.len() {
1441                    assert_eq!(f.values[c + 1].re, th.re);
1442                    assert_eq!(f.values[c + 1].im, -th.im);
1443                }
1444                assert!(th.im >= 0.0 || (c > 0 && f.values[c - 1].im == -th.im));
1445            }
1446            // The order of `which`.
1447            for w2 in f.values.windows(2) {
1448                let (a0, b0) = ((w2[0].re, w2[0].im.abs()), (w2[1].re, w2[1].im.abs()));
1449                assert!(!before(which, b0, a0), "{which:?}: {:?}", f.values);
1450            }
1451        }
1452    }
1453
1454    #[test]
1455    fn arpack_codes_round_trip() {
1456        for c in ["LM", "SM", "LA", "SA", "BE", "LR", "SR", "LI", "SI"] {
1457            assert_eq!(Which::from_arpack(c).unwrap().arpack_code(), c);
1458        }
1459        assert_eq!(Which::from_arpack("lm"), None);
1460        assert_eq!(Which::from_arpack("XX"), None);
1461        let e = eps23::<f64>();
1462        let r = (e / f64::EPSILON.powf(2.0 / 3.0) - 1.0).abs();
1463        assert!(r < 1e-14, "{e} {r}");
1464    }
1465
1466    #[test]
1467    #[allow(clippy::too_many_lines)] // one assertion per error path
1468    fn options_and_errors() {
1469        let d: Vec<f64> = (0..10).map(f64::from).collect();
1470        let mut a = sym_matrix::<f64>(&d, 1);
1471        let o = EigsOptions::<f64>::default();
1472        let inv = |r: Result<SymEigen<f64>, StatlaError>| {
1473            matches!(r, Err(StatlaError::InvalidArgument { .. }))
1474        };
1475        assert!(inv(eigsh(&mut a, 0, Which::LargestMagnitude, &o)));
1476        assert!(inv(eigsh(&mut a, 10, Which::LargestMagnitude, &o)));
1477        assert!(inv(eigsh(&mut a, 2, Which::LargestReal, &o)));
1478        assert!(matches!(
1479            eigs(&mut a, 9, Which::LargestMagnitude, &o),
1480            Err(StatlaError::InvalidArgument { .. })
1481        ));
1482        assert!(matches!(
1483            eigs(&mut a, 2, Which::BothEnds, &o),
1484            Err(StatlaError::InvalidArgument { .. })
1485        ));
1486        for bad in [
1487            EigsOptions {
1488                ncv: Some(2),
1489                ..o.clone()
1490            },
1491            EigsOptions {
1492                ncv: Some(11),
1493                ..o.clone()
1494            },
1495            EigsOptions {
1496                tol: -1.0,
1497                ..o.clone()
1498            },
1499            EigsOptions {
1500                tol: f64::INFINITY,
1501                ..o.clone()
1502            },
1503            EigsOptions {
1504                reorth_eta: 1.0,
1505                ..o.clone()
1506            },
1507            EigsOptions {
1508                v0: Some(vec![0.0; 10]),
1509                ..o.clone()
1510            },
1511        ] {
1512            assert!(
1513                inv(eigsh(&mut a, 2, Which::LargestMagnitude, &bad)),
1514                "{bad:?}"
1515            );
1516        }
1517        assert!(matches!(
1518            eigsh(
1519                &mut a,
1520                2,
1521                Which::LargestMagnitude,
1522                &EigsOptions {
1523                    v0: Some(vec![1.0; 3]),
1524                    ..o.clone()
1525                }
1526            ),
1527            Err(StatlaError::Dimension { what: "v0", .. })
1528        ));
1529        assert!(matches!(
1530            eigsh(
1531                &mut a,
1532                2,
1533                Which::LargestMagnitude,
1534                &EigsOptions {
1535                    v0: Some(vec![f64::NAN; 10]),
1536                    ..o.clone()
1537                }
1538            ),
1539            Err(StatlaError::NonFinite {
1540                what: "v0",
1541                index: 0
1542            })
1543        ));
1544        let mut rect = DenseBlock::<f64>::zeros(4, 3);
1545        assert!(matches!(
1546            eigsh(&mut rect, 1, Which::LargestMagnitude, &o),
1547            Err(StatlaError::InvalidArgument { .. })
1548        ));
1549        // Operator failure and NaN output.
1550        let mut failing = from_fn(10, 10, |_x: &[f64], _y: &mut [f64]| {
1551            Err(crate::OperatorError {
1552                message: "boom".into(),
1553            })
1554        });
1555        assert!(matches!(
1556            eigsh(&mut failing, 2, Which::LargestMagnitude, &o),
1557            Err(StatlaError::Operator(_))
1558        ));
1559        let mut nan = from_fn(10, 10, |_x: &[f64], y: &mut [f64]| {
1560            y.fill(f64::NAN);
1561            Ok(())
1562        });
1563        assert!(matches!(
1564            eigs(&mut nan, 2, Which::LargestMagnitude, &o),
1565            Err(StatlaError::NonFinite { .. })
1566        ));
1567        // Restart limit: NoConvergence, or partial.
1568        let dd: Vec<f64> = (0..200).map(|j| 1.0 + 1e-3 * f64::from(j)).collect();
1569        let mut slow = sym_matrix::<f64>(&dd, 5);
1570        let lim = EigsOptions {
1571            max_restarts: Some(1),
1572            ..o.clone()
1573        };
1574        assert!(matches!(
1575            eigsh(&mut slow, 6, Which::SmallestMagnitude, &lim),
1576            Err(StatlaError::NoConvergence { requested: 6, .. })
1577        ));
1578        let part = eigsh(
1579            &mut slow,
1580            6,
1581            Which::SmallestMagnitude,
1582            &EigsOptions {
1583                allow_partial: true,
1584                ..lim
1585            },
1586        )
1587        .unwrap();
1588        assert!(part.values.len() < 6);
1589        assert_eq!(part.stats.converged, part.values.len());
1590        // ncv = n: one pass, exact; vectors off.
1591        let f = eigsh(
1592            &mut a,
1593            3,
1594            Which::LargestAlgebraic,
1595            &EigsOptions {
1596                ncv: Some(10),
1597                vectors: false,
1598                ..o
1599            },
1600        )
1601        .unwrap();
1602        assert_eq!(f.stats.restarts, 0);
1603        assert!(f.vectors.is_none());
1604        for (g, e) in f.values.iter().zip([9.0, 8.0, 7.0]) {
1605            assert!((g - e).abs() < 1e-13);
1606        }
1607    }
1608
1609    /// Determinism: the same bits twice; an invariant start vector
1610    /// (an eigenvector) breaks down and recovers from the seed's stream.
1611    #[test]
1612    fn reproducible_and_breakdown_safe() {
1613        let d: Vec<f64> = (0..30).map(|j| f64::from(j % 10)).collect();
1614        let mut a = DenseBlock::<f64>::zeros(30, 30);
1615        for (i, &x) in d.iter().enumerate() {
1616            a.data[i + i * 30] = x;
1617        }
1618        let mut e0 = vec![0.0; 30];
1619        e0[3] = 1.0;
1620        let o = EigsOptions {
1621            v0: Some(e0),
1622            ..EigsOptions::default()
1623        };
1624        let f = eigsh(&mut a, 3, Which::LargestAlgebraic, &o).unwrap();
1625        for g in &f.values {
1626            assert!((g - 9.0).abs() < 1e-14, "{:?}", f.values);
1627        }
1628        let g = eigsh(&mut a, 3, Which::LargestAlgebraic, &o).unwrap();
1629        assert_eq!(
1630            f.values.iter().map(|x| x.to_bits()).collect::<Vec<_>>(),
1631            g.values.iter().map(|x| x.to_bits()).collect::<Vec<_>>()
1632        );
1633    }
1634}