use xingo_sparse::{DenseBlock, Real};
use crate::StatlaError;
use crate::error::op_err;
use crate::jacobi::{JacobiOptions, jacobi_svd};
use crate::krylov::{expand, kept_dimension};
use crate::operator::AdjointOperator;
use crate::random::Rng;
use crate::real::{is_exact_zero, le_exact, lt};
use crate::rsvd::{Svd, SvdStats};
use crate::small::{axpy_sub, check_finite, check_len, dot, norm2};
pub(crate) const C_G: f64 = 8.0;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum SvdWhich {
#[default]
Largest,
}
#[derive(Clone, Debug, PartialEq)]
pub struct SvdsOptions<T: Real = f64> {
pub which: SvdWhich,
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 SvdsOptions<T> {
fn default() -> Self {
Self {
which: SvdWhich::Largest,
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,
}
}
}
struct Params<T> {
ncv: usize,
tau: T,
eta: T,
max_restarts: usize,
}
fn invalid(what: &'static str) -> StatlaError {
StatlaError::InvalidArgument { what }
}
fn validate<T: Real>(
m: usize,
n: usize,
k: usize,
o: &SvdsOptions<T>,
) -> Result<Params<T>, StatlaError> {
let mn = m.min(n);
if k == 0 || k >= mn {
return Err(invalid("svds: k must satisfy 1 <= k < min(m, n)"));
}
let ncv = o.ncv.unwrap_or_else(|| mn.min((2 * k + 1).max(20)));
if ncv <= k || ncv > mn {
return Err(invalid("svds: ncv must satisfy k < ncv <= min(m, n)"));
}
if !o.tol.is_finite() || lt(o.tol, 0.0) {
return Err(invalid("svds: 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("svds: 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("svds: v0 is the zero vector"));
}
}
let tau = if is_exact_zero(o.tol) {
T::EPSILON
} else {
T::from_f64(o.tol)
};
Ok(Params {
ncv,
tau,
eta: T::from_f64(o.reorth_eta),
max_restarts: o.max_restarts.unwrap_or(10 * mn),
})
}
#[derive(Clone, Copy, Debug)]
enum Slot {
Locked(usize),
Active(usize),
}
#[derive(Clone, Copy, Debug)]
struct Cand<T> {
value: T,
slot: Slot,
converged: bool,
}
struct Engine<T: Real> {
m: usize,
n: usize,
ncv: usize,
p: Vec<T>,
u: Vec<T>,
b: DenseBlock<T>,
beta_last: T,
nl: usize,
sigma_est: T,
rng: Rng,
stats: SvdStats,
#[cfg(test)]
g2: Option<f64>,
}
fn apply<T: Real, O: AdjointOperator<T> + ?Sized>(
op: &mut O,
x: &[T],
y: &mut [T],
transpose: bool,
stats: &mut SvdStats,
) -> Result<(), StatlaError> {
if transpose {
op.apply_t(x, y).map_err(op_err)?;
stats.applies_t += 1;
} else {
op.apply(x, y).map_err(op_err)?;
stats.applies += 1;
}
check_finite("operator output", y)
}
impl<T: Real> Engine<T> {
fn expand_from<O: AdjointOperator<T> + ?Sized>(
&mut self,
op: &mut O,
from: usize,
eta: T,
) -> Result<(), StatlaError> {
let (m, n, ncv) = (self.m, self.n, self.ncv);
let mut w = vec![T::ZERO; m];
let mut r = vec![T::ZERO; n];
for j in from..ncv {
apply(
op,
&self.p[j * n..(j + 1) * n],
&mut w,
false,
&mut self.stats,
)?;
for i in 0..j {
let bij = self.b.data[i + j * ncv];
if !is_exact_zero(bij) {
axpy_sub(bij, &self.u[i * m..(i + 1) * m], &mut w);
}
}
let floor = T::EPSILON * self.sigma_est;
let alpha = expand(
&self.u,
m,
j,
&mut w,
eta,
floor,
&mut self.rng,
&mut self.stats.reorthogonalizations,
);
self.u[j * m..(j + 1) * m].copy_from_slice(&w);
self.b.data[j + j * ncv] = alpha;
apply(
op,
&self.u[j * m..(j + 1) * m],
&mut r,
true,
&mut self.stats,
)?;
axpy_sub(alpha, &self.p[j * n..(j + 1) * n], &mut r);
let floor = T::EPSILON * self.sigma_est.max(alpha);
let beta = expand(
&self.p,
n,
j + 1,
&mut r,
eta,
floor,
&mut self.rng,
&mut self.stats.reorthogonalizations,
);
self.p[(j + 1) * n..(j + 2) * n].copy_from_slice(&r);
if j + 1 < ncv {
self.b.data[j + (j + 1) * ncv] = beta;
} else {
self.beta_last = beta;
}
self.sigma_est = self.sigma_est.max((alpha * alpha + beta * beta).sqrt());
}
Ok(())
}
#[cfg(test)]
fn relations<O: AdjointOperator<T> + ?Sized>(&mut self, op: &mut O) -> f64 {
let (m, n, ncv) = (self.m, self.n, self.ncv);
let mut worst = 0.0f64;
let mut y = vec![T::ZERO; m];
let mut z = vec![T::ZERO; n];
for j in 0..ncv {
op.apply(&self.p[j * n..(j + 1) * n], &mut y).unwrap();
for i in 0..=j {
axpy_sub(
self.b.data[i + j * ncv],
&self.u[i * m..(i + 1) * m],
&mut y,
);
}
worst = worst.max(norm2(&y).to_f64());
op.apply_t(&self.u[j * m..(j + 1) * m], &mut z).unwrap();
for i in j..ncv {
axpy_sub(
self.b.data[j + i * ncv],
&self.p[i * n..(i + 1) * n],
&mut z,
);
}
if j + 1 == ncv {
axpy_sub(self.beta_last, &self.p[ncv * n..(ncv + 1) * n], &mut z);
}
worst = worst.max(norm2(&z).to_f64());
}
worst / self.sigma_est.to_f64().max(f64::MIN_POSITIVE)
}
fn active_block(&self) -> DenseBlock<T> {
let (ncv, nl) = (self.ncv, self.nl);
let na = ncv - nl;
let mut a = DenseBlock::zeros(na, na);
for j in 0..na {
for i in 0..=j {
a.data[i + j * na] = self.b.data[nl + i + (nl + j) * ncv];
}
}
a
}
fn ritz(&self, coef: &DenseBlock<T>, c: usize, left: bool) -> Vec<T> {
let (rows, base) = if left {
(self.m, &self.u)
} else {
(self.n, &self.p)
};
let na = coef.rows;
let mut out = vec![T::ZERO; rows];
for t in 0..na {
let f = coef.data[t + c * na];
let col = &base[(self.nl + t) * rows..(self.nl + t + 1) * rows];
for (o, &v) in out.iter_mut().zip(col) {
*o += v * f;
}
}
out
}
fn arrowhead_shape(&self, kp: usize) -> bool {
let ncv = self.ncv;
for j in 0..ncv {
for i in 0..ncv {
let v = self.b.data[i + j * ncv];
let allowed = (i == j && j < kp) || (j == kp && i >= self.nl && i < kp);
if !allowed && !is_exact_zero(v) {
return false;
}
}
}
true
}
fn orthogonality(&self, j: usize) -> f64 {
let mut e = 0.0f64;
for (base, rows, cols) in [(&self.p, self.n, j + 1), (&self.u, self.m, j)] {
for a in 0..cols {
for c in 0..=a {
let d = dot(
&base[a * rows..(a + 1) * rows],
&base[c * rows..(c + 1) * rows],
);
let t = if a == c { d - T::ONE } else { d };
if a == c && is_exact_zero(d) {
continue;
}
e = e.max(t.abs().to_f64());
}
}
}
e
}
}
pub fn svds<T, O>(op: &mut O, k: usize, opts: &SvdsOptions<T>) -> Result<Svd<T>, StatlaError>
where
T: Real,
O: AdjointOperator<T> + ?Sized,
{
run(op, k, opts, false).map(|(svd, _)| svd)
}
#[derive(Clone, Copy, Debug)]
#[cfg_attr(not(test), allow(dead_code))]
struct Diag {
g2: f64,
locked: usize,
}
#[allow(clippy::too_many_lines)]
fn run<T, O>(
op: &mut O,
k: usize,
opts: &SvdsOptions<T>,
paranoid: bool,
) -> Result<(Svd<T>, Diag), StatlaError>
where
T: Real,
O: AdjointOperator<T> + ?Sized,
{
let (m, n) = (op.nrows(), op.ncols());
let par = validate(m, n, k, opts)?;
let ncv = par.ncv;
let _ = paranoid;
let mut rng = Rng::new(opts.seed);
let mut p = vec![T::ZERO; n * (ncv + 1)];
match &opts.v0 {
Some(v0) => p[..n].copy_from_slice(v0),
None => rng.fill(crate::Sketch::Gaussian, &mut p[..n]),
}
let nv = norm2(&p[..n]);
for v in &mut p[..n] {
*v = *v / nv;
}
let mut e = Engine {
m,
n,
ncv,
p,
u: vec![T::ZERO; m * ncv],
b: DenseBlock::zeros(ncv, ncv),
beta_last: T::ZERO,
nl: 0,
sigma_est: T::ZERO,
rng,
stats: SvdStats::default(),
#[cfg(test)]
g2: None,
};
let mut locked: Vec<T> = Vec::new();
let mut from = 0;
let jopts = JacobiOptions::for_rows(ncv);
loop {
e.expand_from(op, from, par.eta)?;
#[cfg(test)]
if paranoid {
let g = e.relations(op);
e.g2 = Some(e.g2.map_or(g, |h: f64| h.max(g)));
}
let na = ncv - e.nl;
let small = jacobi_svd(&e.active_block(), &jopts)?;
let rho: Vec<T> = (0..na)
.map(|i| e.beta_last * small.x.data[(na - 1) + i * na])
.collect();
let mut sigma1 = small.s[0];
for &v in &locked {
sigma1 = sigma1.max(v);
}
let thresh = par.tau * sigma1;
let mut cands: Vec<Cand<T>> = Vec::with_capacity(ncv);
for (i, &v) in locked.iter().enumerate() {
cands.push(Cand {
value: v,
slot: Slot::Locked(i),
converged: true,
});
}
for i in 0..na {
cands.push(Cand {
value: small.s[i],
slot: Slot::Active(i),
converged: le_exact(rho[i].abs(), thresh),
});
}
cands.sort_by(|a, b| {
if lt(b.value, a.value) {
core::cmp::Ordering::Less
} else if lt(a.value, b.value) {
core::cmp::Ordering::Greater
} else {
core::cmp::Ordering::Equal
}
});
let wanted = &cands[..k];
let n_conv = wanted.iter().filter(|c| c.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<Cand<T>> = wanted.iter().copied().filter(|c| c.converged).collect();
let cols = if opts.vectors { take.len() } else { 0 };
let mut uo = DenseBlock::zeros(m, cols);
let mut vo = DenseBlock::zeros(n, cols);
let mut s = Vec::with_capacity(take.len());
for (c, cand) in take.iter().enumerate() {
s.push(cand.value);
if !opts.vectors {
continue;
}
let (uc, vc) = match cand.slot {
Slot::Locked(i) => (
e.u[i * m..(i + 1) * m].to_vec(),
e.p[i * n..(i + 1) * n].to_vec(),
),
Slot::Active(i) => (e.ritz(&small.x, i, true), e.ritz(&small.y, i, false)),
};
uo.data[c * m..(c + 1) * m].copy_from_slice(&uc);
vo.data[c * n..(c + 1) * n].copy_from_slice(&vc);
}
let mut stats = e.stats;
stats.converged = s.len();
#[cfg(test)]
let g2 = e.g2.unwrap_or(0.0);
#[cfg(not(test))]
let g2 = 0.0;
let diag = Diag { g2, locked: e.nl };
return Ok((
Svd {
u: uo,
s,
v: vo,
stats,
},
diag,
));
}
e.stats.restarts += 1;
let newly: Vec<usize> = wanted
.iter()
.filter_map(|c| match c.slot {
Slot::Active(i) if c.converged => Some(i),
_ => None,
})
.collect();
let nl_new = e.nl + newly.len();
let kp = kept_dimension(k, ncv, n_conv, nl_new);
let kept: Vec<usize> = (0..na)
.filter(|i| !newly.contains(i))
.take(kp - nl_new)
.collect();
let (mut pn, mut un) = (e.p.clone(), e.u.clone());
let mut bn = DenseBlock::zeros(ncv, ncv);
for i in 0..e.nl {
bn.data[i + i * ncv] = e.b.data[i + i * ncv];
}
for (slot, &i) in newly.iter().chain(&kept).enumerate() {
let col = e.nl + slot;
un[col * m..(col + 1) * m].copy_from_slice(&e.ritz(&small.x, i, true));
pn[col * n..(col + 1) * n].copy_from_slice(&e.ritz(&small.y, i, false));
bn.data[col + col * ncv] = small.s[i];
if col >= nl_new {
bn.data[col + kp * ncv] = rho[i];
}
}
pn[kp * n..(kp + 1) * n].copy_from_slice(&e.p[ncv * n..(ncv + 1) * n]);
for &i in &newly {
locked.push(small.s[i]);
}
e.p = pn;
e.u = un;
e.b = bn;
e.nl = nl_new;
from = kp;
debug_assert!(e.arrowhead_shape(kp), "(G3) arrowhead after a restart");
#[allow(clippy::cast_precision_loss)]
let g1 = C_G * (ncv as f64) * T::EPSILON.to_f64() / 2.0;
debug_assert!(
e.orthogonality(kp) <= g1,
"(G1) after a restart: {}",
e.orthogonality(kp)
);
}
}
#[cfg(test)]
#[allow(clippy::cast_precision_loss)]
mod tests {
use super::*;
use xingo_extprec::DoubleDouble as Dd;
fn test_matrix<T: Real>(m: usize, n: usize, s: &[f64], seed: u64) -> DenseBlock<T> {
let mut a = DenseBlock::<T>::zeros(m, n);
for (i, &v) in s.iter().enumerate() {
a.data[i + i * m] = T::from_f64(v);
}
let mut rng = Rng::new(seed);
for _ in 0..3 {
let v: Vec<T> = (0..m).map(|_| T::from_f64(rng.gaussian())).collect();
let vv = dot(&v, &v);
for j in 0..n {
let col = &mut a.data[j * m..(j + 1) * m];
let f = T::from_f64(2.0) * dot(col, &v) / vv;
axpy_sub(f, &v, col);
}
let w: Vec<T> = (0..n).map(|_| T::from_f64(rng.gaussian())).collect();
let ww = dot(&w, &w);
for i in 0..m {
let d: T = (0..n).map(|j| a.data[i + j * m] * w[j]).sum();
let f = T::from_f64(2.0) * d / ww;
for j in 0..n {
a.data[i + j * m] -= f * w[j];
}
}
}
a
}
fn g2_of<T: Real>(u: f64) -> f64 {
let s: Vec<f64> = (0..60).map(|j| 0.9f64.powi(j)).collect();
let mut a = test_matrix::<T>(90, 60, &s, 5);
let (f, d) = run(&mut a, 6, &SvdsOptions::default(), true).unwrap();
assert!(f.stats.restarts > 0, "the test must restart");
assert!(d.locked > 0, "the test must lock");
d.g2 / (20.0 * u)
}
#[test]
fn relations_hold_after_every_expansion() {
let r64 = g2_of::<f64>(f64::EPSILON / 2.0);
let rdd = g2_of::<Dd>(Dd::EPSILON.to_f64() / 2.0);
eprintln!("(G2) / (ncv u): f64 {r64:.3}, dd {rdd:.3}");
assert!(r64 <= C_G && rdd <= C_G, "{r64} {rdd}");
}
#[test]
fn converged_triplets_are_locked() {
let s: Vec<f64> = (0..80).map(|j| 1.0 / (1.0 + 0.05 * f64::from(j))).collect();
let mut a = test_matrix::<f64>(100, 80, &s, 2);
let (f, d) = run(&mut a, 8, &SvdsOptions::default(), false).unwrap();
assert!(d.locked > 0 && f.stats.restarts > 2, "{d:?} {:?}", f.stats);
let mut y = vec![0.0; 80];
for c in 0..f.s.len() {
a.apply_t(&f.u.data[c * 100..(c + 1) * 100], &mut y)
.unwrap();
axpy_sub(f.s[c], &f.v.data[c * 80..(c + 1) * 80], &mut y);
assert!(norm2(&y) <= 1e-14 * f.s[0], "{c}: {}", norm2(&y));
assert!(
(f.s[c] - s[c]).abs() <= 1e-14,
"{c}: {} vs {}",
f.s[c],
s[c]
);
}
}
#[test]
fn options_are_validated() {
let mut a = test_matrix::<f64>(8, 6, &[3.0, 2.0, 1.0, 0.5, 0.25, 0.1], 1);
let d = SvdsOptions::<f64>::default();
let bad =
|o: &SvdsOptions<f64>, k: usize, a: &mut DenseBlock<f64>| svds(a, k, o).unwrap_err();
assert!(matches!(
bad(&d, 0, &mut a),
StatlaError::InvalidArgument { .. }
));
assert!(matches!(
bad(&d, 6, &mut a),
StatlaError::InvalidArgument { .. }
));
for o in [
SvdsOptions {
ncv: Some(2),
..d.clone()
},
SvdsOptions {
ncv: Some(7),
..d.clone()
},
SvdsOptions {
tol: -1.0,
..d.clone()
},
SvdsOptions {
tol: f64::NAN,
..d.clone()
},
SvdsOptions {
reorth_eta: 1.0,
..d.clone()
},
SvdsOptions {
reorth_eta: 0.0,
..d.clone()
},
SvdsOptions {
v0: Some(vec![0.0; 6]),
..d.clone()
},
] {
assert!(
matches!(bad(&o, 2, &mut a), StatlaError::InvalidArgument { .. }),
"{o:?}"
);
}
let o = SvdsOptions {
v0: Some(vec![1.0; 5]),
..d.clone()
};
assert!(matches!(
bad(&o, 2, &mut a),
StatlaError::Dimension { what: "v0", .. }
));
let o = SvdsOptions {
v0: Some(vec![1.0, f64::INFINITY, 0.0, 0.0, 0.0, 0.0]),
..d.clone()
};
assert!(matches!(
bad(&o, 2, &mut a),
StatlaError::NonFinite {
what: "v0",
index: 1
}
));
let f = svds(
&mut a,
3,
&SvdsOptions {
ncv: Some(6),
..d.clone()
},
)
.unwrap();
assert_eq!(f.stats.restarts, 0);
assert!((f.s[0] - 3.0).abs() < 1e-14 && (f.s[2] - 1.0).abs() < 1e-14);
}
}