krylovscope 0.1.0

GPU-resident Krylov spectral endpoint estimation for large symmetric operators
Documentation
#![cfg_attr(not(feature = "cuda"), allow(dead_code))]

/// Extremal Ritz estimates from a finite Lanczos/Krylov projection.
///
/// Despite the historical `Bounds` name, `lambda_min` and `lambda_max` are not
/// guaranteed enclosing bounds for the spectrum of the original operator.
/// Convergence, especially at the lower endpoint, can depend on Krylov dimension
/// and starting seed.
#[derive(Debug, Clone, Copy)]
pub struct RitzBounds {
    pub lambda_min: f64,
    pub lambda_max: f64,
    pub steps: usize,
    pub tail_beta: f64,
}

impl RitzBounds {
    /// Ritz-based condition estimate when the estimated lower endpoint is positive.
    ///
    /// This is not a certified condition-number bound.
    pub fn condition_estimate(&self) -> Option<f64> {
        if self.lambda_min.is_finite() && self.lambda_max.is_finite() && self.lambda_min > 0.0 {
            let k = self.lambda_max / self.lambda_min;
            k.is_finite().then_some(k)
        } else {
            None
        }
    }
}

#[cfg(test)]
pub(crate) trait SymmetricOperator {
    fn dim(&self) -> usize;
    fn apply(&mut self, x: &[f64], y: &mut [f64]);
}

#[inline]
pub(crate) fn dot(x: &[f64], y: &[f64]) -> f64 {
    debug_assert_eq!(x.len(), y.len());
    x.iter().zip(y).map(|(&a, &b)| a * b).sum()
}

#[inline]
fn norm2(x: &[f64]) -> f64 {
    dot(x, x).sqrt()
}

#[inline]
#[cfg(test)]
fn axpy(alpha: f64, x: &[f64], y: &mut [f64]) {
    debug_assert_eq!(x.len(), y.len());
    for (yi, &xi) in y.iter_mut().zip(x) {
        *yi += alpha * xi;
    }
}

fn splitmix64(state: &mut u64) -> u64 {
    *state = state.wrapping_add(0x9e3779b97f4a7c15);
    let mut z = *state;
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
    z ^ (z >> 31)
}

pub(crate) fn deterministic_unit_vector(n: usize, seed: u64) -> Vec<f64> {
    let mut state = seed ^ 0xd1b54a32d192ed03;
    let mut q = Vec::with_capacity(n);
    const INV_2POW53: f64 = 1.0 / 9_007_199_254_740_992.0;
    for _ in 0..n {
        let bits = splitmix64(&mut state);
        let u = ((bits >> 11) as f64) * INV_2POW53;
        q.push(2.0 * u - 1.0);
    }
    let nrm = norm2(&q);
    if nrm == 0.0 || !nrm.is_finite() {
        q.fill(0.0);
        if n != 0 {
            q[0] = 1.0;
        }
        return q;
    }
    for x in &mut q {
        *x /= nrm;
    }
    q
}

fn tridiag_gershgorin(diag: &[f64], off: &[f64]) -> (f64, f64) {
    debug_assert!(!diag.is_empty());
    debug_assert_eq!(off.len() + 1, diag.len());
    let n = diag.len();
    let mut lo = f64::INFINITY;
    let mut hi = f64::NEG_INFINITY;
    for i in 0..n {
        let mut radius = 0.0;
        if i > 0 {
            radius += off[i - 1].abs();
        }
        if i + 1 < n {
            radius += off[i].abs();
        }
        lo = lo.min(diag[i] - radius);
        hi = hi.max(diag[i] + radius);
    }
    let scale = lo.abs().max(hi.abs()).max(1.0);
    let span = (hi - lo).abs();
    let pad = 64.0 * f64::EPSILON * scale + 1.0e-14 * span.max(scale);
    (lo - pad, hi + pad)
}

