use super::lit;
use super::vfe::{VfeExact, VfeState, refresh_w};
use crate::data::{pack_points, validate_inducing};
use crate::error::{CholeskyStage, GprError};
use crate::kernel::{CrossViews, KernelScalar, KernelSpec, NoSupply};
use crate::linalg::{
append_chol_border, chol_rank1_downdate, chol_rank1_update, cholesky_lower_owned,
delete_chol_row, frobenius2, gram_aat_plus_noise, mat_vec, mul_lower_left, solve_lower,
};
use crate::sparse::KernelScratch;
use faer::{Mat, MatMut, MatRef};
pub(crate) fn push_column<T: KernelScalar>(a: &mut Mat<T>, col: &[f64]) {
let m = a.nrows();
let n = a.ncols();
a.reserve(m, (n + 1).next_power_of_two());
a.resize_with(m, n + 1, |row, _| T::from_f64(col[row]));
}
pub(crate) fn remove_column_in_place<T: KernelScalar>(a: &mut Mat<T>, idx: usize) {
let m = a.nrows();
let n = a.ncols();
for col in idx..n - 1 {
for row in 0..m {
a[(row, col)] = a[(row, col + 1)];
}
}
a.truncate(m, n - 1);
}
pub(crate) fn a_times_y<T: KernelScalar>(a: MatRef<'_, T>, y: &[f64]) -> Vec<f64> {
let mut ay = vec![0.0; a.nrows()];
for (col, &y_col) in y.iter().enumerate().take(a.ncols()) {
for (row, slot) in ay.iter_mut().enumerate() {
*slot += a[(row, col)].to_f64() * y_col;
}
}
ay
}
pub(crate) fn append_point(x: &mut Vec<f64>, n: usize, d: usize, x_new: &[f64]) {
x.resize((n + 1) * d, 0.0);
for dim in (0..d).rev() {
x.copy_within(dim * n..(dim + 1) * n, dim * (n + 1));
x[dim * (n + 1) + n] = x_new[dim];
}
}
pub(crate) fn remove_point(x: &[f64], n: usize, d: usize, idx: usize) -> Vec<f64> {
let mut out = vec![0.0; (n - 1) * d];
for dim in 0..d {
let mut dest = 0;
for i in 0..n {
if i == idx {
continue;
}
out[dest + (n - 1) * dim] = x[i + n * dim];
dest += 1;
}
}
out
}
pub(crate) fn point_at(x: &[f64], n: usize, d: usize, idx: usize) -> Vec<f64> {
let mut out = vec![0.0; d];
for dim in 0..d {
out[dim] = x[idx + n * dim];
}
out
}
pub(crate) fn kernel_column<M: crate::math::KernelMath, T>(
kernel: &KernelSpec,
z: &[f64],
m: usize,
x_pt: &[f64],
d: usize,
ks: &mut KernelScratch<T>,
) -> Result<Mat<T>, GprError>
where
T: KernelScalar,
{
let compiled = kernel.compile_as::<T>();
let z64 = pack_points(z, m, d);
let x64 = pack_points(x_pt, 1, d);
let mut z_cast = T::empty_cols();
let mut x_cast = T::empty_cols();
let z_mat = T::storage_cols(z64.as_ref(), &mut z_cast);
let x_mat = T::storage_cols(x64.as_ref(), &mut x_cast);
ks.cross::<M, NoSupply>(&compiled, CrossViews::points(z_mat, x_mat))
}
pub(crate) fn kernel_diag_at<T, U: crate::kernel::Supply>(
kernel: &KernelSpec<U>,
x_pt: &[f64],
d: usize,
) -> Result<T, GprError>
where
T: KernelScalar,
{
let compiled = kernel.compile_as::<T>();
let x64 = pack_points(x_pt, 1, d);
let mut x_cast = T::empty_cols();
let x_mat = T::storage_cols(x64.as_ref(), &mut x_cast);
let mut diag = vec![lit::<T>(0.0); 1];
match U::coordinates(&compiled) {
Some(coords) => coords.fill_diag_points(x_mat, &mut diag)?,
None => compiled.eval_diag(x_mat, &mut diag)?,
}
Ok(diag[0])
}
pub(crate) fn solve_lmm<T: KernelScalar>(k_mm_l: MatRef<'_, T>, col: MatMut<'_, T>) {
solve_lower(k_mm_l, col);
}
pub(crate) struct InducingBorder<T> {
pub(crate) k_z: Mat<T>,
pub(crate) k_self: T,
pub(crate) k_x: Vec<T>,
}
#[allow(clippy::too_many_arguments)] pub(crate) fn coordinate_border<M: crate::math::KernelMath, T>(
kernel: &KernelSpec,
x: &[f64],
n: usize,
d: usize,
z: &[f64],
m: usize,
z_new: &[f64],
ks: &mut KernelScratch<T>,
) -> Result<InducingBorder<T>, GprError>
where
T: KernelScalar,
{
validate_inducing(z, m, d)?;
validate_inducing(z_new, 1, d)?;
if n == 0 {
return Err(GprError::EmptyInput);
}
let compiled = kernel.compile_as::<T>();
let z64 = pack_points(z, m, d);
let z_new64 = pack_points(z_new, 1, d);
let x64 = pack_points(x, n, d);
let mut z_cast = T::empty_cols();
let mut zn_cast = T::empty_cols();
let mut x_cast = T::empty_cols();
let z_mat = T::storage_cols(z64.as_ref(), &mut z_cast);
let z_new_mat = T::storage_cols(z_new64.as_ref(), &mut zn_cast);
let x_mat = T::storage_cols(x64.as_ref(), &mut x_cast);
let k_z = ks.cross::<M, NoSupply>(&compiled, CrossViews::points(z_mat, z_new_mat))?;
let k_self = kernel_diag_at::<T, NoSupply>(kernel, z_new, d)?;
let k_zx = ks.cross::<M, NoSupply>(&compiled, CrossViews::points(z_new_mat, x_mat))?;
let k_x = (0..n).map(|j| k_zx[(0, j)]).collect();
Ok(InducingBorder { k_z, k_self, k_x })
}
const INDUCING_PIVOT_RTOL: f64 = 1e-5;
const X_STEP_PIVOT_RTOL: f64 = 8.0 * f64::EPSILON;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum PivotGate {
XStep,
InducingStep,
}
impl PivotGate {
pub(crate) fn rtol(self) -> f64 {
match self {
Self::XStep => X_STEP_PIVOT_RTOL,
Self::InducingStep => INDUCING_PIVOT_RTOL,
}
}
pub(crate) fn holds(self, ratio: f64) -> bool {
ratio > self.rtol()
}
}
pub(crate) fn inducing_append<T: KernelScalar>(
state: &mut VfeState<T>,
border: InducingBorder<T>,
replace: Option<usize>,
noise: f64,
y: &[f64],
) -> Result<(), GprError> {
let InducingBorder {
k_z: mut l,
k_self,
k_x,
} = border;
let (m, n) = (state.a.nrows(), state.a.ncols());
let failed = |jitter| GprError::CholeskyFailed {
jitter,
matrix_size: m + 1,
stage: CholeskyStage::OnlineInsert,
};
solve_lmm(state.k_mm_l.as_ref(), l.as_mut());
let k_diag = k_self + lit::<T>(state.k_mm_jitter);
let mut ell2 = k_diag;
for i in 0..m {
ell2 -= l[(i, 0)] * l[(i, 0)];
}
if !pivot_holds(ell2, k_diag) {
return Err(failed(state.k_mm_jitter));
}
let l_col: Vec<T> = (0..m).map(|i| l[(i, 0)]).collect();
if let Some(col) = replace {
let mut old: Vec<T> = (0..m).map(|i| state.a[(i, col)]).collect();
let mut new = l_col.clone();
for (i, (&o, &v)) in old.iter().zip(&new).enumerate() {
state.a_frobenius2 += v * v - o * o;
state.a[(i, col)] = v;
}
chol_rank1_update(state.b_l.as_mut(), &mut new);
if !chol_rank1_downdate(state.b_l.as_mut(), &mut old) {
return Err(failed(0.0));
}
}
let ell = ell2.sqrt();
let mut a_new = vec![lit::<T>(0.0); n];
let mut a_new_norm2 = lit::<T>(0.0);
for j in 0..n {
let mut dot = lit::<T>(0.0);
for (i, &li) in l_col.iter().enumerate() {
dot += li * state.a[(i, j)];
}
let value = (k_x[j] - dot) / ell;
a_new[j] = value;
a_new_norm2 += value * value;
}
let v = mat_vec(state.a.as_ref(), &a_new);
let mut b_border = Mat::zeros(m, 1);
for i in 0..m {
b_border[(i, 0)] = v[i];
}
solve_lmm(state.b_l.as_ref(), b_border.as_mut());
let b_diag = lit::<T>(noise) + a_new_norm2;
let mut beta2 = b_diag;
for i in 0..m {
let bi = b_border[(i, 0)];
beta2 -= bi * bi;
}
if !pivot_holds(beta2, b_diag) {
return Err(failed(0.0));
}
let b_col: Vec<T> = (0..m).map(|i| b_border[(i, 0)]).collect();
state.k_mm_l = append_chol_border(&state.k_mm_l, &l_col, ell);
state.k_mm_l_f64 = T::hold_f64_factor(state.k_mm_l.as_ref());
state.b_l = append_chol_border(&state.b_l, &b_col, beta2.sqrt());
state.a = append_row(&state.a, &a_new);
state.a_frobenius2 += a_new_norm2;
let mut y_cast = T::empty_rows();
let y_s = T::storage_rows(y, &mut y_cast);
state.w = refresh_w(state.a.as_ref(), state.b_l.as_ref(), y_s);
state.exact = hold_promoted(state);
Ok(())
}
fn pivot_holds<T: KernelScalar>(pivot: T, diag: T) -> bool {
let (pivot, diag) = (pivot.to_f64(), diag.to_f64());
pivot.is_finite() && pivot > INDUCING_PIVOT_RTOL * diag
}
pub(crate) fn min_pivot_ratio<T: KernelScalar>(l: MatRef<'_, T>) -> f64 {
(0..l.nrows())
.map(|i| {
let mut row2 = 0.0;
for k in 0..=i {
let value = l[(i, k)].to_f64();
row2 += value * value;
}
let pivot = l[(i, i)].to_f64();
let ratio = pivot * pivot / row2;
if ratio.is_finite() { ratio } else { 0.0 }
})
.fold(1.0, f64::min)
}
pub(crate) fn inducing_delete<T: KernelScalar>(
state: &mut VfeState<T>,
noise: f64,
y: &[f64],
idx: usize,
) -> Result<(), GprError> {
let m = state.a.nrows();
if m <= 1 {
return Err(GprError::EmptyInput);
}
if idx >= m {
return Err(GprError::IndexOutOfRange {
reason: "inducing index is out of range".to_owned(),
});
}
let k_zx = mul_lower_left(state.k_mm_l.as_ref(), state.a.as_ref());
let k_zx = remove_row(&k_zx, idx);
state.k_mm_l = delete_chol_row(&state.k_mm_l, idx);
state.k_mm_l_f64 = T::hold_f64_factor(state.k_mm_l.as_ref());
let mut a = k_zx;
solve_lower(state.k_mm_l.as_ref(), a.as_mut());
let mut b = gram_aat_plus_noise(a.as_ref(), noise);
cholesky_lower_owned(&mut b, std::iter::empty(), CholeskyStage::OnlineDelete)?;
state.a = a;
state.b_l = b;
state.a_frobenius2 = frobenius2(state.a.as_ref());
let mut y_cast = T::empty_rows();
let y_s = T::storage_rows(y, &mut y_cast);
state.w = refresh_w(state.a.as_ref(), state.b_l.as_ref(), y_s);
state.exact = hold_promoted(state);
Ok(())
}
fn hold_promoted<T: KernelScalar>(state: &VfeState<T>) -> T::F64Held<VfeExact> {
T::hold_f64(|| {
VfeExact::promoted(
state.b_l.as_ref(),
&state.w,
state.k_diag_sum,
state.a_frobenius2,
)
})
}
pub(super) fn append_row<T: KernelScalar>(a: &Mat<T>, row: &[T]) -> Mat<T> {
let m = a.nrows();
let n = a.ncols();
let mut out = Mat::zeros(m + 1, n);
for j in 0..n {
for i in 0..m {
out[(i, j)] = a[(i, j)];
}
out[(m, j)] = row[j];
}
out
}
pub(super) fn remove_row<T: KernelScalar>(a: &Mat<T>, idx: usize) -> Mat<T> {
let m = a.nrows();
let n = a.ncols();
let mut out = Mat::zeros(m - 1, n);
for j in 0..n {
for i in 0..idx {
out[(i, j)] = a[(i, j)];
}
for i in (idx + 1)..m {
out[(i - 1, j)] = a[(i, j)];
}
}
out
}