use xingo_sparse::{
Amd, Col, CscMatrix, DenseKernel, KktError, KktForm, KktSolver, LuError, LuFactor, LuOptions,
NaiveDense, NumericLdl, Real, Regularization, SparseVec, SupernodalLdl, SupernodalOptions,
};
use crate::StatlaError;
use crate::eigs::{Complex, Eigen, EigsOptions, SymEigen, Which, eigs, eigsh, validate_for};
use crate::operator::{LinearOperator, OperatorError};
use crate::real::{is_exact_zero, lt};
use crate::schur::Cx;
fn idx32(j: usize) -> u32 {
u32::try_from(j).unwrap_or(u32::MAX)
}
fn sub_product<T: Real>(m: &CscMatrix<T>, y: &[T], r: &mut [T], symmetric: bool) {
for j in 0..m.n_cols() {
let (rows, vals) = m.col(Col::from_usize(j));
let yj = y[j];
let mut acc = T::ZERO;
for (&i, &v) in rows.iter().zip(vals) {
let iu = i as usize;
r[iu] -= v * yj;
if symmetric && iu != j {
acc += v * y[iu];
}
}
if symmetric {
r[j] -= acc;
}
}
}
fn check_apply(n: usize, x: usize, y: usize) -> Result<(), OperatorError> {
if x == n && y == n {
Ok(())
} else {
Err(OperatorError {
message: "shift-invert: x and y must have the order of A".to_owned(),
})
}
}
fn check_input<T: Real>(a: &CscMatrix<T>, sigma: T) -> Result<usize, StatlaError> {
if a.n_rows() != a.n_cols() {
return Err(StatlaError::InvalidArgument {
what: "shift-invert: A is not square",
});
}
if let Some(index) = a.val.iter().position(|v| !v.is_finite()) {
return Err(StatlaError::NonFinite { what: "a", index });
}
if !sigma.is_finite() {
return Err(StatlaError::NonFinite {
what: "sigma",
index: 0,
});
}
Ok(a.n_cols())
}
fn shifted<T: Real>(a: &CscMatrix<T>, sigma: T, lower_only: bool) -> CscMatrix<T> {
let n = a.n_cols();
let mut col_ptr = Vec::with_capacity(n + 1);
let mut row_idx = Vec::with_capacity(a.nnz() + n);
let mut val = Vec::with_capacity(a.nnz() + n);
col_ptr.push(0);
let push = |i: u32, v: T, row_idx: &mut Vec<u32>, val: &mut Vec<T>| {
if !is_exact_zero(v) {
row_idx.push(i);
val.push(v);
}
};
for j in 0..n {
let (rows, vals) = a.col(Col::from_usize(j));
let mut diag_done = false;
for (&i, &v) in rows.iter().zip(vals) {
let iu = i as usize;
if lower_only && iu < j {
continue;
}
if iu > j && !diag_done {
push(idx32(j), -sigma, &mut row_idx, &mut val);
diag_done = true;
}
if iu == j {
push(i, v - sigma, &mut row_idx, &mut val);
diag_done = true;
} else {
push(i, v, &mut row_idx, &mut val);
}
}
if !diag_done {
push(idx32(j), -sigma, &mut row_idx, &mut val);
}
col_ptr.push(row_idx.len());
}
CscMatrix {
n_rows: n,
col_ptr,
row_idx,
val,
}
}
#[derive(Debug)]
pub struct ShiftInvert<T: Real = f64> {
sigma: T,
n: usize,
lu: xingo_sparse::Lu<T>,
work: SparseVec<T>,
m: CscMatrix<T>,
r: Vec<T>,
d: Vec<T>,
}
impl<T: Real> ShiftInvert<T> {
pub fn new(a: &CscMatrix<T>, sigma: T, opts: LuOptions) -> Result<Self, StatlaError> {
let n = check_input(a, sigma)?;
a.check_invariants()
.map_err(|e| StatlaError::Lu(LuError::Structure(e)))?;
let fin = |x: f64| x.is_finite() && !lt(x, 0.0);
if opts.search_limit == 0
|| !lt(0.0, opts.rel_pivot_tol)
|| lt(1.0, opts.rel_pivot_tol)
|| !fin(opts.abs_pivot_tol)
|| !fin(opts.drop_tol)
|| !fin(opts.update_stability_tol)
|| !lt(0.0, opts.update_multiplier_limit)
{
return Err(StatlaError::InvalidArgument {
what: "ShiftInvert: LuOptions outside their domain",
});
}
let m = shifted(a, sigma, false);
let mut lu = xingo_sparse::Lu::<T>::new(opts);
lu.factorize(&m).map_err(StatlaError::Lu)?;
Ok(Self {
sigma,
n,
lu,
work: SparseVec::new(n),
m,
r: vec![T::ZERO; n],
d: vec![T::ZERO; n],
})
}
pub fn sigma(&self) -> T {
self.sigma
}
}
impl<T: Real> LinearOperator<T> for ShiftInvert<T> {
fn nrows(&self) -> usize {
self.n
}
fn ncols(&self) -> usize {
self.n
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
check_apply(self.n, x.len(), y.len())?;
self.lu_solve(x, y);
self.r.copy_from_slice(x);
sub_product(&self.m, y, &mut self.r, false);
let (r, mut d) = (core::mem::take(&mut self.r), core::mem::take(&mut self.d));
self.lu_solve(&r, &mut d);
for (yi, &di) in y.iter_mut().zip(&d) {
*yi += di;
}
(self.r, self.d) = (r, d);
Ok(())
}
}
impl<T: Real> ShiftInvert<T> {
fn lu_solve(&mut self, x: &[T], y: &mut [T]) {
self.work = SparseVec::from_dense(x);
self.lu.ftran(&mut self.work);
for (i, yi) in y.iter_mut().enumerate() {
*yi = self.work.get(idx32(i));
}
}
}
#[derive(Debug)]
pub struct SymShiftInvert<T: Real = f64, K: DenseKernel<T> = NaiveDense> {
sigma: T,
n: usize,
below: usize,
ldl: SupernodalLdl<T, K>,
num: NumericLdl<T>,
low: CscMatrix<T>,
r: Vec<T>,
}
impl<T: Real, K: DenseKernel<T>> SymShiftInvert<T, K> {
pub fn new(a: &CscMatrix<T>, sigma: T, kernel: K) -> Result<Self, StatlaError> {
let n = check_input(a, sigma)?;
a.check_invariants()
.map_err(|e| StatlaError::Kkt(KktError::Structure(e)))?;
let low = shifted(a, sigma, true);
let ldl = SupernodalLdl::new(kernel, SupernodalOptions::default());
let pattern = low.pattern();
let attempt = |n_primal: usize| {
let form = KktForm::Augmented {
n_primal,
n_dual: n - n_primal,
};
let sym = ldl.analyze(&pattern, form, &Amd::default())?;
ldl.factorize(&sym, &low, Regularization::none())
};
let (num, inertia) = match attempt(0) {
Ok(r) => r,
Err(KktError::WrongInertia { found, .. }) if found.zero == 0 => {
attempt(found.negative).map_err(StatlaError::Kkt)?
}
Err(e) => return Err(StatlaError::Kkt(e)),
};
debug_assert_eq!(
inertia.positive + inertia.negative + inertia.zero,
n,
"(I1) the inertia counts every pivot"
);
Ok(Self {
sigma,
n,
below: inertia.negative,
ldl,
num,
low,
r: vec![T::ZERO; n],
})
}
pub fn sigma(&self) -> T {
self.sigma
}
#[must_use]
pub fn count_below(&self) -> usize {
self.below
}
}
impl<T: Real, K: DenseKernel<T>> LinearOperator<T> for SymShiftInvert<T, K> {
fn nrows(&self) -> usize {
self.n
}
fn ncols(&self) -> usize {
self.n
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
check_apply(self.n, x.len(), y.len())?;
y.copy_from_slice(x);
self.ldl.solve(&self.num, y);
self.r.copy_from_slice(x);
sub_product(&self.low, y, &mut self.r, true);
self.ldl.solve(&self.num, &mut self.r);
for (yi, &di) in y.iter_mut().zip(&self.r) {
*yi += di;
}
Ok(())
}
}
pub fn eigsh_near<T: Real>(
a: &CscMatrix<T>,
k: usize,
sigma: T,
opts: &EigsOptions<T>,
) -> Result<(SymEigen<T>, usize), StatlaError> {
validate_for(
a.n_rows(),
a.n_cols(),
k,
Which::LargestMagnitude,
opts,
true,
)?;
let mut op = SymShiftInvert::<T, NaiveDense>::new(a, sigma, NaiveDense)?;
let below = op.count_below();
let mut f = eigsh(&mut op, k, Which::LargestMagnitude, opts)?;
for v in &mut f.values {
*v = sigma + T::ONE / *v;
}
Ok((f, below))
}
pub fn eigs_near<T: Real>(
a: &CscMatrix<T>,
k: usize,
sigma: T,
opts: &EigsOptions<T>,
) -> Result<Eigen<T>, StatlaError> {
validate_for(
a.n_rows(),
a.n_cols(),
k,
Which::LargestMagnitude,
opts,
false,
)?;
let mut op = ShiftInvert::new(a, sigma, LuOptions::for_scalar::<T>())?;
let mut f = eigs(&mut op, k, Which::LargestMagnitude, opts)?;
let n = a.n_rows();
let len = f.values.len();
let one = Cx::new(T::ONE, T::ZERO);
let mapped: Vec<Complex<T>> = f
.values
.iter()
.map(|nu| {
let w = one.div(Cx::new(nu.re, nu.im));
Complex {
re: sigma + w.re,
im: w.im,
}
})
.collect();
let mut i = 0;
while i < len {
let nu = f.values[i];
if lt(T::ZERO, nu.im) {
let paired = i + 1 < len && f.values[i + 1].re == nu.re && f.values[i + 1].im == -nu.im;
if paired {
f.values[i] = Complex {
re: mapped[i].re,
im: -mapped[i].im,
};
f.values[i + 1] = mapped[i];
if let Some(vi) = &mut f.vectors_im {
for r in 0..n {
vi.data.swap(r + i * n, r + (i + 1) * n);
}
}
i += 2;
continue;
}
f.values[i] = Complex {
re: mapped[i].re,
im: -mapped[i].im,
};
if let Some(vi) = &mut f.vectors_im {
for v in &mut vi.data[i * n..(i + 1) * n] {
*v = -*v;
}
}
} else {
f.values[i] = mapped[i];
if is_exact_zero(nu.im) {
f.values[i].im = T::ZERO;
}
}
i += 1;
}
Ok(f)
}
#[cfg(test)]
#[allow(
clippy::cast_precision_loss,
clippy::float_cmp,
clippy::cast_possible_truncation
)]
mod tests {
use super::*;
use xingo_sparse::Triplets;
fn lap1d(n: usize, lower: bool) -> CscMatrix<f64> {
let mut t = Triplets::new(n, n);
for i in 0..n {
t.push(i as u32, i as u32, 2.0);
if i + 1 < n {
t.push((i + 1) as u32, i as u32, -1.0);
if !lower {
t.push(i as u32, (i + 1) as u32, -1.0);
}
}
}
t.to_csc().unwrap()
}
fn exact(n: usize) -> Vec<f64> {
(1..=n)
.map(|j| 2.0 - 2.0 * (j as f64 * core::f64::consts::PI / (n as f64 + 1.0)).cos())
.collect()
}
#[test]
fn count_below_and_nearest_values() {
let n = 50;
let lam = exact(n);
for lower in [true, false] {
let a = lap1d(n, lower);
for sigma in [-0.5, 0.3, 1.01, 2.05, 3.9, 4.5] {
let (f, below) = eigsh_near(&a, 4, sigma, &EigsOptions::default())
.unwrap_or_else(|e| panic!("lower {lower} sigma {sigma}: {e:?}"));
assert_eq!(below, lam.iter().filter(|&&l| l < sigma).count(), "{sigma}");
let mut near = lam.clone();
near.sort_by(|x, y| (x - sigma).abs().total_cmp(&(y - sigma).abs()));
for (g, e) in f.values.iter().zip(&near) {
assert!((g - e).abs() < 1e-12, "{sigma}: {:?} {near:?}", f.values);
}
}
}
assert!(matches!(
eigsh_near(&lap1d(50, true), 4, 1.0, &EigsOptions::default()),
Err(StatlaError::Kkt(_))
));
let a = lap1d(5, true);
assert!(matches!(
SymShiftInvert::<f64>::new(&a, 2.0, NaiveDense),
Err(StatlaError::Kkt(_))
));
assert!(matches!(
ShiftInvert::new(&lap1d(5, false), 2.0, LuOptions::default()),
Err(StatlaError::Lu(_))
));
}
#[test]
fn general_shift_invert_maps_pairs_back() {
let blocks = [(1.0, 0.5), (2.0, 0.25), (3.0, 0.0), (0.5, 0.0), (2.2, 1.0)];
let mut t = Triplets::new(8, 8);
let mut r = 0u32;
for &(re, im) in &blocks {
if im == 0.0 {
t.push(r, r, re);
r += 1;
} else {
t.push(r, r, re);
t.push(r + 1, r + 1, re);
t.push(r, r + 1, -im);
t.push(r + 1, r, im);
r += 2;
}
}
let a = t.to_csc().unwrap();
let f = eigs_near(&a, 3, 1.9, &EigsOptions::default()).unwrap();
let want = [(2.0, 0.25), (2.0, -0.25), (1.0, 0.5)];
for (g, w) in f.values.iter().zip(want) {
assert!(
(g.re - w.0).abs() < 1e-12 && (g.im - w.1).abs() < 1e-12,
"{:?}",
f.values
);
}
let yr = f.vectors_re.as_ref().unwrap();
let yi = f.vectors_im.as_ref().unwrap();
let mut dense = [[0.0; 8]; 8];
for j in 0..8 {
let (rows, vals) = a.col(Col::from_usize(j));
for (&i, &v) in rows.iter().zip(vals) {
dense[i as usize][j] = v;
}
}
for (c, th) in f.values.iter().enumerate() {
let (y, z) = (&yr.data[c * 8..(c + 1) * 8], &yi.data[c * 8..(c + 1) * 8]);
let mut e = 0.0f64;
for i in 0..8 {
let (mut sr, mut si) = (0.0, 0.0);
for j in 0..8 {
sr += dense[i][j] * y[j];
si += dense[i][j] * z[j];
}
e = e
.max((sr - (th.re * y[i] - th.im * z[i])).abs())
.max((si - (th.re * z[i] + th.im * y[i])).abs());
}
assert!(e < 1e-12, "{c}: {e}");
}
}
#[test]
fn errors_are_returned() {
let a = lap1d(6, true);
let o = EigsOptions::<f64>::default();
let rect = CscMatrix::<f64>::zeros(3, 4);
assert!(matches!(
eigsh_near(&rect, 1, 0.0, &o),
Err(StatlaError::InvalidArgument { .. })
));
assert!(matches!(
eigs_near(&rect, 1, 0.0, &o),
Err(StatlaError::InvalidArgument { .. })
));
assert!(matches!(
SymShiftInvert::<f64>::new(&rect, 0.0, NaiveDense),
Err(StatlaError::InvalidArgument { .. })
));
assert!(matches!(
eigsh_near(&a, 0, 0.0, &o),
Err(StatlaError::InvalidArgument { .. })
));
assert!(matches!(
eigsh_near(&a, 2, f64::NAN, &o),
Err(StatlaError::NonFinite { what: "sigma", .. })
));
let mut bad = a.clone();
bad.val[0] = f64::INFINITY;
assert!(matches!(
eigsh_near(&bad, 2, 0.0, &o),
Err(StatlaError::NonFinite {
what: "a",
index: 0
})
));
let mut broken = a.clone();
broken.row_idx[0] = 99;
assert!(matches!(
eigsh_near(&broken, 2, 0.0, &o),
Err(StatlaError::Kkt(KktError::Structure(_)))
));
assert!(matches!(
eigs_near(&broken, 2, 0.0, &o),
Err(StatlaError::Lu(LuError::Structure(_)))
));
let lo = LuOptions {
rel_pivot_tol: 0.0,
..LuOptions::default()
};
assert!(matches!(
ShiftInvert::new(&lap1d(6, false), 0.0, lo),
Err(StatlaError::InvalidArgument { .. })
));
let mut op = SymShiftInvert::<f64>::new(&a, 0.1, NaiveDense).unwrap();
assert!(op.apply(&[1.0; 5], &mut [0.0; 6]).is_err());
let mut op = ShiftInvert::new(&lap1d(6, false), 0.1, LuOptions::default()).unwrap();
assert!(op.apply(&[1.0; 6], &mut [0.0; 7]).is_err());
assert_eq!(op.sigma(), 0.1);
}
}