fn sturm_count_le(diag: &[f64], off: &[f64], x: f64) -> usize {
    debug_assert!(!diag.is_empty());
    debug_assert_eq!(off.len() + 1, diag.len());
    let scale = diag.iter().fold(x.abs().max(1.0), |s, &v| s.max(v.abs()));
    let pivmin = 64.0 * f64::EPSILON * scale;
    let mut p = diag[0] - x;
    if p.abs() < pivmin {
        p = -pivmin;
    }
    let mut count = usize::from(p < 0.0);
    for i in 1..diag.len() {
        let e = off[i - 1];
        p = diag[i] - x - (e * e) / p;
        if p.abs() < pivmin {
            p = -pivmin;
        }
        if p < 0.0 {
            count += 1;
        }
    }
    count
}

pub(crate) fn tridiag_eigenvalue(diag: &[f64], off: &[f64], index: usize) -> f64 {
    debug_assert!(index < diag.len());
    if diag.len() == 1 {
        return diag[0];
    }
    // Normalize the small tridiagonal before Sturm bisection.  This avoids the
    // implicit absolute scale floor in pivot and stopping tolerances and keeps
    // endpoint extraction accurate for both very small and very large A.
    let scale = diag
        .iter()
        .chain(off)
        .map(|x| x.abs())
        .fold(0.0_f64, f64::max);
    if scale == 0.0 {
        return 0.0;
    }
    let scaled_diag: Vec<f64> = diag.iter().map(|x| *x / scale).collect();
    let scaled_off: Vec<f64> = off.iter().map(|x| *x / scale).collect();
    let (mut lo, mut hi) = tridiag_gershgorin(&scaled_diag, &scaled_off);
    for _ in 0..128 {
        let mid = lo + 0.5 * (hi - lo);
        let count = sturm_count_le(&scaled_diag, &scaled_off, mid);
        if count <= index {
            lo = mid;
        } else {
            hi = mid;
        }
        let tol = 32.0 * f64::EPSILON * lo.abs().max(hi.abs()).max(1.0);
        if hi - lo <= tol {
            break;
        }
    }
    (lo + 0.5 * (hi - lo)) * scale
}

#[cfg(test)]
fn checkpoint(alpha: &[f64], beta: &[f64], tail_beta: f64) -> RitzBounds {
    let k = alpha.len();
    debug_assert!(k > 0);
    debug_assert_eq!(beta.len(), k.saturating_sub(1));
    RitzBounds {
        lambda_min: tridiag_eigenvalue(alpha, beta, 0),
        lambda_max: tridiag_eigenvalue(alpha, beta, k - 1),
        steps: k,
        tail_beta,
    }
}

/// One Lanczos run, reporting prefix Ritz extrema at the requested step counts.
/// Two-pass full reorthogonalization is deliberate: this is setup diagnostics,
/// not a hot solver path.
#[cfg(test)]
pub(crate) fn lanczos_ritz_checkpoints<O: SymmetricOperator>(
    op: &mut O,
    requested: &[usize],
    seed: u64,
) -> Result<Vec<RitzBounds>, String> {
    let n = op.dim();
    if n == 0 {
        return Err("spectral operator has zero dimension".into());
    }
    if requested.is_empty() || requested.contains(&0) {
        return Err("Lanczos checkpoints must be non-empty and >= 1".into());
    }
    let mut checkpoints = requested.to_vec();
    checkpoints.sort_unstable();
    checkpoints.dedup();
    let max_steps = checkpoints.last().copied().unwrap().min(n);

    let mut q = deterministic_unit_vector(n, seed);
    let mut q_prev = vec![0.0; n];
    let mut z = vec![0.0; n];
    let mut basis: Vec<Vec<f64>> = Vec::with_capacity(max_steps);
    let mut alpha: Vec<f64> = Vec::with_capacity(max_steps);
    let mut beta: Vec<f64> = Vec::with_capacity(max_steps.saturating_sub(1));
    let mut beta_prev = 0.0;
    let mut out = Vec::with_capacity(checkpoints.len());
    let mut next_cp = 0usize;

    for j in 0..max_steps {
        basis.push(q.clone());
        z.fill(0.0);
        op.apply(&q, &mut z);
        if z.iter().any(|v| !v.is_finite()) {
            return Err("non-finite output from spectral operator".into());
        }
        if j > 0 {
            axpy(-beta_prev, &q_prev, &mut z);
        }
        let a = dot(&q, &z);
        if !a.is_finite() {
            return Err("non-finite Lanczos alpha".into());
        }
        axpy(-a, &q, &mut z);

        for _ in 0..2 {
            for qi in &basis {
                let h = dot(qi, &z);
                axpy(-h, qi, &mut z);
            }
        }

        let b = norm2(&z);
        if !b.is_finite() {
            return Err("non-finite Lanczos beta".into());
        }
        alpha.push(a);
        let k = alpha.len();

        while next_cp < checkpoints.len() && checkpoints[next_cp].min(n) == k {
            out.push(checkpoint(&alpha, &beta, b));
            next_cp += 1;
        }

        let breakdown_tol = 256.0 * f64::EPSILON * a.abs().max(beta_prev.abs());
        if b <= breakdown_tol {
            while next_cp < checkpoints.len() {
                out.push(checkpoint(&alpha, &beta, b));
                next_cp += 1;
            }
            break;
        }
        if j + 1 == max_steps {
            break;
        }

        beta.push(b);
        q_prev.copy_from_slice(&q);
        for i in 0..n {
            q[i] = z[i] / b;
        }
        beta_prev = b;
    }

    if out.is_empty() {
        return Err("Lanczos produced no checkpoint".into());
    }
    Ok(out)
}

