use crate::algebra::{Algebra, BasisIdx};
use crate::field::{Fp, PrimeField};
use crate::linalg::DenseMat;
use super::super::cochain::next_usize;
use super::super::limits::BarStage;
use super::tuple;
use super::{BuildResult, Layout, Ledger, Shape};
struct DifferentialPlan(usize, usize, usize);
struct DifferentialContext<'a> {
algebra: &'a Algebra,
degree: usize,
target_degree: usize,
shape: &'a Shape,
source_layout: &'a Layout,
target_offsets: &'a [usize],
starts: &'a [Vec<usize>],
field: &'a PrimeField,
}
fn differential_plan(
algebra: &Algebra,
degree: usize,
cochain_dim: usize,
target_offsets: &[usize],
ledger: &mut Ledger,
) -> BuildResult<DifferentialPlan> {
let stage = BarStage::Differential;
let target_dim = *target_offsets
.last()
.expect("a tuple offset table has its final offset");
let target_degree = next_usize(ledger, degree, stage, degree)?;
let term_count = next_usize(ledger, target_degree, stage, target_degree)?;
let algebra_dimension = next_usize(ledger, degree, stage, algebra.dim())?;
let budget = ledger.budget(degree, stage);
let entries = budget.size(budget.product([cochain_dim as u128, target_dim as u128])?)?;
ledger.scratch(degree, stage, entries)?;
ledger.work(degree, stage, entries as u128)?;
let target_tuples = ledger.checked_usize(degree, stage, target_offsets.len().checked_sub(1))?;
let term_work = ledger.budget(degree, stage).product([
cochain_dim as u128,
target_tuples as u128,
term_count as u128,
algebra_dimension as u128,
])?;
ledger
.work(degree, stage, term_work)
.and(Ok(DifferentialPlan(target_dim, target_degree, entries)))
}
pub(crate) fn build_differential(
algebra: &Algebra,
degree: usize,
shape: &Shape,
source_layout: &Layout,
target_offsets: &[usize],
starts: &[Vec<usize>],
ledger: &mut Ledger,
) -> BuildResult<DenseMat> {
let stage = BarStage::Differential;
let plan = differential_plan(algebra, degree, shape.cochain_dim, target_offsets, ledger)?;
let field = algebra.field();
let mut differential = DenseMat::zero(shape.cochain_dim, plan.0);
if differential_is_empty(shape, &plan) {
ledger.retain(degree, stage, plan.2)?;
return Ok(differential);
}
fill_differential(
&DifferentialContext {
algebra,
degree,
target_degree: plan.1,
shape,
source_layout,
target_offsets,
starts,
field: &field,
},
&mut differential,
);
ledger.retain(degree, stage, plan.2)?;
Ok(differential)
}
fn differential_is_empty(shape: &Shape, plan: &DifferentialPlan) -> bool {
shape.cochain_dim == 0 || plan.0 == 0
}
struct SourceTuple {
words: Vec<BasisIdx>,
start: u32,
rows: std::ops::Range<usize>,
}
fn fill_differential(context: &DifferentialContext<'_>, differential: &mut DenseMat) {
let sources = source_tuples(context);
let mut products = Vec::with_capacity(context.degree);
tuple::walk_tuples(
context.algebra,
context.target_degree,
context.target_offsets.len() - 1,
context.starts,
|target_rank, target, target_start, target_end| {
let coordinate = TargetCoordinate {
algebra: context.algebra,
offsets: context.target_offsets,
tuple_rank: target_rank,
source: target_start,
target: target_end,
field: context.field,
};
products.clear();
products.extend(
(1..=context.degree).map(|i| context.algebra.mul_basis(target[i - 1], target[i])),
);
for source in &sources {
fill_source(
context,
&coordinate,
source,
target,
&products,
differential,
);
}
Ok::<(), ()>(())
},
)
.expect("the differential callback cannot fail");
}
fn source_tuples(context: &DifferentialContext<'_>) -> Vec<SourceTuple> {
let mut sources = Vec::new();
tuple::walk_tuples(
context.algebra,
context.degree,
context.shape.tuples,
context.starts,
|rank, words, start, _end| {
let offsets = &context.source_layout.offsets;
if offsets[rank] < offsets[rank + 1] {
sources.push(SourceTuple {
words: words.to_vec(),
start,
rows: offsets[rank]..offsets[rank + 1],
});
}
Ok::<(), ()>(())
},
)
.expect("the source callback cannot fail");
sources
}
fn fill_source(
context: &DifferentialContext,
coordinate: &TargetCoordinate,
source: &SourceTuple,
target: &[BasisIdx],
products: &[Vec<(BasisIdx, Fp)>],
differential: &mut DenseMat,
) {
let (words, degree) = (source.words.as_slice(), context.degree);
let first =
words == &target[1..] && source.start == context.algebra.basis()[target[0]].target();
let last = words == &target[..degree] && source.start == coordinate.source;
let middles = middle_coefficients(context, words, target, products);
if !first && !last && middles.is_empty() {
return;
}
for row in source.rows.clone() {
let output = context.source_layout.coordinates[row].output;
if first {
coordinate.add_product(differential, row, target[0], output, false);
}
for &value in &middles {
coordinate.add(differential, row, output, value);
}
if last {
let negative = context.target_degree % 2 == 1;
coordinate.add_product(differential, row, output, target[degree], negative);
}
}
}
fn middle_coefficients(
context: &DifferentialContext,
source: &[BasisIdx],
target: &[BasisIdx],
products: &[Vec<(BasisIdx, Fp)>],
) -> Vec<Fp> {
let mut values = Vec::new();
for (i, product) in (1..=context.degree).zip(products) {
for &(middle, coefficient) in product {
if matches_middle(source, target, i, middle) {
values.push(signed(coefficient, i % 2 == 1, context.field));
}
}
}
values
}
fn matches_middle(source: &[BasisIdx], target: &[BasisIdx], i: usize, middle: BasisIdx) -> bool {
source[..i - 1] == target[..i - 1] && source[i - 1] == middle && source[i..] == target[i + 1..]
}
fn signed(value: Fp, negative: bool, field: &PrimeField) -> Fp {
if negative { field.neg(value) } else { value }
}
struct TargetCoordinate<'a> {
algebra: &'a Algebra,
offsets: &'a [usize],
tuple_rank: usize,
source: u32,
target: u32,
field: &'a PrimeField,
}
impl TargetCoordinate<'_> {
fn add(&self, matrix: &mut DenseMat, row: usize, output: BasisIdx, value: Fp) {
let position = self
.algebra
.paths_between(self.source, self.target)
.binary_search(&output)
.expect("a bar differential stays in the target component");
let column = self.offsets[self.tuple_rank] + position;
matrix.set(row, column, self.field.add(matrix.get(row, column), value));
}
fn add_product(
&self,
matrix: &mut DenseMat,
row: usize,
left: BasisIdx,
right: BasisIdx,
negative: bool,
) {
for &(output, value) in self.algebra.mul_basis(left, right).iter() {
self.add(matrix, row, output, signed(value, negative, self.field));
}
}
}