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}