1use 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
178pub(crate) const C_K: f64 = 8.0;
181
182#[derive(Clone, Copy, Debug, Default, PartialEq)]
186pub struct Complex<T: Real = f64> {
187 pub re: T,
189 pub im: T,
191}
192
193#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
199#[non_exhaustive]
200pub enum Which {
201 LargestMagnitude,
203 SmallestMagnitude,
206 LargestAlgebraic,
208 SmallestAlgebraic,
210 BothEnds,
213 LargestReal,
215 SmallestReal,
217 LargestImag,
219 SmallestImag,
221}
222
223impl Which {
224 #[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 #[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#[derive(Clone, Debug, PartialEq)]
284pub struct EigsOptions<T: Real = f64> {
285 pub ncv: Option<usize>,
288 pub tol: f64,
292 pub max_restarts: Option<usize>,
294 pub v0: Option<Vec<T>>,
297 pub seed: u64,
300 pub reorth_eta: f64,
302 pub vectors: bool,
305 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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
328#[non_exhaustive]
329pub struct EigsStats {
330 pub restarts: usize,
332 pub applies: usize,
334 pub reorthogonalizations: usize,
336 pub converged: usize,
338}
339
340#[derive(Clone, Debug)]
342#[non_exhaustive]
343pub struct SymEigen<T: Real = f64> {
344 pub values: Vec<T>,
346 pub vectors: Option<DenseBlock<T>>,
349 pub stats: EigsStats,
351}
352
353#[derive(Clone, Debug)]
358#[non_exhaustive]
359pub struct Eigen<T: Real = f64> {
360 pub values: Vec<Complex<T>>,
362 pub vectors_re: Option<DenseBlock<T>>,
365 pub vectors_im: Option<DenseBlock<T>>,
367 pub stats: EigsStats,
369}
370
371struct 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
384fn 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
396fn 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
452pub(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
465fn 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
478fn 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
495fn 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 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#[derive(Clone, Copy, Debug)]
538struct Blk<T> {
539 start: usize,
541 size: usize,
542 re: T,
543 im: T,
544 locked: bool,
545 converged: bool,
546}
547
548struct Engine<T: Real> {
550 n: usize,
551 m: usize,
552 sym: bool,
553 v: Vec<T>,
555 h: DenseBlock<T>,
557 nl: usize,
559 anorm: T,
561 rng: Rng,
562 stats: EigsStats,
563 #[cfg(test)]
564 k2: Option<f64>,
565}
566
567struct ActiveSchur<T: Real> {
569 t: DenseBlock<T>,
571 z: DenseBlock<T>,
573 c0: Vec<T>,
575 hla0: DenseBlock<T>,
577}
578
579impl<T: Real> ActiveSchur<T> {
580 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 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 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 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 #[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 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 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 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 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; }
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 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
800fn passes<T: Real>(rho: T, abs: T, p: &Params<T>) -> bool {
802 le_exact(rho, p.tol * p.eps23.max(abs))
803}
804
805struct 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#[allow(clippy::too_many_lines)] fn 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 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 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 let mut act = e.active_schur(&so)?;
871 let nl = e.nl;
872 let na = m - nl;
873 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 let mut wanted: Vec<(usize, bool)> = Vec::with_capacity(k); 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 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 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 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 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 let mut nl_new = nl;
988 for &(q, s, r) in &bl_r {
989 if r >= cands.len() {
990 break; }
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 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 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 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 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 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 if is_exact_zero(cands[ci].im) {
1152 im.fill(T::ZERO);
1153 }
1154 }
1155 (yr, yi)
1156 }
1157}
1158
1159pub 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
1200pub 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 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 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 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 #[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 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 #[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 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 #[test]
1374 fn general_which_set_and_pairs() {
1375 let n = 40;
1376 let mut a = DenseBlock::<f64>::zeros(n, n);
1377 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 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 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)] 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 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 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 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 #[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}