#![cfg_attr(not(feature = "cuda"), allow(dead_code))]
#[derive(Debug, Clone, Copy)]
pub struct RitzBounds {
pub lambda_min: f64,
pub lambda_max: f64,
pub steps: usize,
pub tail_beta: f64,
}
impl RitzBounds {
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];
}
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,
}
}
#[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);
}
}