Skip to main content

xingo_statla/
shift_invert.rs

1//! # Chapter 12.6.2 — Shift-invert: `eigsh_near` over `SupernodalLdl`, `eigs_near` over `Lu`
2//!
3//! ## Purpose
4//! *The `k` eigenvalues nearest a shift `σ`.* Krylov methods find the ends
5//! of the spectrum quickly and the interior slowly; ARPACK's mode 3 for the
6//! standard problem runs them on `(A − σI)⁻¹`, whose largest eigenvalues
7//! `ν = 1/(λ − σ)` are the `λ` nearest `σ`. The factorization comes from
8//! `xingo-sparse`: the threshold LU (`Lu<T>`) for a general `A`, and the
9//! supernodal `LBLᵀ` (`SupernodalLdl<T, K>`, Bunch–Kaufman pivoting,
10//! no regularization) for a symmetric one — whose **inertia** counts, by
11//! Sylvester's law, the eigenvalues of `A` below `σ`: a check of
12//! completeness that ARPACK does not offer ([`SymShiftInvert::count_below`]).
13//!
14//! ## Notation
15//! `A ∈ R^{n×n}` sparse (CSC); `σ` the real shift; `M = A − σI`; `ν` the
16//! eigenvalues of `M⁻¹`; `In(M) = (n₊, n₋, n₀)` its inertia.
17//!
18//! ## Algorithm SI (symmetric, [`eigsh_near`])
19//! SI1. \[Check.\] `A` square and structurally valid, entries and `σ`
20//!      finite; the arguments of [`crate::eigsh()`] are validated first.
21//! SI2. \[Form.\] The lower triangle of `M` (entries `a_ij`, `i ≥ j`, of the
22//!      input — only the lower triangle is read — with `σ` subtracted on the
23//!      diagonal; an entry that becomes exactly zero is not stored, as the
24//!      CSC invariant requires, and the analysis adds the structural
25//!      diagonal).
26//! SI3. \[Factorize.\] Analyze with the crate's own AMD and factorize by the
27//!      `LBLᵀ` path of `SupernodalLdl` (no regularization: `Regularization::
28//!      none()` on an augmented form). That path checks the inertia against
29//!      the form's (`KktForm::Augmented { n_primal, n_dual }` expects
30//!      `(n_dual, n_primal, 0)`), and the inertia of `M` is not known in
31//!      advance: the first attempt declares `(n, 0, 0)` (right whenever
32//!      `σ` is below the spectrum); on `WrongInertia { found }` with `found.zero
33//!      = 0` the analysis and the factorization are repeated with
34//!      `n_primal = found.negative` — at most two factorizations. A zero
35//!      pivot (`found.zero > 0`, or `ZeroPivot`) means `σ` is numerically an
36//!      eigenvalue: [`StatlaError::Kkt`].
37//! SI4. \[Count.\] `count_below = n₋`, the eigenvalues of `A` strictly below
38//!      `σ` (Sylvester; exact for the computed factorization, i.e. for a
39//!      matrix within the backward error of `LBLᵀ` from `M`).
40//! SI5. \[Iterate.\] [`crate::eigsh()`] with `LM` on `x ↦ M⁻¹x`, each
41//!      application by Algorithm R below (two solves and one product with
42//!      `M`).
43//! SI6. \[Map back.\] `λ = σ + 1/ν`; the order (largest `|ν|` first) is
44//!      nearest `σ` first; the eigenvectors are those of `M⁻¹`.
45//!
46//! ## Algorithm SG (general, [`eigs_near`])
47//! SG1–SG2 as SI1–SI2 on the whole of `M`. SG3: `Lu<T>` with
48//! `LuOptions::for_scalar::<T>()` (the defaults of `xingo-sparse`; `M`
49//! is the "basis" whose columns are those of `M`); singular is
50//! [`StatlaError::Lu`]. SG5: [`crate::eigs()`] with `LM` on `x ↦ M⁻¹x`
51//! (`ftran`: row-indexed in, column-indexed out; Algorithm R). SG6: `λ = σ + 1/ν`
52//! computed by complex division. `1/ν` *conjugates the imaginary part's
53//! sign*, so a pair `ν, ν̄` (`+i` first) maps to `λ̄, λ`: the two values,
54//! and the imaginary parts of their vectors, are swapped back to keep the
55//! `+i` member first; a lone `k`-th member is replaced by its conjugate.
56//!
57//! ## Algorithm R (one step of iterative refinement per application)
58//! *Task L3.4, second round (answer to question Q-L34-4).* Both operators
59//! apply `x ↦ M⁻¹x` as
60//! R1. \[Solve.\] `y ← F⁻¹x` with the factorization `F ≈ M` (LU `ftran`, or
61//!     the `LBLᵀ` solve).
62//! R2. \[Residual.\] `r ← x − M y`, in the scalar `T`, with the stored `M`
63//!     (the whole `A − σI` for the LU; its lower triangle, applied
64//!     symmetrically, for the `LBLᵀ`).
65//! R3. \[Correct.\] `y ← y + F⁻¹r`.
66//!
67//! *What it guarantees.* Without R2–R3 the computed `y` solves `(M + δM) y
68//! = x` with `‖δM‖` the backward error of the factorization, which for a
69//! threshold LU (`rel_pivot_tol = 0.01`) or a Bunch–Kaufman `LBLᵀ` carries
70//! the element growth, `γ·u·‖M‖` with `γ` up to hundreds — and that, not
71//! the convergence tolerance, bounded the residual on `A` (measured `114·ncv
72//! ·u‖A‖` for `eigs_near`, `4.75` for `eigsh_near`, task L3.4 first round).
73//! One step of refinement **in the working precision** makes the solve
74//! backward stable with `‖δM‖ = O(n_row · u · ‖M‖)` (componentwise, the row
75//! counts of `M`), provided `γ·κ(M)·u` is well below one (Skeel 1980;
76//! Higham, *Accuracy and Stability*, ch. 12: fixed-precision refinement
77//! improves the *backward* error, not the forward one). That is what the
78//! residual on `A` needs: for a converged pair, `‖A y − λ y‖ = ‖M y − y/ν‖ ≤
79//! ‖M‖·ρ_ν/|ν| + ‖δM‖`, so a residual in `T` suffices; a residual in higher
80//! precision would improve the forward error of each solve, which the
81//! eigenvalue problem does not need (the error along the wanted eigenvector
82//! is harmless, as in ARPACK's mode 3). It does **not** remove the
83//! dependence on `κ(M)`: for `σ` within `γ·u·‖M‖` of an eigenvalue one step
84//! may not suffice (and the factorization would usually have failed with
85//! a zero pivot). *Measured* (`l34-tables.md`): with R2–R3 the residual on
86//! `A` satisfies the criterion of `eigsh`/`eigs`, `≤ (τ + c_K·ncv·u)‖A‖`, on
87//! every fixture.
88//!
89//! *Cost.* Per application one more solve and one sparse product with `M`
90//! (`2·nnz(M)` flops; the solves dominate), and the `n`-vectors `r`, `d`
91//! kept in the operator; the stored `M` doubles the matrix memory.
92//!
93//! ## Invariants
94//! (I1) `count_below + n₀ + n₊ = n` with `n₀ = 0` for every operator built.
95//! (I2) The applications solve `M y = x` with backward error `η = ‖x −
96//!      My‖_∞/(‖M‖_∞‖y‖_∞) = O(u)` after Algorithm R (measured `≤ 0.73u`
97//!      on the fixtures, against up to `526u` without it; tested `≤ 2u` by
98//!      `tests/arpack.rs`).
99//! (I4) Algorithm R runs on every application (one refinement step, never
100//!      more, never skipped: the results are reproducible bit for bit).
101//! (I3) `eigsh_near`/`eigs_near` return exactly the values `σ + 1/ν` of the
102//!      pairs `eigsh`/`eigs` returned on `M⁻¹`, in that order (up to the swap
103//!      of SG6 inside a pair).
104//!
105//! ## References
106//! Lehoucq, Sorensen & Yang, *ARPACK Users' Guide* (1998), mode 3;
107//! Parlett, *The Symmetric Eigenvalue Problem* (1998), §3.3 (Sylvester's
108//! inertia and spectrum slicing); Ericsson & Ruhe, "The spectral
109//! transformation Lanczos method", Math. Comp. 35 (1980); Chapters 5.15–5.16
110//! of `xingo-sparse` (`LBLᵀ`, Bunch–Kaufman). Cited from memory.
111
112use xingo_sparse::{
113    Amd, Col, CscMatrix, DenseKernel, KktError, KktForm, KktSolver, LuError, LuFactor, LuOptions,
114    NaiveDense, NumericLdl, Real, Regularization, SparseVec, SupernodalLdl, SupernodalOptions,
115};
116
117use crate::StatlaError;
118use crate::eigs::{Complex, Eigen, EigsOptions, SymEigen, Which, eigs, eigsh, validate_for};
119use crate::operator::{LinearOperator, OperatorError};
120use crate::real::{is_exact_zero, lt};
121use crate::schur::Cx;
122
123/// `j` as a `u32` index (a valid `CscMatrix` has dimensions `≤ u32::MAX`,
124/// checked by `check_invariants` before any use).
125fn idx32(j: usize) -> u32 {
126    u32::try_from(j).unwrap_or(u32::MAX)
127}
128
129/// Step R2: `r ← r − M y`, with `m` the whole `M` or (`symmetric`) its
130/// lower triangle applied as the symmetric matrix it stands for.
131fn sub_product<T: Real>(m: &CscMatrix<T>, y: &[T], r: &mut [T], symmetric: bool) {
132    for j in 0..m.n_cols() {
133        let (rows, vals) = m.col(Col::from_usize(j));
134        let yj = y[j];
135        let mut acc = T::ZERO;
136        for (&i, &v) in rows.iter().zip(vals) {
137            let iu = i as usize;
138            r[iu] -= v * yj;
139            if symmetric && iu != j {
140                acc += v * y[iu];
141            }
142        }
143        if symmetric {
144            r[j] -= acc;
145        }
146    }
147}
148
149/// The length check of an application of a shift-invert operator.
150fn check_apply(n: usize, x: usize, y: usize) -> Result<(), OperatorError> {
151    if x == n && y == n {
152        Ok(())
153    } else {
154        Err(OperatorError {
155            message: "shift-invert: x and y must have the order of A".to_owned(),
156        })
157    }
158}
159
160/// SI1/SG1 (after the structure check): square, finite entries and shift.
161fn check_input<T: Real>(a: &CscMatrix<T>, sigma: T) -> Result<usize, StatlaError> {
162    if a.n_rows() != a.n_cols() {
163        return Err(StatlaError::InvalidArgument {
164            what: "shift-invert: A is not square",
165        });
166    }
167    if let Some(index) = a.val.iter().position(|v| !v.is_finite()) {
168        return Err(StatlaError::NonFinite { what: "a", index });
169    }
170    if !sigma.is_finite() {
171        return Err(StatlaError::NonFinite {
172            what: "sigma",
173            index: 0,
174        });
175    }
176    Ok(a.n_cols())
177}
178
179/// SI2/SG2: `A − σI`, the whole matrix or its lower triangle.
180fn shifted<T: Real>(a: &CscMatrix<T>, sigma: T, lower_only: bool) -> CscMatrix<T> {
181    let n = a.n_cols();
182    let mut col_ptr = Vec::with_capacity(n + 1);
183    let mut row_idx = Vec::with_capacity(a.nnz() + n);
184    let mut val = Vec::with_capacity(a.nnz() + n);
185    col_ptr.push(0);
186    // An exact zero is not stored (invariant of `CscMatrix`): a diagonal
187    // entry that cancels, or `−σ` for `σ = 0`.
188    let push = |i: u32, v: T, row_idx: &mut Vec<u32>, val: &mut Vec<T>| {
189        if !is_exact_zero(v) {
190            row_idx.push(i);
191            val.push(v);
192        }
193    };
194    for j in 0..n {
195        let (rows, vals) = a.col(Col::from_usize(j));
196        let mut diag_done = false;
197        for (&i, &v) in rows.iter().zip(vals) {
198            let iu = i as usize;
199            if lower_only && iu < j {
200                continue;
201            }
202            if iu > j && !diag_done {
203                push(idx32(j), -sigma, &mut row_idx, &mut val);
204                diag_done = true;
205            }
206            if iu == j {
207                push(i, v - sigma, &mut row_idx, &mut val);
208                diag_done = true;
209            } else {
210                push(i, v, &mut row_idx, &mut val);
211            }
212        }
213        if !diag_done {
214            push(idx32(j), -sigma, &mut row_idx, &mut val);
215        }
216        col_ptr.push(row_idx.len());
217    }
218    CscMatrix {
219        n_rows: n,
220        col_ptr,
221        row_idx,
222        val,
223    }
224}
225
226/// `x ↦ (A − σI)⁻¹ x` for a square sparse `A`, by the threshold LU of
227/// `xingo-sparse` (`Lu<T>` over the columns of `A − σI`, factorized once),
228/// with one step of iterative refinement per application (Algorithm R: two
229/// solves and one product with `A − σI`, which the operator keeps). The
230/// operator of [`eigs_near`] (Algorithm SG of Chapter 12.6.2).
231#[derive(Debug)]
232pub struct ShiftInvert<T: Real = f64> {
233    sigma: T,
234    n: usize,
235    lu: xingo_sparse::Lu<T>,
236    work: SparseVec<T>,
237    /// `M = A − σI` (Algorithm R).
238    m: CscMatrix<T>,
239    /// The residual `r` of step R2.
240    r: Vec<T>,
241    /// The correction `d = F⁻¹r` of step R3.
242    d: Vec<T>,
243}
244
245impl<T: Real> ShiftInvert<T> {
246    /// Factorize `A − σI`.
247    ///
248    /// # Errors
249    /// [`StatlaError::InvalidArgument`] (not square; options outside the
250    /// domain `xingo-sparse` asserts), [`StatlaError::NonFinite`] (`a`,
251    /// `sigma`), [`StatlaError::Lu`] (a structurally invalid `a`, or
252    /// singular: `σ` is, numerically, an eigenvalue).
253    pub fn new(a: &CscMatrix<T>, sigma: T, opts: LuOptions) -> Result<Self, StatlaError> {
254        let n = check_input(a, sigma)?;
255        a.check_invariants()
256            .map_err(|e| StatlaError::Lu(LuError::Structure(e)))?;
257        let fin = |x: f64| x.is_finite() && !lt(x, 0.0);
258        if opts.search_limit == 0
259            || !lt(0.0, opts.rel_pivot_tol)
260            || lt(1.0, opts.rel_pivot_tol)
261            || !fin(opts.abs_pivot_tol)
262            || !fin(opts.drop_tol)
263            || !fin(opts.update_stability_tol)
264            || !lt(0.0, opts.update_multiplier_limit)
265        {
266            return Err(StatlaError::InvalidArgument {
267                what: "ShiftInvert: LuOptions outside their domain",
268            });
269        }
270        let m = shifted(a, sigma, false);
271        let mut lu = xingo_sparse::Lu::<T>::new(opts);
272        lu.factorize(&m).map_err(StatlaError::Lu)?;
273        Ok(Self {
274            sigma,
275            n,
276            lu,
277            work: SparseVec::new(n),
278            m,
279            r: vec![T::ZERO; n],
280            d: vec![T::ZERO; n],
281        })
282    }
283
284    /// The shift.
285    pub fn sigma(&self) -> T {
286        self.sigma
287    }
288}
289
290impl<T: Real> LinearOperator<T> for ShiftInvert<T> {
291    fn nrows(&self) -> usize {
292        self.n
293    }
294    fn ncols(&self) -> usize {
295        self.n
296    }
297    fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
298        check_apply(self.n, x.len(), y.len())?;
299        // R1.
300        self.lu_solve(x, y);
301        // R2.
302        self.r.copy_from_slice(x);
303        sub_product(&self.m, y, &mut self.r, false);
304        // R3.
305        let (r, mut d) = (core::mem::take(&mut self.r), core::mem::take(&mut self.d));
306        self.lu_solve(&r, &mut d);
307        for (yi, &di) in y.iter_mut().zip(&d) {
308            *yi += di;
309        }
310        (self.r, self.d) = (r, d);
311        Ok(())
312    }
313}
314
315impl<T: Real> ShiftInvert<T> {
316    /// `y ← F⁻¹x` by `ftran` (row-indexed in, column-indexed out).
317    fn lu_solve(&mut self, x: &[T], y: &mut [T]) {
318        self.work = SparseVec::from_dense(x);
319        self.lu.ftran(&mut self.work);
320        for (i, yi) in y.iter_mut().enumerate() {
321            *yi = self.work.get(idx32(i));
322        }
323    }
324}
325
326/// `x ↦ (A − σI)⁻¹ x` for a symmetric sparse `A` (lower triangle read), by
327/// `SupernodalLdl<T, K>` with no regularization; the inertia of `A − σI`
328/// is kept: by Sylvester's law it counts the eigenvalues below `σ`
329/// ([`SymShiftInvert::count_below`]) — a check ARPACK does not offer. Each
330/// application refines once (Algorithm R: two solves and one product with
331/// the kept lower triangle of `A − σI`). The operator of [`eigsh_near`]
332/// (Algorithm SI of Chapter 12.6.2).
333#[derive(Debug)]
334pub struct SymShiftInvert<T: Real = f64, K: DenseKernel<T> = NaiveDense> {
335    sigma: T,
336    n: usize,
337    below: usize,
338    ldl: SupernodalLdl<T, K>,
339    num: NumericLdl<T>,
340    /// The lower triangle of `M = A − σI` (Algorithm R).
341    low: CscMatrix<T>,
342    /// The residual `r` of step R2.
343    r: Vec<T>,
344}
345
346impl<T: Real, K: DenseKernel<T>> SymShiftInvert<T, K> {
347    /// Analyze (own AMD ordering) and factorize `A − σI`.
348    ///
349    /// # Errors
350    /// [`StatlaError::InvalidArgument`] (not square), [`StatlaError::NonFinite`]
351    /// (`a`, `sigma`), [`StatlaError::Kkt`] (a structurally invalid `a`; a
352    /// zero pivot: `σ` is numerically an eigenvalue).
353    pub fn new(a: &CscMatrix<T>, sigma: T, kernel: K) -> Result<Self, StatlaError> {
354        let n = check_input(a, sigma)?;
355        a.check_invariants()
356            .map_err(|e| StatlaError::Kkt(KktError::Structure(e)))?;
357        let low = shifted(a, sigma, true);
358        let ldl = SupernodalLdl::new(kernel, SupernodalOptions::default());
359        let pattern = low.pattern();
360        let attempt = |n_primal: usize| {
361            let form = KktForm::Augmented {
362                n_primal,
363                n_dual: n - n_primal,
364            };
365            let sym = ldl.analyze(&pattern, form, &Amd::default())?;
366            ldl.factorize(&sym, &low, Regularization::none())
367        };
368        // SI3.
369        let (num, inertia) = match attempt(0) {
370            Ok(r) => r,
371            Err(KktError::WrongInertia { found, .. }) if found.zero == 0 => {
372                attempt(found.negative).map_err(StatlaError::Kkt)?
373            }
374            Err(e) => return Err(StatlaError::Kkt(e)),
375        };
376        debug_assert_eq!(
377            inertia.positive + inertia.negative + inertia.zero,
378            n,
379            "(I1) the inertia counts every pivot"
380        );
381        Ok(Self {
382            sigma,
383            n,
384            below: inertia.negative,
385            ldl,
386            num,
387            low,
388            r: vec![T::ZERO; n],
389        })
390    }
391
392    /// The shift.
393    pub fn sigma(&self) -> T {
394        self.sigma
395    }
396
397    /// Number of eigenvalues of `A` strictly below `σ` (negative inertia of
398    /// `A − σI`).
399    #[must_use]
400    pub fn count_below(&self) -> usize {
401        self.below
402    }
403}
404
405impl<T: Real, K: DenseKernel<T>> LinearOperator<T> for SymShiftInvert<T, K> {
406    fn nrows(&self) -> usize {
407        self.n
408    }
409    fn ncols(&self) -> usize {
410        self.n
411    }
412    fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
413        check_apply(self.n, x.len(), y.len())?;
414        // R1.
415        y.copy_from_slice(x);
416        self.ldl.solve(&self.num, y);
417        // R2.
418        self.r.copy_from_slice(x);
419        sub_product(&self.low, y, &mut self.r, true);
420        // R3.
421        self.ldl.solve(&self.num, &mut self.r);
422        for (yi, &di) in y.iter_mut().zip(&self.r) {
423            *yi += di;
424        }
425        Ok(())
426    }
427}
428
429/// The `k` eigenvalues of the symmetric `A` nearest `σ`: [`eigsh()`] with
430/// `LargestMagnitude` on [`SymShiftInvert`], mapped back by `λ = σ + 1/ν`
431/// (ARPACK mode 3 for the standard problem), nearest first. Returns also
432/// [`SymShiftInvert::count_below`]. Only the lower triangle of `a` is read.
433///
434/// # Errors
435/// As [`eigsh()`] and [`SymShiftInvert::new`].
436pub fn eigsh_near<T: Real>(
437    a: &CscMatrix<T>,
438    k: usize,
439    sigma: T,
440    opts: &EigsOptions<T>,
441) -> Result<(SymEigen<T>, usize), StatlaError> {
442    validate_for(
443        a.n_rows(),
444        a.n_cols(),
445        k,
446        Which::LargestMagnitude,
447        opts,
448        true,
449    )?;
450    let mut op = SymShiftInvert::<T, NaiveDense>::new(a, sigma, NaiveDense)?;
451    let below = op.count_below();
452    let mut f = eigsh(&mut op, k, Which::LargestMagnitude, opts)?;
453    // SI6.
454    for v in &mut f.values {
455        *v = sigma + T::ONE / *v;
456    }
457    Ok((f, below))
458}
459
460/// The `k` eigenvalues of the general `A` nearest the real shift `σ`, by
461/// [`eigs()`] on [`ShiftInvert`] (`LuOptions::for_scalar::<T>()`), mapped
462/// back by `λ = σ + 1/ν`, nearest first; conjugate pairs keep the `+i`
463/// member first.
464///
465/// # Errors
466/// As [`eigs()`] and [`ShiftInvert::new`].
467pub fn eigs_near<T: Real>(
468    a: &CscMatrix<T>,
469    k: usize,
470    sigma: T,
471    opts: &EigsOptions<T>,
472) -> Result<Eigen<T>, StatlaError> {
473    validate_for(
474        a.n_rows(),
475        a.n_cols(),
476        k,
477        Which::LargestMagnitude,
478        opts,
479        false,
480    )?;
481    let mut op = ShiftInvert::new(a, sigma, LuOptions::for_scalar::<T>())?;
482    let mut f = eigs(&mut op, k, Which::LargestMagnitude, opts)?;
483    // SG6.
484    let n = a.n_rows();
485    let len = f.values.len();
486    let one = Cx::new(T::ONE, T::ZERO);
487    let mapped: Vec<Complex<T>> = f
488        .values
489        .iter()
490        .map(|nu| {
491            let w = one.div(Cx::new(nu.re, nu.im));
492            Complex {
493                re: sigma + w.re,
494                im: w.im,
495            }
496        })
497        .collect();
498    let mut i = 0;
499    while i < len {
500        let nu = f.values[i];
501        if lt(T::ZERO, nu.im) {
502            let paired = i + 1 < len && f.values[i + 1].re == nu.re && f.values[i + 1].im == -nu.im;
503            if paired {
504                f.values[i] = Complex {
505                    re: mapped[i].re,
506                    im: -mapped[i].im,
507                };
508                f.values[i + 1] = mapped[i];
509                if let Some(vi) = &mut f.vectors_im {
510                    for r in 0..n {
511                        vi.data.swap(r + i * n, r + (i + 1) * n);
512                    }
513                }
514                i += 2;
515                continue;
516            }
517            // A lone `+i` member: its conjugate.
518            f.values[i] = Complex {
519                re: mapped[i].re,
520                im: -mapped[i].im,
521            };
522            if let Some(vi) = &mut f.vectors_im {
523                for v in &mut vi.data[i * n..(i + 1) * n] {
524                    *v = -*v;
525                }
526            }
527        } else {
528            f.values[i] = mapped[i];
529            if is_exact_zero(nu.im) {
530                f.values[i].im = T::ZERO;
531            }
532        }
533        i += 1;
534    }
535    Ok(f)
536}
537
538#[cfg(test)]
539#[allow(
540    clippy::cast_precision_loss,
541    clippy::float_cmp,
542    clippy::cast_possible_truncation
543)]
544mod tests {
545    use super::*;
546    use xingo_sparse::Triplets;
547
548    /// The tridiagonal `tridiag(−1, 2, −1)` of order `n`, full or lower.
549    fn lap1d(n: usize, lower: bool) -> CscMatrix<f64> {
550        let mut t = Triplets::new(n, n);
551        for i in 0..n {
552            t.push(i as u32, i as u32, 2.0);
553            if i + 1 < n {
554                t.push((i + 1) as u32, i as u32, -1.0);
555                if !lower {
556                    t.push(i as u32, (i + 1) as u32, -1.0);
557                }
558            }
559        }
560        t.to_csc().unwrap()
561    }
562
563    fn exact(n: usize) -> Vec<f64> {
564        (1..=n)
565            .map(|j| 2.0 - 2.0 * (j as f64 * core::f64::consts::PI / (n as f64 + 1.0)).cos())
566            .collect()
567    }
568
569    #[test]
570    fn count_below_and_nearest_values() {
571        let n = 50;
572        let lam = exact(n);
573        for lower in [true, false] {
574            let a = lap1d(n, lower);
575            for sigma in [-0.5, 0.3, 1.01, 2.05, 3.9, 4.5] {
576                let (f, below) = eigsh_near(&a, 4, sigma, &EigsOptions::default())
577                    .unwrap_or_else(|e| panic!("lower {lower} sigma {sigma}: {e:?}"));
578                assert_eq!(below, lam.iter().filter(|&&l| l < sigma).count(), "{sigma}");
579                let mut near = lam.clone();
580                near.sort_by(|x, y| (x - sigma).abs().total_cmp(&(y - sigma).abs()));
581                for (g, e) in f.values.iter().zip(&near) {
582                    assert!((g - e).abs() < 1e-12, "{sigma}: {:?} {near:?}", f.values);
583                }
584            }
585        }
586        // σ an eigenvalue: λ_17 = 2 − 2cos(π/3) = 1 for n = 50, and λ_3 = 2
587        // for n = 5 — a zero pivot, an error.
588        assert!(matches!(
589            eigsh_near(&lap1d(50, true), 4, 1.0, &EigsOptions::default()),
590            Err(StatlaError::Kkt(_))
591        ));
592        let a = lap1d(5, true);
593        assert!(matches!(
594            SymShiftInvert::<f64>::new(&a, 2.0, NaiveDense),
595            Err(StatlaError::Kkt(_))
596        ));
597        assert!(matches!(
598            ShiftInvert::new(&lap1d(5, false), 2.0, LuOptions::default()),
599            Err(StatlaError::Lu(_))
600        ));
601    }
602
603    #[test]
604    fn general_shift_invert_maps_pairs_back() {
605        // Block diagonal: rotation-scalings and reals; σ near a pair.
606        let blocks = [(1.0, 0.5), (2.0, 0.25), (3.0, 0.0), (0.5, 0.0), (2.2, 1.0)];
607        let mut t = Triplets::new(8, 8);
608        let mut r = 0u32;
609        for &(re, im) in &blocks {
610            if im == 0.0 {
611                t.push(r, r, re);
612                r += 1;
613            } else {
614                t.push(r, r, re);
615                t.push(r + 1, r + 1, re);
616                t.push(r, r + 1, -im);
617                t.push(r + 1, r, im);
618                r += 2;
619            }
620        }
621        let a = t.to_csc().unwrap();
622        let f = eigs_near(&a, 3, 1.9, &EigsOptions::default()).unwrap();
623        let want = [(2.0, 0.25), (2.0, -0.25), (1.0, 0.5)];
624        for (g, w) in f.values.iter().zip(want) {
625            assert!(
626                (g.re - w.0).abs() < 1e-12 && (g.im - w.1).abs() < 1e-12,
627                "{:?}",
628                f.values
629            );
630        }
631        // Residuals with the returned vectors (A dense here).
632        let yr = f.vectors_re.as_ref().unwrap();
633        let yi = f.vectors_im.as_ref().unwrap();
634        let mut dense = [[0.0; 8]; 8];
635        for j in 0..8 {
636            let (rows, vals) = a.col(Col::from_usize(j));
637            for (&i, &v) in rows.iter().zip(vals) {
638                dense[i as usize][j] = v;
639            }
640        }
641        for (c, th) in f.values.iter().enumerate() {
642            let (y, z) = (&yr.data[c * 8..(c + 1) * 8], &yi.data[c * 8..(c + 1) * 8]);
643            let mut e = 0.0f64;
644            for i in 0..8 {
645                let (mut sr, mut si) = (0.0, 0.0);
646                for j in 0..8 {
647                    sr += dense[i][j] * y[j];
648                    si += dense[i][j] * z[j];
649                }
650                e = e
651                    .max((sr - (th.re * y[i] - th.im * z[i])).abs())
652                    .max((si - (th.re * z[i] + th.im * y[i])).abs());
653            }
654            assert!(e < 1e-12, "{c}: {e}");
655        }
656    }
657
658    #[test]
659    fn errors_are_returned() {
660        let a = lap1d(6, true);
661        let o = EigsOptions::<f64>::default();
662        let rect = CscMatrix::<f64>::zeros(3, 4);
663        assert!(matches!(
664            eigsh_near(&rect, 1, 0.0, &o),
665            Err(StatlaError::InvalidArgument { .. })
666        ));
667        assert!(matches!(
668            eigs_near(&rect, 1, 0.0, &o),
669            Err(StatlaError::InvalidArgument { .. })
670        ));
671        assert!(matches!(
672            SymShiftInvert::<f64>::new(&rect, 0.0, NaiveDense),
673            Err(StatlaError::InvalidArgument { .. })
674        ));
675        assert!(matches!(
676            eigsh_near(&a, 0, 0.0, &o),
677            Err(StatlaError::InvalidArgument { .. })
678        ));
679        assert!(matches!(
680            eigsh_near(&a, 2, f64::NAN, &o),
681            Err(StatlaError::NonFinite { what: "sigma", .. })
682        ));
683        let mut bad = a.clone();
684        bad.val[0] = f64::INFINITY;
685        assert!(matches!(
686            eigsh_near(&bad, 2, 0.0, &o),
687            Err(StatlaError::NonFinite {
688                what: "a",
689                index: 0
690            })
691        ));
692        let mut broken = a.clone();
693        broken.row_idx[0] = 99;
694        assert!(matches!(
695            eigsh_near(&broken, 2, 0.0, &o),
696            Err(StatlaError::Kkt(KktError::Structure(_)))
697        ));
698        assert!(matches!(
699            eigs_near(&broken, 2, 0.0, &o),
700            Err(StatlaError::Lu(LuError::Structure(_)))
701        ));
702        let lo = LuOptions {
703            rel_pivot_tol: 0.0,
704            ..LuOptions::default()
705        };
706        assert!(matches!(
707            ShiftInvert::new(&lap1d(6, false), 0.0, lo),
708            Err(StatlaError::InvalidArgument { .. })
709        ));
710        // Wrong lengths in an application.
711        let mut op = SymShiftInvert::<f64>::new(&a, 0.1, NaiveDense).unwrap();
712        assert!(op.apply(&[1.0; 5], &mut [0.0; 6]).is_err());
713        let mut op = ShiftInvert::new(&lap1d(6, false), 0.1, LuOptions::default()).unwrap();
714        assert!(op.apply(&[1.0; 6], &mut [0.0; 7]).is_err());
715        assert_eq!(op.sigma(), 0.1);
716    }
717}