#[cfg(test)]
mod tests {
    use super::*;

    struct DiagonalOperator {
        d: Vec<f64>,
    }
    impl SymmetricOperator for DiagonalOperator {
        fn dim(&self) -> usize {
            self.d.len()
        }
        fn apply(&mut self, x: &[f64], y: &mut [f64]) {
            for i in 0..self.d.len() {
                y[i] = self.d[i] * x[i];
            }
        }
    }

    #[test]
    fn identity_breakdown_is_correct() {
        let mut op = DiagonalOperator { d: vec![1.0; 16] };
        let r = lanczos_ritz_checkpoints(&mut op, &[16], 0x1234).unwrap();
        let r = r.last().unwrap();
        assert!((r.lambda_min - 1.0).abs() < 1.0e-12);
        assert!((r.lambda_max - 1.0).abs() < 1.0e-12);
        assert_eq!(r.steps, 1);
    }

    #[test]
    fn diagonal_extremes_are_recovered() {
        let exact = [0.125, 0.5, 1.0, 2.0, 3.75];
        let mut op = DiagonalOperator { d: exact.to_vec() };
        let r = lanczos_ritz_checkpoints(&mut op, &[exact.len()], 0x5678).unwrap();
        let r = r.last().unwrap();
        assert!((r.lambda_min - 0.125).abs() < 1.0e-10);
        assert!((r.lambda_max - 3.75).abs() < 1.0e-10);
    }

    #[test]
    fn checkpoints_are_monotone_outward() {
        let d: Vec<f64> = (1..=64).map(|i| 0.1 + i as f64 * 0.05).collect();
        let mut op = DiagonalOperator { d };
        let r = lanczos_ritz_checkpoints(&mut op, &[8, 16, 32], 0xabcd).unwrap();
        assert_eq!(r.len(), 3);
        assert!(r[1].lambda_min <= r[0].lambda_min + 1.0e-12);
        assert!(r[2].lambda_min <= r[1].lambda_min + 1.0e-12);
        assert!(r[1].lambda_max >= r[0].lambda_max - 1.0e-12);
        assert!(r[2].lambda_max >= r[1].lambda_max - 1.0e-12);
    }

    #[test]
    fn tiny_scale_does_not_trigger_absolute_breakdown() {
        let exact = [1.0e-12, 2.0e-12];
        let mut op = DiagonalOperator { d: exact.to_vec() };
        let r = lanczos_ritz_checkpoints(&mut op, &[2], 0x9876).unwrap();
        let r = r.last().unwrap();
        assert_eq!(r.steps, 2);
        assert!((r.lambda_min - exact[0]).abs() < 1.0e-24);
        assert!((r.lambda_max - exact[1]).abs() < 1.0e-24);
    }
}