use std::borrow::Cow;
use faer::{Mat, MatMut, MatRef};
use super::ResidualFormula;
use crate::error::{CholeskyStage, GprError};
use crate::kernel::{
CompiledKernel, GramInputs, KernelScalar, KernelSpec, NoSupply, ScalarOps, Supply, SupplyViews,
TrainSources, Triangle,
};
use crate::linalg::{cholesky_lower_owned, inf_norm, symmetrize_lower};
const MAX_CORRECTIONS: usize = 10;
const STAGNATION_RATIO: f64 = 0.9;
const STAGNATION_STEPS: usize = 2;
pub(crate) const COLUMN_BLOCK: usize = 32;
pub(crate) trait RefineSystem {
fn rhs(&self) -> &[f64];
fn residual(&self, w: &[f64], r: &mut [f64]) -> Result<f64, GprError>;
fn correct(&self, r: &[f64], w: &mut [f64]);
fn accept(&self, _w: &[f64], _tol: f64) -> Result<bool, GprError> {
Ok(true)
}
fn fallback(&self) -> Result<Vec<f64>, GprError>;
}
pub(crate) fn refine<S: RefineSystem>(system: &S, mut w: Vec<f64>) -> Result<Vec<f64>, GprError> {
let dim = w.len();
let tol = 10.0 * dim as f64 * f64::EPSILON;
let mut resid = vec![0.0; dim];
let mut prev: Option<f64> = None;
let mut streak = 0usize;
for _ in 0..MAX_CORRECTIONS {
let b_inf = system.residual(&w, &mut resid)?;
let r_inf = inf_norm(&resid);
let denom = b_inf * inf_norm(&w) + inf_norm(system.rhs());
if denom > 0.0 && r_inf / denom < tol {
if !system.accept(&w, tol)? {
return system.fallback();
}
return Ok(w);
}
if let Some(prev_r) = prev {
let ratio = if prev_r > 0.0 { r_inf / prev_r } else { 0.0 };
if ratio > STAGNATION_RATIO {
streak += 1;
if streak >= STAGNATION_STEPS {
return system.fallback();
}
} else {
streak = 0;
}
}
prev = Some(r_inf);
system.correct(&resid, &mut w);
}
system.fallback()
}
#[derive(Clone, Copy)]
pub enum StoredFactor<'a, T> {
Llt(MatRef<'a, T>),
Ldlt(MatRef<'a, T>),
}
impl<T: KernelScalar> StoredFactor<'_, T> {
pub(crate) fn solve_in_place(&self, rhs: MatMut<'_, T>) {
match *self {
Self::Llt(l) => T::solve_llt_owned_scratch(l, rhs),
Self::Ldlt(ld) => {
let n = rhs.nrows();
crate::linalg::solve_ldlt_in_place(ld, rhs, n);
}
}
}
}
pub struct TrainSystem<'a, T: KernelScalar, S: Supply = NoSupply> {
pub kernel: &'a KernelSpec<S>,
pub compiled: &'a CompiledKernel<T, S>,
pub x: MatRef<'a, f64>,
pub sources: <S as SupplyViews>::Held<&'a TrainSources<T>>,
pub exact: Option<&'a TrainSources<f64>>,
pub y: &'a [f64],
pub noise: f64,
pub jitter: f64,
pub factor: StoredFactor<'a, T>,
pub factor_alpha: &'a [T],
pub policy: crate::policy::JitterPolicy,
pub stage: CholeskyStage,
}
pub(crate) struct ExactSystem<'s, 'a, M, R, S: Supply> {
sys: &'s TrainSystem<'a, f32, S>,
kernel_f64: CompiledKernel<f64, S>,
exact: Cow<'a, TrainSources<f64>>,
saved: Mat<f32>,
diag: f64,
_marker: core::marker::PhantomData<(M, R)>,
}
impl<'s, 'a, M: crate::math::KernelMath, R: ResidualFormula, S: Supply>
ExactSystem<'s, 'a, M, R, S>
{
pub(crate) fn new(sys: &'s TrainSystem<'a, f32, S>) -> Result<Self, GprError> {
let n = sys.x.nrows();
if n == 0 || sys.y.len() != n || sys.factor_alpha.len() != n {
return Err(GprError::EmptyInput);
}
let saved = if R::READS_STORAGE {
storage_system::<M, _>(sys)?
} else {
Mat::<f32>::zeros(0, 0)
};
Ok(Self {
sys,
kernel_f64: sys.kernel.compile(),
exact: exact_sources(sys)?,
saved,
diag: sys.noise + sys.jitter,
_marker: core::marker::PhantomData,
})
}
pub(crate) fn start(&self) -> Vec<f64> {
self.sys
.factor_alpha
.iter()
.map(|&v| f64::from(v))
.collect()
}
}
impl<M: crate::math::KernelMath, R: ResidualFormula, S: Supply> RefineSystem
for ExactSystem<'_, '_, M, R, S>
{
fn rhs(&self) -> &[f64] {
self.sys.y
}
fn residual(&self, w: &[f64], r: &mut [f64]) -> Result<f64, GprError> {
if R::READS_STORAGE {
Ok(row_sum_matvec(self.saved.as_ref(), w, self.sys.y, r))
} else {
fresh_residual::<M, _>(&self.kernel_f64, self.sys, &self.exact, self.diag, w, r)
}
}
fn correct(&self, r: &[f64], w: &mut [f64]) {
let mut rhs = Mat::<f32>::from_fn(r.len(), 1, |i, _| r[i] as f32);
self.sys.factor.solve_in_place(rhs.as_mut());
for (slot, i) in w.iter_mut().zip(0..) {
*slot += f64::from(rhs[(i, 0)]);
}
}
fn accept(&self, w: &[f64], tol: f64) -> Result<bool, GprError> {
if R::READS_STORAGE {
meets_f64_system::<M, _>(&self.kernel_f64, self.sys, &self.exact, self.diag, w, tol)
} else {
Ok(true)
}
}
fn fallback(&self) -> Result<Vec<f64>, GprError> {
f64_alpha::<M, _>(&self.kernel_f64, self.sys, &self.exact, self.diag)
}
}
pub(super) fn exact_sources<'a, S: Supply>(
sys: &TrainSystem<'a, f32, S>,
) -> Result<Cow<'a, TrainSources<f64>>, GprError> {
match S::held(&sys.sources) {
Some(storage) => crate::kernel::widened(sys.exact, storage),
None => Ok(Cow::Owned(TrainSources::empty())),
}
}
pub(crate) fn refine_alpha<M: crate::math::KernelMath, R: ResidualFormula, S: Supply>(
sys: &TrainSystem<'_, f32, S>,
) -> Result<Vec<f64>, GprError> {
let system = ExactSystem::<M, R, S>::new(sys)?;
let start = system.start();
refine(&system, start)
}
fn meets_f64_system<M: crate::math::KernelMath, S: Supply>(
kernel_f64: &CompiledKernel<f64, S>,
sys: &TrainSystem<'_, f32, S>,
exact: &TrainSources<f64>,
diag: f64,
alpha: &[f64],
tol: f64,
) -> Result<bool, GprError> {
let mut resid = vec![0.0; alpha.len()];
let a_inf = fresh_residual::<M, _>(kernel_f64, sys, exact, diag, alpha, &mut resid)?;
let denom = a_inf * inf_norm(alpha) + inf_norm(sys.y);
Ok(denom > 0.0 && inf_norm(&resid) / denom < tol)
}
fn storage_system<M: crate::math::KernelMath, S: Supply>(
sys: &TrainSystem<'_, f32, S>,
) -> Result<Mat<f32>, GprError> {
let x = sys.x;
let n = x.nrows();
let mut x32 = Mat::<f32>::zeros(n, x.ncols());
for col in 0..x.ncols() {
for row in 0..n {
x32[(row, col)] = x[(row, col)] as f32;
}
}
let mut a = Mat::<f32>::zeros(n, n);
let mut scratch = Mat::<f32>::zeros(n, n);
sys.compiled.eval_gram::<M>(
GramInputs::supplied(
x32.as_ref(),
S::held_squares(S::map_held(S::held_ref(&sys.sources), |storage| *storage)),
),
a.as_mut(),
Triangle::Lower,
scratch.as_mut(),
&mut Vec::new(),
)?;
let noise32 = sys.noise as f32;
let jitter32 = sys.jitter as f32;
for i in 0..n {
a[(i, i)] += noise32;
if sys.jitter != 0.0 {
a[(i, i)] += jitter32;
}
}
symmetrize_lower(a.as_mut(), n);
Ok(a)
}
fn row_sum_matvec(a: MatRef<'_, f32>, alpha: &[f64], y: &[f64], r: &mut [f64]) -> f64 {
let n = y.len();
let mut row_abs = vec![0.0f64; n];
let mut sum = vec![0.0f64; n];
for (j, &aj) in alpha.iter().enumerate().take(n) {
let col = a.col(j);
for i in 0..n {
let aij = f64::from(col[i]);
row_abs[i] += aij.abs();
sum[i] += aij * aj;
}
}
for i in 0..n {
r[i] = y[i] - sum[i];
}
row_abs.iter().fold(0.0f64, |acc, &v| acc.max(v))
}
fn fresh_residual<M: crate::math::KernelMath, S: Supply>(
kernel: &CompiledKernel<f64, S>,
sys: &TrainSystem<'_, f32, S>,
exact: &TrainSources<f64>,
diag: f64,
alpha: &[f64],
r: &mut [f64],
) -> Result<f64, GprError> {
let (x, y) = (sys.x, sys.y);
let n = y.len();
let d = x.ncols();
let block = COLUMN_BLOCK.min(n.max(1));
let mut rows = Mat::<f64>::zeros(block, d);
let mut k_block = Mat::<f64>::zeros(n, block);
let mut scratch = Mat::<f64>::zeros(n, block);
let mut dist = Mat::<f64>::zeros(n, block);
let mut nested = Vec::new();
let mut row_abs = vec![0.0f64; n];
let mut sum = vec![0.0f64; n];
let mut start = 0;
while start < n {
let len = block.min(n - start);
for dim in 0..d {
for jj in 0..len {
rows[(jj, dim)] = x[(start + jj, dim)];
}
}
let cols = exact.columns(start..start + len);
kernel.eval_cross_slots::<M>(
x,
rows.as_ref().submatrix(0, 0, len, d),
S::rects(&cols),
Some(dist.as_mut().submatrix_mut(0, 0, n, len)),
k_block.as_mut().submatrix_mut(0, 0, n, len),
scratch.as_mut().submatrix_mut(0, 0, n, len),
&mut nested,
&mut [],
)?;
for jj in 0..len {
let j = start + jj;
let aj = alpha[j];
for i in 0..n {
let mut kij = k_block[(i, jj)];
if i == j {
kij += diag;
}
row_abs[i] += kij.abs();
sum[i] += kij * aj;
}
}
start += len;
}
for i in 0..n {
r[i] = y[i] - sum[i];
}
Ok(row_abs.iter().fold(0.0f64, |acc, &v| acc.max(v)))
}
pub(crate) fn f64_alpha<M: crate::math::KernelMath, S: Supply>(
kernel: &CompiledKernel<f64, S>,
sys: &TrainSystem<'_, f32, S>,
sources: &TrainSources<f64>,
diag: f64,
) -> Result<Vec<f64>, GprError> {
let x = sys.x;
let y = sys.y;
let n = y.len();
let mut a = Mat::<f64>::zeros(n, n);
let mut scratch = Mat::<f64>::zeros(n, n);
kernel.eval_gram::<M>(
GramInputs::supplied(x, S::squares(sources)),
a.as_mut(),
Triangle::Lower,
scratch.as_mut(),
&mut Vec::new(),
)?;
for i in 0..n {
a[(i, i)] += diag;
}
cholesky_lower_owned(&mut a, sys.policy.retry_jitters(), sys.stage)?;
let mut rhs = Mat::<f64>::from_fn(n, 1, |i, _| y[i]);
f64::solve_llt_owned_scratch(a.as_ref(), rhs.as_mut());
Ok((0..n).map(|i| rhs[(i, 0)]).collect())
}