use nalgebra::{DMatrix, DVector};
use crate::Vce;
pub(crate) fn factorial(n: usize) -> f64 {
(1..=n).map(|k| k as f64).product()
}
pub(crate) fn compute_dups_dupsid(x: &[f64]) -> (Vec<usize>, Vec<usize>) {
let n = x.len();
let mut dups = vec![0usize; n];
let mut dupsid = vec![0usize; n];
let mut i = 0;
while i < n {
let mut j = i + 1;
while j < n && x[j] == x[i] {
j += 1;
}
let len = j - i;
for k in i..j {
dups[k] = len;
dupsid[k] = k - i + 1;
}
i = j;
}
(dups, dupsid)
}
pub(crate) fn nn_residuals(
x: &[f64],
d: &DMatrix<f64>,
dups: &[usize],
dupsid: &[usize],
matches: usize,
) -> DMatrix<f64> {
let n = x.len();
let ncols = d.ncols();
let nn_tol_eps = f64::EPSILON.sqrt();
let target = matches.min(n.saturating_sub(1)) as isize;
let mut res = DMatrix::zeros(n, ncols);
for pos in 1..=n {
let p = pos as isize;
let mut rpos = dups[pos - 1] as isize - dupsid[pos - 1] as isize;
let mut lpos = dupsid[pos - 1] as isize - 1;
while lpos + rpos < target {
if p - lpos - 1 <= 0 {
rpos += dups[(p + rpos) as usize] as isize;
} else if p + rpos + 1 > n as isize {
lpos += dups[(p - lpos - 2) as usize] as isize;
} else {
let dleft = x[pos - 1] - x[(p - lpos - 2) as usize];
let dright = x[(p + rpos) as usize] - x[pos - 1];
let nn_tol = dleft.max(dright) * nn_tol_eps;
if dleft - dright > nn_tol {
rpos += dups[(p + rpos) as usize] as isize;
} else if dright - dleft > nn_tol {
lpos += dups[(p - lpos - 2) as usize] as isize;
} else {
rpos += dups[(p + rpos) as usize] as isize;
lpos += dups[(p - lpos - 2) as usize] as isize;
}
}
}
let lo0 = (p - lpos - 1) as usize;
let hi0 = (p + rpos - 1) as usize;
let ji = (lpos + rpos) as f64;
for col in 0..ncols {
let mut sum = 0.0;
for k in lo0..=hi0 {
sum += d[(k, col)];
}
let d_j = sum - d[(pos - 1, col)];
res[(pos - 1, col)] = (ji / (ji + 1.0)).sqrt() * (d[(pos - 1, col)] - d_j / ji);
}
}
res
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn residuals(
ex: &[f64],
r_mat: &DMatrix<f64>,
inv_g: &DMatrix<f64>,
rx: &DMatrix<f64>,
beta: &DMatrix<f64>,
d: &DMatrix<f64>,
n_w: usize,
vce: Vce,
dups_w: &[usize],
dupsid_w: &[usize],
nnmatch: usize,
has_cluster: bool,
) -> DMatrix<f64> {
if has_cluster {
return d - r_mat * beta;
}
if vce.cluster_order().is_some() {
return d - r_mat * beta;
}
match vce.hc_order() {
Some(0) => d - r_mat * beta,
Some(1) => {
let dof = r_mat.ncols() as f64;
let w = (n_w as f64 / (n_w as f64 - dof)).sqrt();
(d - r_mat * beta) * w
}
Some(2) | Some(3) => {
let hc3 = vce.hc_order() == Some(3);
let rig = r_mat * inv_g; let mut res = d - r_mat * beta;
let ncols = res.ncols();
for k in 0..n_w {
let hii: f64 = (0..r_mat.ncols()).map(|j| rig[(k, j)] * rx[(k, j)]).sum();
let denom = (1.0 - hii).max(1e-8);
let w = if hc3 {
1.0 / denom
} else {
(1.0 / denom).sqrt()
};
for col in 0..ncols {
res[(k, col)] *= w;
}
}
res
}
_ => match vce {
Vce::NearestNeighbor => nn_residuals(ex, d, dups_w, dupsid_w, nnmatch),
_ => unreachable!("non-NearestNeighbor vce {vce:?} handled above"),
},
}
}
pub(crate) fn partialling(
rx: &DMatrix<f64>,
inv_g: &DMatrix<f64>,
d: &DMatrix<f64>,
ew: &[f64],
dt: usize,
dz: usize,
) -> (DMatrix<f64>, DMatrix<f64>) {
let cz = 1 + dt;
let mut ezw = d.columns(cz, dz).into_owned();
for i in 0..d.nrows() {
for j in 0..dz {
ezw[(i, j)] *= ew[i];
}
}
let u = rx.transpose() * d; let zwd = ezw.transpose() * d; let u_cz = u.columns(cz, dz).into_owned();
let uigu = u_cz.transpose() * (inv_g * &u);
let zwz = zwd.columns(cz, dz) - uigu.columns(cz, dz);
let zwy = zwd.columns(0, 1 + dt) - uigu.columns(0, 1 + dt);
(zwz, zwy)
}
pub(crate) fn gamma_from(
zwz: &DMatrix<f64>,
zwy: &DMatrix<f64>,
covs_drop_coll: bool,
) -> DMatrix<f64> {
if covs_drop_coll {
crate::linalg::ginv(zwz) * zwy
} else {
match zwz.clone().cholesky() {
Some(ch) => ch.inverse() * zwy,
None => crate::linalg::ginv(zwz) * zwy,
}
}
}
pub(crate) fn v_matrix(
inv_g: &DMatrix<f64>,
rx: &DMatrix<f64>,
res: &DMatrix<f64>,
s: &DVector<f64>,
) -> DMatrix<f64> {
let r_comb = res * s; let mut rsc = rx.clone();
let nrow = rx.nrows();
let ncol = rx.ncols();
for i in 0..nrow {
let ri = r_comb[i];
for j in 0..ncol {
rsc[(i, j)] *= ri;
}
}
let m = rsc.transpose() * &rsc;
inv_g * (m * inv_g)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum ClusterKind {
Cr1,
Crv2,
Crv3,
}
pub(crate) fn cluster_kind(vce: Vce) -> ClusterKind {
match (vce.hc_order(), vce.cluster_order()) {
(Some(2), _) | (_, Some(2)) => ClusterKind::Crv2,
(Some(3), _) | (_, Some(3)) => ClusterKind::Crv3,
_ => ClusterKind::Cr1,
}
}
pub(crate) fn cluster_idx(c: &[f64]) -> Vec<Vec<usize>> {
let n = c.len();
if n == 0 {
return Vec::new();
}
let mut ord: Vec<usize> = (0..n).collect();
ord.sort_by(|&a, &b| c[a].total_cmp(&c[b]));
let mut groups: Vec<Vec<usize>> = Vec::new();
let mut start = 0;
while start < n {
let v = c[ord[start]];
let mut end = start + 1;
while end < n && c[ord[end]] == v {
end += 1;
}
groups.push(ord[start..end].to_vec());
start = end;
}
groups
}
fn solve_or_ginv(m: &DMatrix<f64>) -> DMatrix<f64> {
match m.clone().try_inverse() {
Some(inv) => inv,
None => crate::linalg::ginv(m),
}
}
fn cluster_score(
s: &DVector<f64>,
ncols: usize,
mut f: impl FnMut(usize) -> DVector<f64>,
) -> DVector<f64> {
let mut sv = f(0) * s[0];
for l in 1..ncols {
sv += f(l) * s[l];
}
sv
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn vce_meat_cluster(
s: &DVector<f64>,
rx: &DMatrix<f64>,
res: &DMatrix<f64>,
groups: &[Vec<usize>],
kind: ClusterKind,
inv_g: Option<&DMatrix<f64>>,
sqrt_rx: Option<&DMatrix<f64>>,
k_override: Option<usize>,
) -> DMatrix<f64> {
let k = rx.ncols();
let ncols = res.ncols();
let mut m = DMatrix::zeros(k, k);
match kind {
ClusterKind::Cr1 => {
for idx in groups {
let xi = rows(rx, idx); let ri = rows(res, idx); let sv = cluster_score(s, ncols, |l| {
(xi.transpose() * ri.column(l)).column(0).into_owned()
});
m += &sv * sv.transpose();
}
let n = res.nrows() as f64;
let k_df = k_override.unwrap_or(k) as f64;
let g = groups.len() as f64;
let w = ((n - 1.0) / (n - k_df)) * (g / (g - 1.0));
m * w
}
ClusterKind::Crv3 => {
let sqrt_rx = sqrt_rx.expect("crv3 requires sqrt_rx");
let inv_g = inv_g.expect("crv3 requires inv_g");
let g_gram = solve_or_ginv(inv_g);
for idx in groups {
let srx_g = rows(sqrt_rx, idx); let sw_g = srx_g.column(0).into_owned(); let ri = rows(res, idx);
let l_g = srx_g.transpose() * &srx_g; let m_g = solve_or_ginv(&(&g_gram - &l_g));
let sv = cluster_score(s, ncols, |l| {
let e = ri.column(l);
let swe =
DVector::from_iterator(idx.len(), (0..idx.len()).map(|i| sw_g[i] * e[i]));
let u_g = srx_g.transpose() * swe; &u_g + &l_g * (&m_g * &u_g)
});
m += &sv * sv.transpose();
}
m
}
ClusterKind::Crv2 => {
let sqrt_rx = sqrt_rx.expect("crv2 requires sqrt_rx");
let inv_g = inv_g.expect("crv2 requires inv_g");
let c_half_lower = nalgebra::Cholesky::new(inv_g.clone());
for idx in groups {
let srx_g = rows(sqrt_rx, idx);
let sw_g = srx_g.column(0).into_owned();
let ri = rows(res, idx);
let l_g = srx_g.transpose() * &srx_g;
let u_of = |l: usize| -> DVector<f64> {
let e = ri.column(l);
let swe =
DVector::from_iterator(idx.len(), (0..idx.len()).map(|i| sw_g[i] * e[i]));
srx_g.transpose() * swe
};
let sv = match &c_half_lower {
None => cluster_score(s, ncols, u_of), Some(ch) => {
let lower = ch.l(); let upper = lower.transpose(); let f_sq = &upper * &l_g * &lower; let eig = nalgebra::SymmetricEigen::new(0.5 * (&f_sq + f_sq.transpose()));
let kk = f_sq.nrows();
let mut c_coef = DVector::zeros(kk);
for j in 0..kk {
let sigma2 = eig.eigenvalues[j].max(0.0);
c_coef[j] = if sigma2 < 1e-14 {
0.0
} else {
(1.0 / (1.0 - sigma2).max(1e-8).sqrt() - 1.0) / sigma2
};
}
let v_g = &eig.eigenvectors;
let lt_chalf = &l_g * &lower; cluster_score(s, ncols, |l| {
let u_g = u_of(l);
let ru_g = &upper * &u_g; let vt_ru = v_g.transpose() * &ru_g;
let scaled =
DVector::from_iterator(kk, (0..kk).map(|j| c_coef[j] * vt_ru[j]));
let adj = v_g * scaled;
&u_g + <_chalf * adj
})
}
};
m += &sv * sv.transpose();
}
m
}
}
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn vce_meat_qq_cluster(
q: &DMatrix<f64>,
r_q: &DMatrix<f64>,
w_b: &[f64],
inv_g_q: &DMatrix<f64>,
res: &DMatrix<f64>,
groups: &[Vec<usize>],
crv2: bool,
s: &DVector<f64>,
) -> DMatrix<f64> {
let k = q.ncols();
let ncols = res.ncols();
let mut m = DMatrix::zeros(k, k);
let g_q = solve_or_ginv(inv_g_q);
for idx in groups {
let q_g = rows(q, idx); let r_g = rows(r_q, idx); let wb_g: Vec<f64> = idx.iter().map(|&i| w_b[i]).collect();
let sqrt_wb: Vec<f64> = wb_g.iter().map(|v| v.sqrt()).collect();
let mut sr_g = r_g.clone();
for i in 0..idx.len() {
for j in 0..sr_g.ncols() {
sr_g[(i, j)] *= sqrt_wb[i];
}
}
let l_g = sr_g.transpose() * &sr_g; let p_g = q_g.transpose() * &r_g; let ri = rows(res, idx);
let mut use_simple = false;
let mut lambda: Option<DMatrix<f64>> = None;
let mut m_g: Option<DMatrix<f64>> = None;
if crv2 {
let eig_l = nalgebra::SymmetricEigen::new(0.5 * (&l_g + l_g.transpose()));
let kr = l_g.nrows();
let sigma: Vec<f64> = (0..kr)
.map(|j| eig_l.eigenvalues[j].max(0.0).sqrt())
.collect();
let max_sig = sigma.iter().cloned().fold(0.0_f64, f64::max);
let keep: Vec<usize> = (0..kr).filter(|&j| sigma[j] > max_sig * 1e-10).collect();
let r = keep.len();
if r == 0 {
use_simple = true;
} else {
let mut v_r = DMatrix::zeros(kr, r);
for (col, &j) in keep.iter().enumerate() {
v_r.set_column(col, &eig_l.eigenvectors.column(j));
}
let sig: Vec<f64> = keep.iter().map(|&j| sigma[j]).collect();
let dsig = DMatrix::from_diagonal(&DVector::from_vec(sig.clone()));
let mut t_mat = &dsig * (v_r.transpose() * (inv_g_q * &v_r)) * &dsig;
t_mat = 0.5 * (&t_mat + t_mat.transpose());
let eig_t = nalgebra::SymmetricEigen::new(t_mat);
let mut gamma = DVector::zeros(r);
for j in 0..r {
let tau = eig_t.eigenvalues[j].clamp(0.0, 1.0 - 1e-10);
gamma[j] = 1.0 / (1.0 - tau).sqrt() - 1.0;
}
let w_g = &eig_t.eigenvectors;
let dinv =
DMatrix::from_diagonal(&DVector::from_iterator(r, sig.iter().map(|v| 1.0 / v)));
let a = &v_r * &dinv * w_g; let mut a_scaled = a.clone();
for col in 0..r {
for row in 0..a_scaled.nrows() {
a_scaled[(row, col)] *= gamma[col];
}
}
lambda = Some(&a_scaled * a.transpose());
}
} else {
m_g = Some(solve_or_ginv(&(&g_q - &l_g)));
}
let sv = cluster_score(s, ncols, |l| {
let e_gl = ri.column(l).into_owned();
let u_qq = q_g.transpose() * &e_gl; if use_simple {
u_qq.column(0).into_owned()
} else {
let wbe =
DVector::from_iterator(idx.len(), (0..idx.len()).map(|i| wb_g[i] * e_gl[i]));
let u_q = r_g.transpose() * wbe; let adj = if crv2 {
lambda.as_ref().unwrap() * &u_q
} else {
m_g.as_ref().unwrap() * &u_q
};
(&u_qq + &p_g * adj).column(0).into_owned()
}
});
m += &sv * sv.transpose();
}
m
}
fn rows(m: &DMatrix<f64>, idx: &[usize]) -> DMatrix<f64> {
let mut out = DMatrix::zeros(idx.len(), m.ncols());
for (r, &i) in idx.iter().enumerate() {
out.set_row(r, &m.row(i));
}
out
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn v_cluster(
inv_g: &DMatrix<f64>,
rx: &DMatrix<f64>,
res: &DMatrix<f64>,
s: &DVector<f64>,
groups: &[Vec<usize>],
kind: ClusterKind,
sqrt_rx: Option<&DMatrix<f64>>,
k_override: Option<usize>,
) -> DMatrix<f64> {
let crv_inv_g = match kind {
ClusterKind::Cr1 => None,
_ => Some(inv_g),
};
let meat = vce_meat_cluster(s, rx, res, groups, kind, crv_inv_g, sqrt_rx, k_override);
inv_g * (meat * inv_g)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn nn_residuals_empty_window_is_empty() {
let d = DMatrix::<f64>::zeros(0, 1);
let res = nn_residuals(&[], &d, &[], &[], 3);
assert_eq!((res.nrows(), res.ncols()), (0, 1));
}
#[test]
fn nn_residuals_single_point_is_nan_like_r() {
let d = DMatrix::from_row_slice(1, 1, &[2.0]);
let res = nn_residuals(&[0.5], &d, &[1], &[1], 3);
assert!(res[(0, 0)].is_nan());
}
#[test]
fn dups_dupsid_runs() {
let (d, id) = compute_dups_dupsid(&[1.0, 1.0, 2.0, 3.0, 3.0, 3.0]);
assert_eq!(d, vec![2, 2, 1, 3, 3, 3]);
assert_eq!(id, vec![1, 2, 1, 1, 2, 3]);
}
}