use xingo_sparse::{DenseBlock, Real};
use crate::error::op_err;
use crate::jacobi::{JacobiOptions, jacobi_svd};
use crate::operator::AdjointOperator;
use crate::random::{Rng, Sketch};
use crate::small::{check_finite, householder_qr};
use crate::{MatMut, MatRef, StatlaError};
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct RsvdOptions {
pub oversample: usize,
pub power_iters: usize,
pub sketch: Sketch,
pub seed: u64,
}
impl Default for RsvdOptions {
fn default() -> Self {
Self {
oversample: 10,
power_iters: 2,
sketch: Sketch::Gaussian,
seed: 0,
}
}
}
#[derive(Clone, Debug)]
#[non_exhaustive]
pub struct Svd<T: Real = f64> {
pub u: DenseBlock<T>,
pub s: Vec<T>,
pub v: DenseBlock<T>,
pub stats: SvdStats,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct SvdStats {
pub applies: usize,
pub applies_t: usize,
pub restarts: usize,
pub reorthogonalizations: usize,
pub converged: usize,
}
pub(crate) fn apply_new<T: Real, O: AdjointOperator<T> + ?Sized>(
op: &mut O,
x: &DenseBlock<T>,
transpose: bool,
stats: &mut SvdStats,
) -> Result<DenseBlock<T>, StatlaError> {
let rows = if transpose { op.ncols() } else { op.nrows() };
let mut y = DenseBlock::zeros(rows, x.cols);
{
let xv = MatRef::from_block(x);
let yv = MatMut::from_block(&mut y);
if transpose {
op.apply_t_block(xv, yv).map_err(op_err)?;
stats.applies_t += x.cols;
} else {
op.apply_block(xv, yv).map_err(op_err)?;
stats.applies += x.cols;
}
}
check_finite("operator output", &y.data)?;
Ok(y)
}
fn range<T: Real, O: AdjointOperator<T> + ?Sized>(
op: &mut O,
l: usize,
opts: &RsvdOptions,
stats: &mut SvdStats,
) -> Result<DenseBlock<T>, StatlaError> {
let mut omega = DenseBlock::zeros(op.ncols(), l);
Rng::new(opts.seed).fill(opts.sketch, &mut omega.data);
let (mut q, _) = householder_qr(apply_new(op, &omega, false, stats)?);
for _ in 0..opts.power_iters {
let (z, _) = householder_qr(apply_new(op, &q, true, stats)?);
q = householder_qr(apply_new(op, &z, false, stats)?).0;
}
Ok(q)
}
pub fn rsvd<T, O>(op: &mut O, k: usize, opts: &RsvdOptions) -> Result<Svd<T>, StatlaError>
where
T: Real,
O: AdjointOperator<T> + ?Sized,
{
let (m, n) = (op.nrows(), op.ncols());
if k == 0 || k > m.min(n) {
return Err(StatlaError::InvalidArgument {
what: "rsvd: k must satisfy 1 <= k <= min(m, n)",
});
}
let l = k.saturating_add(opts.oversample).min(m).min(n);
let mut stats = SvdStats::default();
let q = range(op, l, opts, &mut stats)?;
let bt = apply_new(op, &q, true, &mut stats)?;
let (qb, r) = householder_qr(bt);
let small = jacobi_svd(&r, &JacobiOptions::for_rows(l))?;
let mut u = DenseBlock::zeros(m, k);
let mut v = DenseBlock::zeros(n, k);
for c in 0..k {
for t in 0..l {
let (yc, xc) = (small.y.get(t, c), small.x.get(t, c));
for i in 0..m {
u.data[i + c * m] += q.data[i + t * m] * yc;
}
for i in 0..n {
v.data[i + c * n] += qb.data[i + t * n] * xc;
}
}
}
stats.converged = k;
Ok(Svd {
u,
s: small.s[..k].to_vec(),
v,
stats,
})
}
pub fn range_finder<T, O>(
op: &mut O,
l: usize,
opts: &RsvdOptions,
) -> Result<DenseBlock<T>, StatlaError>
where
T: Real,
O: AdjointOperator<T> + ?Sized,
{
let (m, n) = (op.nrows(), op.ncols());
if l == 0 || l > m.min(n) {
return Err(StatlaError::InvalidArgument {
what: "range_finder: l must satisfy 1 <= l <= min(m, n)",
});
}
range(op, l, opts, &mut SvdStats::default())
}