use xingo_sparse::{DenseBlock, DenseError, DenseKernel, Inertia, NaiveDense, Perm};
use crate::dd::DoubleDouble;
use crate::kernels::reference::Reference;
use crate::kernels::{BLOCK_K, ColumnUpdate, dispatch, gemm_blocked};
#[derive(Clone, Copy, Debug, Default)]
pub struct DdDense;
fn is_consistent(a: &DenseBlock<DoubleDouble>) -> bool {
a.data.len() == a.rows * a.cols
}
fn square(a: &DenseBlock<DoubleDouble>) -> Option<usize> {
(is_consistent(a) && a.rows == a.cols).then_some(a.rows)
}
#[inline(always)] #[allow(clippy::inline_always)]
fn syrk<U: ColumnUpdate>(
update: U,
n: usize,
a: &DenseBlock<DoubleDouble>,
c: &mut DenseBlock<DoubleDouble>,
) {
let kk = a.cols;
let mut l0 = 0;
while l0 < kk {
let l1 = (l0 + BLOCK_K).min(kk);
for j in 0..n {
let cj = &mut c.data[j * n + j..(j + 1) * n];
for l in l0..l1 {
update.column_sub(cj, &a.data[l * n + j..(l + 1) * n], a.data[j + l * n]);
}
}
l0 = l1;
}
}
#[inline(always)] #[allow(clippy::inline_always)]
fn trsm_transposed<U: ColumnUpdate>(
update: U,
n: usize,
l: &DenseBlock<DoubleDouble>,
b: &mut DenseBlock<DoubleDouble>,
) {
let rows = b.rows;
for j in 0..n {
let (done, rest) = b.data.split_at_mut(j * rows);
let xj = &mut rest[..rows];
for k in 0..j {
update.column_sub(xj, &done[k * rows..(k + 1) * rows], l.get(j, k));
}
let d = l.get(j, j);
for x in xj {
*x /= d;
}
}
}
#[inline(always)] #[allow(clippy::inline_always)]
fn potrf_columns<U: ColumnUpdate>(
update: U,
n: usize,
a: &mut DenseBlock<DoubleDouble>,
) -> Result<(), DenseError> {
for j in 0..n {
let (done, rest) = a.data.split_at_mut(j * n);
let cj = &mut rest[j..n];
for k in 0..j {
update.column_sub(cj, &done[j + k * n..(k + 1) * n], done[j + k * n]);
}
let d = cj[0];
if !d.is_finite() || d <= DoubleDouble::ZERO {
return Err(DenseError::NotPositiveDefinite { position: j });
}
let ljj = d.sqrt();
cj[0] = ljj;
for x in &mut cj[1..] {
*x /= ljj;
}
}
Ok(())
}
const SOLVE_MIN_ROWS: usize = 8;
#[inline(always)]
#[allow(clippy::inline_always)]
fn solve_offset(skip: &[bool], j: usize) -> usize {
j + 1 + usize::from(skip.get(j).copied().unwrap_or(false))
}
fn check_solve(l: &DenseBlock<DoubleDouble>, skip: &[bool], y: &[DoubleDouble]) {
assert!(
is_consistent(l)
&& l.rows >= l.cols
&& y.len() == l.rows
&& (skip.is_empty() || skip.len() == l.cols),
"solve_unit_lower: dimensions do not agree"
);
}
#[inline(always)] #[allow(clippy::inline_always)]
fn solve_forward<U: ColumnUpdate>(
update: U,
l: &DenseBlock<DoubleDouble>,
skip: &[bool],
y: &mut [DoubleDouble],
) {
let nr = l.rows;
for j in 0..l.cols {
let o = solve_offset(skip, j);
let t = y[j];
update.column_sub(&mut y[o..], &l.data[j * nr + o..(j + 1) * nr], t);
}
}
#[inline(always)] #[allow(clippy::inline_always)]
fn solve_backward(
l: &DenseBlock<DoubleDouble>,
skip: &[bool],
y: &mut [DoubleDouble],
dot: impl Fn(&[DoubleDouble], &[DoubleDouble]) -> DoubleDouble,
) {
let (nr, nc) = (l.rows, l.cols);
for j in (0..nc).rev() {
let o = solve_offset(skip, j);
let col = &l.data[j * nr..(j + 1) * nr];
let a = dot(&col[o..nc], &y[o..nc]);
let b = dot(&col[nc..], &y[nc..]);
y[j] -= a + b;
}
}
#[inline(always)] #[allow(clippy::inline_always)]
fn trsm_plain<U: ColumnUpdate>(
update: U,
n: usize,
l: &DenseBlock<DoubleDouble>,
b: &mut DenseBlock<DoubleDouble>,
) {
for col in b.data.chunks_exact_mut(n.max(1)).take(b.cols) {
for k in 0..n {
let x = col[k] / l.get(k, k);
col[k] = x;
update.column_sub(&mut col[k + 1..], &l.data[k + 1 + k * n..(k + 1) * n], x);
}
}
}
impl DenseKernel<DoubleDouble> for DdDense {
fn potrf(&self, a: &mut DenseBlock<DoubleDouble>) -> Result<(), DenseError> {
let Some(n) = square(a) else {
return Err(DenseError::Dimension);
};
dispatch!(|lanes| potrf_columns(lanes, n, a));
potrf_columns(Reference, n, a)
}
fn sytrf(
&self,
a: &mut DenseBlock<DoubleDouble>,
perm: &mut Perm,
pivot_2x2: &mut Vec<bool>,
) -> Result<Inertia, DenseError> {
NaiveDense.sytrf(a, perm, pivot_2x2)
}
fn trsm_lower(
&self,
l: &DenseBlock<DoubleDouble>,
b: &mut DenseBlock<DoubleDouble>,
transpose: bool,
) {
let n = square(l).expect("trsm_lower: L must be square");
assert!(is_consistent(b), "trsm_lower: B is inconsistent");
if transpose {
assert_eq!(b.cols, n, "trsm_lower: B must have n columns");
dispatch!(|lanes| trsm_transposed(lanes, n, l, b));
trsm_transposed(Reference, n, l, b);
} else {
assert_eq!(b.rows, n, "trsm_lower: B must have n rows");
dispatch!(|lanes| trsm_plain(lanes, n, l, b));
trsm_plain(Reference, n, l, b);
}
}
fn gemm_sub(
&self,
a: &DenseBlock<DoubleDouble>,
b: &DenseBlock<DoubleDouble>,
c: &mut DenseBlock<DoubleDouble>,
) {
assert!(
is_consistent(a)
&& is_consistent(b)
&& is_consistent(c)
&& a.cols == b.cols
&& c.rows == a.rows
&& c.cols == b.rows,
"gemm_sub: dimensions do not agree"
);
let (m, k, n) = (a.rows, a.cols, b.rows);
dispatch!(
|lanes| gemm_blocked(lanes, m, k, &a.data, &mut c.data, |j, l| b.data[j + l * n])
);
gemm_blocked(Reference, m, k, &a.data, &mut c.data, |j, l| {
b.data[j + l * n]
});
}
fn syrk_sub(&self, a: &DenseBlock<DoubleDouble>, c: &mut DenseBlock<DoubleDouble>) {
let n = square(c).expect("syrk_sub: C must be square");
assert!(
is_consistent(a) && a.rows == n,
"syrk_sub: dimensions do not agree"
);
dispatch!(|lanes| syrk(lanes, n, a, c));
syrk(Reference, n, a, c);
}
fn name(&self) -> &'static str {
"dd"
}
fn solve_min_rows(&self) -> usize {
SOLVE_MIN_ROWS
}
fn solve_unit_lower(
&self,
l: &DenseBlock<DoubleDouble>,
skip: &[bool],
y: &mut [DoubleDouble],
) {
check_solve(l, skip, y);
dispatch!(|lanes| solve_forward(lanes, l, skip, y));
solve_forward(Reference, l, skip, y);
}
fn solve_unit_lower_t(
&self,
l: &DenseBlock<DoubleDouble>,
skip: &[bool],
y: &mut [DoubleDouble],
) {
check_solve(l, skip, y);
dispatch!(|lanes| solve_backward(l, skip, y, |a, b| crate::simd::dot4(lanes, a, b)));
solve_backward(l, skip, y, crate::kernels::reference::dot4);
}
}