use xingo_sparse::{DenseBlock, Real};
use crate::StatlaError;
use crate::error::op_err;
use crate::krylov::{expand_arnoldi, kept_dimension};
use crate::operator::LinearOperator;
use crate::random::Rng;
use crate::real::{is_exact_zero, le_exact, lt};
use crate::schur::{
Cx, SchurOptions, block_value, blocks, hypot, identity, real_schur, reorder, schur_eigvec,
sym_eig,
};
use crate::small::{check_finite, check_len, dot, norm2, orthogonalize_against};
pub(crate) const C_K: f64 = 8.0;
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct Complex<T: Real = f64> {
pub re: T,
pub im: T,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum Which {
LargestMagnitude,
SmallestMagnitude,
LargestAlgebraic,
SmallestAlgebraic,
BothEnds,
LargestReal,
SmallestReal,
LargestImag,
SmallestImag,
}
impl Which {
#[must_use]
pub fn from_arpack(code: &str) -> Option<Self> {
Some(match code {
"LM" => Self::LargestMagnitude,
"SM" => Self::SmallestMagnitude,
"LA" => Self::LargestAlgebraic,
"SA" => Self::SmallestAlgebraic,
"BE" => Self::BothEnds,
"LR" => Self::LargestReal,
"SR" => Self::SmallestReal,
"LI" => Self::LargestImag,
"SI" => Self::SmallestImag,
_ => return None,
})
}
#[must_use]
pub fn arpack_code(self) -> &'static str {
match self {
Self::LargestMagnitude => "LM",
Self::SmallestMagnitude => "SM",
Self::LargestAlgebraic => "LA",
Self::SmallestAlgebraic => "SA",
Self::BothEnds => "BE",
Self::LargestReal => "LR",
Self::SmallestReal => "SR",
Self::LargestImag => "LI",
Self::SmallestImag => "SI",
}
}
fn symmetric_ok(self) -> bool {
matches!(
self,
Self::LargestMagnitude
| Self::SmallestMagnitude
| Self::LargestAlgebraic
| Self::SmallestAlgebraic
| Self::BothEnds
)
}
fn general_ok(self) -> bool {
matches!(
self,
Self::LargestMagnitude
| Self::SmallestMagnitude
| Self::LargestReal
| Self::SmallestReal
| Self::LargestImag
| Self::SmallestImag
)
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct EigsOptions<T: Real = f64> {
pub ncv: Option<usize>,
pub tol: f64,
pub max_restarts: Option<usize>,
pub v0: Option<Vec<T>>,
pub seed: u64,
pub reorth_eta: f64,
pub vectors: bool,
pub allow_partial: bool,
}
impl<T: Real> Default for EigsOptions<T> {
fn default() -> Self {
Self {
ncv: None,
tol: 0.0,
max_restarts: None,
v0: None,
seed: 0,
reorth_eta: core::f64::consts::FRAC_1_SQRT_2,
vectors: true,
allow_partial: false,
}
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct EigsStats {
pub restarts: usize,
pub applies: usize,
pub reorthogonalizations: usize,
pub converged: usize,
}
#[derive(Clone, Debug)]
#[non_exhaustive]
pub struct SymEigen<T: Real = f64> {
pub values: Vec<T>,
pub vectors: Option<DenseBlock<T>>,
pub stats: EigsStats,
}
#[derive(Clone, Debug)]
#[non_exhaustive]
pub struct Eigen<T: Real = f64> {
pub values: Vec<Complex<T>>,
pub vectors_re: Option<DenseBlock<T>>,
pub vectors_im: Option<DenseBlock<T>>,
pub stats: EigsStats,
}
struct Params<T> {
ncv: usize,
tol: T,
eta: T,
eps23: T,
max_restarts: usize,
}
fn invalid(what: &'static str) -> StatlaError {
StatlaError::InvalidArgument { what }
}
fn eps23<T: Real>() -> T {
let a = T::EPSILON * T::EPSILON;
let (two, three) = (T::from_f64(2.0), T::from_f64(3.0));
let mut y = T::ONE;
for _ in 0..300 {
y = (two * y + a / (y * y)) / three;
}
y
}
fn validate<T: Real>(
rows: usize,
cols: usize,
k: usize,
which: Which,
o: &EigsOptions<T>,
symmetric: bool,
) -> Result<Params<T>, StatlaError> {
if rows != cols {
return Err(invalid("eigs/eigsh: the operator is not square"));
}
let n = rows;
if symmetric && !which.symmetric_ok() {
return Err(invalid("eigsh: which must be one of LM SM LA SA BE"));
}
if !symmetric && !which.general_ok() {
return Err(invalid("eigs: which must be one of LM SM LR SR LI SI"));
}
if symmetric && (k == 0 || k >= n) {
return Err(invalid("eigsh: k must satisfy 1 <= k < n"));
}
if !symmetric && (k == 0 || k + 1 >= n) {
return Err(invalid("eigs: k must satisfy 1 <= k < n - 1"));
}
let ncv = o.ncv.unwrap_or_else(|| n.min((2 * k + 1).max(20)));
if ncv <= k || ncv > n {
return Err(invalid("eigs/eigsh: ncv must satisfy k < ncv <= n"));
}
if !o.tol.is_finite() || lt(o.tol, 0.0) {
return Err(invalid("eigs/eigsh: tol must be finite and >= 0"));
}
if !o.reorth_eta.is_finite() || !lt(0.0, o.reorth_eta) || !lt(o.reorth_eta, 1.0) {
return Err(invalid("eigs/eigsh: reorth_eta must lie in (0, 1)"));
}
if let Some(v0) = &o.v0 {
check_len("v0", n, v0.len())?;
check_finite("v0", v0)?;
if is_exact_zero(norm2(v0)) {
return Err(invalid("eigs/eigsh: v0 is the zero vector"));
}
}
let tol = if is_exact_zero(o.tol) {
T::EPSILON
} else {
T::from_f64(o.tol)
};
Ok(Params {
ncv,
tol,
eta: T::from_f64(o.reorth_eta),
eps23: eps23::<T>(),
max_restarts: o.max_restarts.unwrap_or_else(|| n.saturating_mul(10)),
})
}
pub(crate) fn validate_for<T: Real>(
rows: usize,
cols: usize,
k: usize,
which: Which,
o: &EigsOptions<T>,
symmetric: bool,
) -> Result<(), StatlaError> {
validate(rows, cols, k, which, o, symmetric).map(|_| ())
}
fn before<T: Real>(which: Which, a: (T, T), b: (T, T)) -> bool {
match which {
Which::LargestMagnitude => lt(hypot(b.0, b.1), hypot(a.0, a.1)),
Which::SmallestMagnitude => lt(hypot(a.0, a.1), hypot(b.0, b.1)),
Which::LargestAlgebraic | Which::LargestReal | Which::BothEnds => lt(b.0, a.0),
Which::SmallestAlgebraic | Which::SmallestReal => lt(a.0, b.0),
Which::LargestImag => lt(b.1.abs(), a.1.abs()),
Which::SmallestImag => lt(a.1.abs(), b.1.abs()),
}
}
fn tie_break(which: Which) -> Which {
match which {
Which::LargestMagnitude => Which::LargestReal,
Which::SmallestMagnitude => Which::SmallestReal,
Which::LargestReal | Which::LargestImag | Which::LargestAlgebraic | Which::BothEnds => {
Which::LargestMagnitude
}
Which::SmallestReal | Which::SmallestImag | Which::SmallestAlgebraic => {
Which::SmallestMagnitude
}
}
}
fn rank_blocks<T: Real>(which: Which, vals: &[(T, T)]) -> Vec<usize> {
let mut idx: Vec<usize> = (0..vals.len()).collect();
let key = if which == Which::BothEnds {
Which::LargestAlgebraic
} else {
which
};
let second = tie_break(which);
let cmp = |w: Which, a: (T, T), b: (T, T)| {
if before(w, a, b) {
core::cmp::Ordering::Less
} else if before(w, b, a) {
core::cmp::Ordering::Greater
} else {
core::cmp::Ordering::Equal
}
};
idx.sort_by(|&i, &j| cmp(key, vals[i], vals[j]).then_with(|| cmp(second, vals[i], vals[j])));
if which != Which::BothEnds {
return idx;
}
let mut out = Vec::with_capacity(idx.len());
let (mut lo, mut hi) = (0usize, idx.len());
let mut high = true;
while lo < hi {
if high {
out.push(idx[lo]);
lo += 1;
} else {
hi -= 1;
out.push(idx[hi]);
}
high = !high;
}
out
}
#[derive(Clone, Copy, Debug)]
struct Blk<T> {
start: usize,
size: usize,
re: T,
im: T,
locked: bool,
converged: bool,
}
struct Engine<T: Real> {
n: usize,
m: usize,
sym: bool,
v: Vec<T>,
h: DenseBlock<T>,
nl: usize,
anorm: T,
rng: Rng,
stats: EigsStats,
#[cfg(test)]
k2: Option<f64>,
}
struct ActiveSchur<T: Real> {
t: DenseBlock<T>,
z: DenseBlock<T>,
c0: Vec<T>,
hla0: DenseBlock<T>,
}
impl<T: Real> ActiveSchur<T> {
fn coupling(&self) -> Vec<T> {
let na = self.z.rows;
(0..na)
.map(|c| dot(&self.c0, &self.z.data[c * na..(c + 1) * na]))
.collect()
}
fn hla(&self) -> DenseBlock<T> {
let (nl, na) = (self.hla0.rows, self.z.rows);
let mut out = DenseBlock::zeros(nl, na);
for c in 0..na {
for t in 0..na {
let f = self.z.data[t + c * na];
if is_exact_zero(f) {
continue;
}
for r in 0..nl {
out.data[r + c * nl] += self.hla0.data[r + t * nl] * f;
}
}
}
out
}
}
impl<T: Real> Engine<T> {
#[inline]
fn hi(&self, i: usize, j: usize) -> usize {
i + j * (self.m + 1)
}
fn expand_from<O: LinearOperator<T> + ?Sized>(
&mut self,
op: &mut O,
from: usize,
eta: T,
) -> Result<(), StatlaError> {
let (n, m) = (self.n, self.m);
let mut w = vec![T::ZERO; n];
let mut col = vec![T::ZERO; m + 1];
for j in from..m {
op.apply(&self.v[j * n..(j + 1) * n], &mut w)
.map_err(op_err)?;
self.stats.applies += 1;
check_finite("operator output", &w)?;
self.anorm = self.anorm.max(norm2(&w));
col.fill(T::ZERO);
let floor = T::EPSILON * self.anorm;
let beta = expand_arnoldi(
&self.v,
n,
j + 1,
&mut w,
&mut col[..=j],
eta,
floor,
&mut self.rng,
&mut self.stats.reorthogonalizations,
);
for i in 0..=j {
let at = self.hi(i, j);
self.h.data[at] = col[i];
}
for i in j + 1..=m {
let at = self.hi(i, j);
self.h.data[at] = T::ZERO;
}
let at = self.hi(j + 1, j);
self.h.data[at] = beta;
if self.sym {
for i in 0..j {
let (up, low) = (self.hi(i, j), self.hi(j, i));
self.h.data[up] = self.h.data[low];
}
}
self.v[(j + 1) * n..(j + 2) * n].copy_from_slice(&w);
}
Ok(())
}
#[cfg(test)]
fn relations<O: LinearOperator<T> + ?Sized>(&self, op: &mut O) -> f64 {
let (n, m) = (self.n, self.m);
let mut worst = 0.0f64;
let mut y = vec![T::ZERO; n];
for j in 0..m {
op.apply(&self.v[j * n..(j + 1) * n], &mut y).unwrap();
for i in 0..=m {
let f = self.h.data[self.hi(i, j)];
crate::small::axpy_sub(f, &self.v[i * n..(i + 1) * n], &mut y);
}
worst = worst.max(norm2(&y).to_f64());
}
worst / self.anorm.to_f64().max(f64::MIN_POSITIVE)
}
fn active_schur(&self, so: &SchurOptions<T>) -> Result<ActiveSchur<T>, StatlaError> {
let (m, nl) = (self.m, self.nl);
let na = m - nl;
let mut ha = DenseBlock::zeros(na, na);
for j in 0..na {
for i in 0..na {
ha.data[i + j * na] = self.h.data[self.hi(nl + i, nl + j)];
}
}
let c0: Vec<T> = (0..na).map(|j| self.h.data[self.hi(m, nl + j)]).collect();
let mut hla0 = DenseBlock::zeros(nl, na);
if !self.sym {
for j in 0..na {
for i in 0..nl {
hla0.data[i + j * nl] = self.h.data[self.hi(i, nl + j)];
}
}
}
let (t, z) = if self.sym {
let (d, z) = sym_eig(&ha, so)?;
let mut t = DenseBlock::zeros(na, na);
for (i, &di) in d.iter().enumerate() {
t.data[i + i * na] = di;
}
(t, z)
} else {
let mut z = identity::<T>(na);
real_schur(&mut ha, &mut z, so)?;
(ha, z)
};
Ok(ActiveSchur { t, z, c0, hla0 })
}
fn s_ll(&self) -> DenseBlock<T> {
let nl = self.nl;
let mut s = DenseBlock::zeros(nl, nl);
for j in 0..nl {
for i in 0..nl {
s.data[i + j * nl] = self.h.data[self.hi(i, j)];
}
}
s
}
fn full_t(&self, a: &ActiveSchur<T>) -> DenseBlock<T> {
let (m, nl) = (self.m, self.nl);
let na = m - nl;
let mut t = DenseBlock::zeros(m, m);
let s = self.s_ll();
for j in 0..nl {
for i in 0..nl {
t.data[i + j * m] = s.data[i + j * nl];
}
}
if !self.sym {
let hla = a.hla();
for j in 0..na {
for i in 0..nl {
t.data[i + (nl + j) * m] = hla.data[i + j * nl];
}
}
}
for j in 0..na {
for i in 0..na {
t.data[nl + i + (nl + j) * m] = a.t.data[i + j * na];
}
}
t
}
fn orthogonality(&self, j: usize) -> f64 {
let n = self.n;
let mut e = 0.0f64;
for a in 0..j {
for c in 0..=a {
let d = dot(&self.v[a * n..(a + 1) * n], &self.v[c * n..(c + 1) * n]);
if a == c && is_exact_zero(d) {
continue; }
let t = if a == c { d - T::ONE } else { d };
e = e.max(t.abs().to_f64());
}
}
e
}
fn restart_shape(&self, kp: usize) -> bool {
let (m, nl) = (self.m, self.nl);
for j in 0..m {
for i in 0..=m {
let v = self.h.data[self.hi(i, j)];
if is_exact_zero(v) {
continue;
}
let ok = if j >= kp || (i > kp) || (i != kp && i > j + 1) {
false
} else if i == kp {
j >= nl
} else if i == j + 1 {
!self.sym
} else {
!self.sym || i == j
};
if !ok {
return false;
}
}
}
true
}
}
fn passes<T: Real>(rho: T, abs: T, p: &Params<T>) -> bool {
le_exact(rho, p.tol * p.eps23.max(abs))
}
struct Raw<T: Real> {
values: Vec<Complex<T>>,
vectors: Option<(DenseBlock<T>, DenseBlock<T>)>,
stats: EigsStats,
#[cfg_attr(not(test), allow(dead_code))]
k2: f64,
#[cfg_attr(not(test), allow(dead_code))]
locked: usize,
}
#[allow(clippy::too_many_lines)] fn run<T, O>(
op: &mut O,
k: usize,
which: Which,
opts: &EigsOptions<T>,
sym: bool,
paranoid: bool,
) -> Result<Raw<T>, StatlaError>
where
T: Real,
O: LinearOperator<T> + ?Sized,
{
let par = validate(op.nrows(), op.ncols(), k, which, opts, sym)?;
let n = op.nrows();
let m = par.ncv;
let so = SchurOptions::<T>::new();
let _ = paranoid;
let mut rng = Rng::new(opts.seed);
let mut v = vec![T::ZERO; n * (m + 1)];
match &opts.v0 {
Some(v0) => v[..n].copy_from_slice(v0),
None => rng.fill(crate::Sketch::Gaussian, &mut v[..n]),
}
let nv = norm2(&v[..n]);
for x in &mut v[..n] {
*x = *x / nv;
}
let mut e = Engine {
n,
m,
sym,
v,
h: DenseBlock::zeros(m + 1, m),
nl: 0,
anorm: T::ZERO,
rng,
stats: EigsStats::default(),
#[cfg(test)]
k2: None,
};
let mut from = 0;
loop {
e.expand_from(op, from, par.eta)?;
#[cfg(test)]
if paranoid {
let g = e.relations(op);
e.k2 = Some(e.k2.map_or(g, |h: f64| h.max(g)));
}
let mut act = e.active_schur(&so)?;
let nl = e.nl;
let na = m - nl;
let s_ll = e.s_ll();
let mut cands: Vec<Blk<T>> = Vec::new();
for (q, s) in blocks(&s_ll) {
let (re, im) = block_value(&s_ll, (q, s));
cands.push(Blk {
start: q,
size: s,
re,
im,
locked: true,
converged: true,
});
}
let bl_a = blocks(&act.t);
let b_a = act.coupling();
for (bi, &(q, s)) in bl_a.iter().enumerate() {
let (re, im) = block_value(&act.t, (q, s));
let x = schur_eigvec(&act.t, &bl_a, bi);
let mut acc = Cx::new(T::ZERO, T::ZERO);
let mut xn2 = T::ZERO;
for (i, xi) in x.iter().enumerate() {
acc = Cx::new(acc.re + b_a[i] * xi.re, acc.im + b_a[i] * xi.im);
xn2 += xi.re * xi.re + xi.im * xi.im;
}
let rho = hypot(acc.re, acc.im) / xn2.sqrt();
cands.push(Blk {
start: nl + q,
size: s,
re,
im,
locked: false,
converged: passes(rho, hypot(re, im), &par),
});
}
let vals: Vec<(T, T)> = cands.iter().map(|c| (c.re, c.im)).collect();
let order = rank_blocks(which, &vals);
let mut wanted: Vec<(usize, bool)> = Vec::with_capacity(k); for &ci in &order {
if wanted.len() == k {
break;
}
wanted.push((ci, false));
if cands[ci].size == 2 && wanted.len() < k {
wanted.push((ci, true));
}
}
let n_conv = wanted.iter().filter(|w| cands[w.0].converged).count();
let limit = e.stats.restarts >= par.max_restarts;
if n_conv == k || limit {
if n_conv < k && !opts.allow_partial {
return Err(StatlaError::NoConvergence {
requested: k,
converged: n_conv,
restarts: e.stats.restarts,
});
}
let take: Vec<(usize, bool)> = wanted
.iter()
.copied()
.filter(|w| cands[w.0].converged)
.collect();
let values: Vec<Complex<T>> = take
.iter()
.map(|&(ci, conj)| Complex {
re: cands[ci].re,
im: if conj { -cands[ci].im } else { cands[ci].im },
})
.collect();
let vectors = if opts.vectors {
Some(e.vectors(&act, &cands, &take))
} else {
None
};
let mut stats = e.stats;
stats.converged = values.len();
#[cfg(test)]
let k2 = e.k2.unwrap_or(0.0);
#[cfg(not(test))]
let k2 = 0.0;
return Ok(Raw {
values,
vectors,
stats,
k2,
locked: e.nl,
});
}
e.stats.restarts += 1;
let n_conv_active = wanted
.iter()
.filter(|w| !cands[w.0].locked && cands[w.0].converged)
.count();
let kp0 = kept_dimension(k, m, n_conv, nl + n_conv_active);
let mut group = vec![2usize; cands.len()];
for &(ci, _) in &wanted {
group[ci] = usize::from(!cands[ci].converged);
}
let mut pos_in_order = vec![0usize; cands.len()];
for (r, &ci) in order.iter().enumerate() {
pos_in_order[ci] = r;
}
let n_locked_blocks = cands.iter().filter(|c| c.locked).count();
let rank: Vec<usize> = (n_locked_blocks..cands.len())
.map(|ci| group[ci] * cands.len() + pos_in_order[ci])
.collect();
let (bl_r, _) = reorder(&mut act.t, &mut act.z, &rank, kp0.saturating_sub(nl), &so);
let b_a = act.coupling();
let mut nl_new = nl;
for &(q, s, r) in &bl_r {
if r >= cands.len() {
break; }
let (re, im) = block_value(&act.t, (q, s));
let bn = if s == 1 {
b_a[q].abs()
} else {
hypot(b_a[q], b_a[q + 1])
};
if !passes(bn, hypot(re, im), &par) {
break;
}
nl_new += s;
}
let mut kp = kp0.max(nl_new).min(m - 1);
if kp > nl {
let last = kp - 1 - nl;
if let Some(&(q, s, _)) = bl_r.iter().find(|b| b.0 <= last && last < b.0 + b.1)
&& s == 2
&& q == last
{
if kp + 1 < m {
kp += 1;
} else {
kp -= 1;
}
}
}
let kp = kp.max(nl_new);
let q = kp - nl;
let mut vn = vec![T::ZERO; n * q];
for c in 0..q {
for t in 0..na {
let f = act.z.data[t + c * na];
if is_exact_zero(f) {
continue;
}
let src = &e.v[(nl + t) * n..(nl + t + 1) * n];
for (o, &x) in vn[c * n..(c + 1) * n].iter_mut().zip(src) {
*o += x * f;
}
}
}
let last = e.v[m * n..(m + 1) * n].to_vec();
e.v[nl * n..kp * n].copy_from_slice(&vn);
e.v[kp * n..(kp + 1) * n].copy_from_slice(&last);
for c in nl..=kp {
let (done, rest) = e.v.split_at_mut(c * n);
let col = &mut rest[..n];
let (nu, _) = orthogonalize_against(done, n, c, col, par.eta);
if !is_exact_zero(nu) {
for x in col.iter_mut() {
*x = *x / nu;
}
}
}
let hla = if sym { None } else { Some(act.hla()) };
let mut hn = DenseBlock::zeros(m + 1, m);
let ld = m + 1;
for j in 0..nl {
for i in 0..nl {
hn.data[i + j * ld] = e.h.data[e.hi(i, j)];
}
}
if let Some(hla) = &hla {
for c in 0..q {
for i in 0..nl {
hn.data[i + (nl + c) * ld] = hla.data[i + c * nl];
}
}
}
for c in 0..q {
for i in 0..q {
hn.data[nl + i + (nl + c) * ld] = act.t.data[i + c * na];
}
if nl + c >= nl_new {
hn.data[kp + (nl + c) * ld] = b_a[c];
}
}
e.h = hn;
e.nl = nl_new;
from = kp;
debug_assert!(e.restart_shape(kp), "(K3) after a restart");
#[allow(clippy::cast_precision_loss)]
let k1 = C_K * (m as f64) * T::EPSILON.to_f64() / 2.0;
debug_assert!(
e.orthogonality(kp + 1) <= k1,
"(K1) after a restart: {}",
e.orthogonality(kp + 1)
);
}
}
impl<T: Real> Engine<T> {
fn vectors(
&self,
act: &ActiveSchur<T>,
cands: &[Blk<T>],
take: &[(usize, bool)],
) -> (DenseBlock<T>, DenseBlock<T>) {
let (n, m, nl) = (self.n, self.m, self.nl);
let na = m - nl;
let t = self.full_t(act);
let bl = blocks(&t);
let mut yr = DenseBlock::zeros(n, take.len());
let mut yi = DenseBlock::zeros(n, take.len());
for (col, &(ci, conj)) in take.iter().enumerate() {
let bi = bl.iter().position(|b| b.0 == cands[ci].start).unwrap_or(0);
let x = schur_eigvec(&t, &bl, bi);
let mut z = vec![Cx::new(T::ZERO, T::ZERO); m];
z[..nl].copy_from_slice(&x[..nl]);
for r in 0..na {
let mut acc = Cx::new(T::ZERO, T::ZERO);
for c in 0..na {
let f = act.z.data[r + c * na];
acc = Cx::new(acc.re + f * x[nl + c].re, acc.im + f * x[nl + c].im);
}
z[nl + r] = acc;
}
let (re, im) = (
&mut yr.data[col * n..(col + 1) * n],
&mut yi.data[col * n..(col + 1) * n],
);
for (j, zj) in z.iter().enumerate() {
let vj = &self.v[j * n..(j + 1) * n];
if !is_exact_zero(zj.re) {
for (o, &x) in re.iter_mut().zip(vj) {
*o += x * zj.re;
}
}
if !is_exact_zero(zj.im) {
for (o, &x) in im.iter_mut().zip(vj) {
*o += x * zj.im;
}
}
}
let nr = hypot(norm2(re), norm2(im));
let mut big = 0;
let mut bm = T::ZERO;
for i in 0..n {
let a = hypot(re[i], im[i]);
if lt(bm, a) {
bm = a;
big = i;
}
}
let ph = if is_exact_zero(bm) {
Cx::new(T::ONE, T::ZERO)
} else {
Cx::new(re[big] / bm, -im[big] / bm)
};
for i in 0..n {
let w = Cx::new(re[i], im[i]).mul(ph);
re[i] = w.re / nr;
im[i] = if conj { -(w.im / nr) } else { w.im / nr };
}
if is_exact_zero(cands[ci].im) {
im.fill(T::ZERO);
}
}
(yr, yi)
}
}
pub fn eigsh<T, O>(
op: &mut O,
k: usize,
which: Which,
opts: &EigsOptions<T>,
) -> Result<SymEigen<T>, StatlaError>
where
T: Real,
O: LinearOperator<T> + ?Sized,
{
let raw = run(op, k, which, opts, true, false)?;
Ok(sym_result(raw))
}
fn sym_result<T: Real>(raw: Raw<T>) -> SymEigen<T> {
SymEigen {
values: raw.values.iter().map(|c| c.re).collect(),
vectors: raw.vectors.map(|(r, _)| r),
stats: raw.stats,
}
}
pub fn eigs<T, O>(
op: &mut O,
k: usize,
which: Which,
opts: &EigsOptions<T>,
) -> Result<Eigen<T>, StatlaError>
where
T: Real,
O: LinearOperator<T> + ?Sized,
{
let raw = run(op, k, which, opts, false, false)?;
Ok(gen_result(raw))
}
fn gen_result<T: Real>(raw: Raw<T>) -> Eigen<T> {
let (vr, vi) = match raw.vectors {
Some((r, i)) => (Some(r), Some(i)),
None => (None, None),
};
Eigen {
values: raw.values,
vectors_re: vr,
vectors_im: vi,
stats: raw.stats,
}
}
#[cfg(test)]
#[allow(clippy::cast_precision_loss, clippy::float_cmp)]
mod tests {
use super::*;
use crate::operator::from_fn;
use xingo_extprec::DoubleDouble as Dd;
fn sym_matrix<T: Real>(d: &[f64], seed: u64) -> DenseBlock<T> {
let n = d.len();
let mut a = DenseBlock::<T>::zeros(n, n);
for (i, &x) in d.iter().enumerate() {
a.data[i + i * n] = T::from_f64(x);
}
let mut rng = Rng::new(seed);
for _ in 0..3 {
let w: Vec<T> = (0..n).map(|_| T::from_f64(rng.gaussian())).collect();
let ww = dot(&w, &w);
let two = T::from_f64(2.0);
for j in 0..n {
let col = &mut a.data[j * n..(j + 1) * n];
let f = two * dot(col, &w) / ww;
crate::small::axpy_sub(f, &w, col);
}
for i in 0..n {
let s: T = (0..n).map(|j| a.data[i + j * n] * w[j]).sum();
let f = two * s / ww;
for j in 0..n {
a.data[i + j * n] -= f * w[j];
}
}
}
for j in 0..n {
for i in 0..j {
let s = (a.data[i + j * n] + a.data[j + i * n]) * T::from_f64(0.5);
a.data[i + j * n] = s;
a.data[j + i * n] = s;
}
}
a
}
fn residual<T: Real>(a: &DenseBlock<T>, y: &[T], yi: &[T], th: Complex<T>) -> f64 {
let n = a.rows;
let mut r = 0.0f64;
for i in 0..n {
let (mut sr, mut si) = (T::ZERO, T::ZERO);
for j in 0..n {
sr += a.data[i + j * n] * y[j];
si += a.data[i + j * n] * yi[j];
}
let er = sr - (th.re * y[i] - th.im * yi[i]);
let ei = si - (th.re * yi[i] + th.im * y[i]);
r += (er * er + ei * ei).to_f64();
}
r.sqrt()
}
#[test]
fn krylov_relation_holds_after_every_expansion() {
fn k2_of<T: Real>(sym: bool, u: f64) -> f64 {
let d: Vec<f64> = (0..80).map(|j| 1.0 / (1.0 + 0.1 * f64::from(j))).collect();
let mut a = sym_matrix::<T>(&d, 3);
if !sym {
for j in 0..80 {
for i in 0..j {
a.data[i + j * 80] += T::from_f64(0.01 * ((i * 7 + j * 3) % 5) as f64);
}
}
}
let raw = run(
&mut a,
6,
Which::LargestMagnitude,
&EigsOptions::default(),
sym,
true,
)
.unwrap();
assert!(raw.stats.restarts > 0, "the test must restart");
assert!(raw.locked > 0, "the test must lock");
raw.k2 / (20.0 * u)
}
let u64_ = f64::EPSILON / 2.0;
let udd = Dd::EPSILON.to_f64() / 2.0;
let r = [
k2_of::<f64>(true, u64_),
k2_of::<f64>(false, u64_),
k2_of::<Dd>(true, udd),
k2_of::<Dd>(false, udd),
];
eprintln!("(K2) / (ncv u): {r:.3?}");
assert!(r.iter().all(|&x| x <= C_K), "{r:?}");
}
#[test]
fn symmetric_which_set() {
let d: Vec<f64> = (0..60).map(|j| -3.0 + 0.1 * f64::from(j)).collect();
let mut a = sym_matrix::<f64>(&d, 7);
let mut sorted = d.clone();
sorted.sort_by(f64::total_cmp);
let cases: [(Which, Vec<f64>); 5] = [
(Which::LargestAlgebraic, vec![2.9, 2.8, 2.7, 2.6]),
(Which::SmallestAlgebraic, vec![-3.0, -2.9, -2.8, -2.7]),
(Which::LargestMagnitude, vec![-3.0, 2.9, -2.9, 2.8]),
(Which::SmallestMagnitude, vec![0.0, -0.1, 0.1, -0.2]),
(Which::BothEnds, vec![2.9, -3.0, 2.8, -2.9]),
];
for (w, want) in cases {
let f = eigsh(&mut a, 4, w, &EigsOptions::default()).unwrap();
let (mut got_s, mut want_s) = (f.values.clone(), want.clone());
if matches!(w, Which::LargestMagnitude | Which::SmallestMagnitude) {
got_s.sort_by(f64::total_cmp);
want_s.sort_by(f64::total_cmp);
}
for (got, exp) in got_s.iter().zip(&want_s) {
assert!((got - exp).abs() < 1e-13, "{w:?}: {:?}", f.values);
}
let y = f.vectors.as_ref().unwrap();
for (c, &th) in f.values.iter().enumerate() {
let col = &y.data[c * 60..(c + 1) * 60];
let r = residual(&a, col, &[0.0; 60], Complex { re: th, im: 0.0 });
assert!(r < 1e-13, "{w:?} {c}: {r}");
}
}
}
#[test]
fn general_which_set_and_pairs() {
let n = 40;
let mut a = DenseBlock::<f64>::zeros(n, n);
let mut exact: Vec<(f64, f64)> = Vec::new();
let mut i = 0;
let mut t = 0;
while i < n {
if t % 3 == 0 && i + 1 < n {
let (re, im) = (0.5 + 0.07 * f64::from(t), 0.2 + 0.05 * f64::from(t));
a.data[i + i * n] = re;
a.data[(i + 1) + (i + 1) * n] = re;
a.data[i + (i + 1) * n] = -im;
a.data[(i + 1) + i * n] = im;
exact.push((re, im));
exact.push((re, -im));
i += 2;
} else {
let re = -1.0 + 0.09 * f64::from(t);
a.data[i + i * n] = re;
exact.push((re, 0.0));
i += 1;
}
t += 1;
}
let w: Vec<f64> = (0..n).map(|j| 1.0 + (j % 7) as f64).collect();
let ww = dot(&w, &w);
for j in 0..n {
let col = &mut a.data[j * n..(j + 1) * n];
let f = 2.0 * dot(col, &w) / ww;
crate::small::axpy_sub(f, &w, col);
}
for r in 0..n {
let s: f64 = (0..n).map(|j| a.data[r + j * n] * w[j]).sum();
let f = 2.0 * s / ww;
for j in 0..n {
a.data[r + j * n] -= f * w[j];
}
}
for which in [
Which::LargestMagnitude,
Which::SmallestMagnitude,
Which::LargestReal,
Which::SmallestReal,
Which::LargestImag,
Which::SmallestImag,
] {
let f = eigs(&mut a, 5, which, &EigsOptions::default()).unwrap();
assert_eq!(f.values.len(), 5);
let yr = f.vectors_re.as_ref().unwrap();
let yi = f.vectors_im.as_ref().unwrap();
for (c, th) in f.values.iter().enumerate() {
let r = residual(
&a,
&yr.data[c * n..(c + 1) * n],
&yi.data[c * n..(c + 1) * n],
*th,
);
assert!(r < 1e-12, "{which:?} {c}: {r}");
assert!(
exact
.iter()
.any(|e| (e.0 - th.re).abs() < 1e-12 && (e.1 - th.im).abs() < 1e-12),
"{which:?}: {th:?}"
);
if th.im > 0.0 && c + 1 < f.values.len() {
assert_eq!(f.values[c + 1].re, th.re);
assert_eq!(f.values[c + 1].im, -th.im);
}
assert!(th.im >= 0.0 || (c > 0 && f.values[c - 1].im == -th.im));
}
for w2 in f.values.windows(2) {
let (a0, b0) = ((w2[0].re, w2[0].im.abs()), (w2[1].re, w2[1].im.abs()));
assert!(!before(which, b0, a0), "{which:?}: {:?}", f.values);
}
}
}
#[test]
fn arpack_codes_round_trip() {
for c in ["LM", "SM", "LA", "SA", "BE", "LR", "SR", "LI", "SI"] {
assert_eq!(Which::from_arpack(c).unwrap().arpack_code(), c);
}
assert_eq!(Which::from_arpack("lm"), None);
assert_eq!(Which::from_arpack("XX"), None);
let e = eps23::<f64>();
let r = (e / f64::EPSILON.powf(2.0 / 3.0) - 1.0).abs();
assert!(r < 1e-14, "{e} {r}");
}
#[test]
#[allow(clippy::too_many_lines)] fn options_and_errors() {
let d: Vec<f64> = (0..10).map(f64::from).collect();
let mut a = sym_matrix::<f64>(&d, 1);
let o = EigsOptions::<f64>::default();
let inv = |r: Result<SymEigen<f64>, StatlaError>| {
matches!(r, Err(StatlaError::InvalidArgument { .. }))
};
assert!(inv(eigsh(&mut a, 0, Which::LargestMagnitude, &o)));
assert!(inv(eigsh(&mut a, 10, Which::LargestMagnitude, &o)));
assert!(inv(eigsh(&mut a, 2, Which::LargestReal, &o)));
assert!(matches!(
eigs(&mut a, 9, Which::LargestMagnitude, &o),
Err(StatlaError::InvalidArgument { .. })
));
assert!(matches!(
eigs(&mut a, 2, Which::BothEnds, &o),
Err(StatlaError::InvalidArgument { .. })
));
for bad in [
EigsOptions {
ncv: Some(2),
..o.clone()
},
EigsOptions {
ncv: Some(11),
..o.clone()
},
EigsOptions {
tol: -1.0,
..o.clone()
},
EigsOptions {
tol: f64::INFINITY,
..o.clone()
},
EigsOptions {
reorth_eta: 1.0,
..o.clone()
},
EigsOptions {
v0: Some(vec![0.0; 10]),
..o.clone()
},
] {
assert!(
inv(eigsh(&mut a, 2, Which::LargestMagnitude, &bad)),
"{bad:?}"
);
}
assert!(matches!(
eigsh(
&mut a,
2,
Which::LargestMagnitude,
&EigsOptions {
v0: Some(vec![1.0; 3]),
..o.clone()
}
),
Err(StatlaError::Dimension { what: "v0", .. })
));
assert!(matches!(
eigsh(
&mut a,
2,
Which::LargestMagnitude,
&EigsOptions {
v0: Some(vec![f64::NAN; 10]),
..o.clone()
}
),
Err(StatlaError::NonFinite {
what: "v0",
index: 0
})
));
let mut rect = DenseBlock::<f64>::zeros(4, 3);
assert!(matches!(
eigsh(&mut rect, 1, Which::LargestMagnitude, &o),
Err(StatlaError::InvalidArgument { .. })
));
let mut failing = from_fn(10, 10, |_x: &[f64], _y: &mut [f64]| {
Err(crate::OperatorError {
message: "boom".into(),
})
});
assert!(matches!(
eigsh(&mut failing, 2, Which::LargestMagnitude, &o),
Err(StatlaError::Operator(_))
));
let mut nan = from_fn(10, 10, |_x: &[f64], y: &mut [f64]| {
y.fill(f64::NAN);
Ok(())
});
assert!(matches!(
eigs(&mut nan, 2, Which::LargestMagnitude, &o),
Err(StatlaError::NonFinite { .. })
));
let dd: Vec<f64> = (0..200).map(|j| 1.0 + 1e-3 * f64::from(j)).collect();
let mut slow = sym_matrix::<f64>(&dd, 5);
let lim = EigsOptions {
max_restarts: Some(1),
..o.clone()
};
assert!(matches!(
eigsh(&mut slow, 6, Which::SmallestMagnitude, &lim),
Err(StatlaError::NoConvergence { requested: 6, .. })
));
let part = eigsh(
&mut slow,
6,
Which::SmallestMagnitude,
&EigsOptions {
allow_partial: true,
..lim
},
)
.unwrap();
assert!(part.values.len() < 6);
assert_eq!(part.stats.converged, part.values.len());
let f = eigsh(
&mut a,
3,
Which::LargestAlgebraic,
&EigsOptions {
ncv: Some(10),
vectors: false,
..o
},
)
.unwrap();
assert_eq!(f.stats.restarts, 0);
assert!(f.vectors.is_none());
for (g, e) in f.values.iter().zip([9.0, 8.0, 7.0]) {
assert!((g - e).abs() < 1e-13);
}
}
#[test]
fn reproducible_and_breakdown_safe() {
let d: Vec<f64> = (0..30).map(|j| f64::from(j % 10)).collect();
let mut a = DenseBlock::<f64>::zeros(30, 30);
for (i, &x) in d.iter().enumerate() {
a.data[i + i * 30] = x;
}
let mut e0 = vec![0.0; 30];
e0[3] = 1.0;
let o = EigsOptions {
v0: Some(e0),
..EigsOptions::default()
};
let f = eigsh(&mut a, 3, Which::LargestAlgebraic, &o).unwrap();
for g in &f.values {
assert!((g - 9.0).abs() < 1e-14, "{:?}", f.values);
}
let g = eigsh(&mut a, 3, Which::LargestAlgebraic, &o).unwrap();
assert_eq!(
f.values.iter().map(|x| x.to_bits()).collect::<Vec<_>>(),
g.values.iter().map(|x| x.to_bits()).collect::<Vec<_>>()
);
}
}