use std::sync::Arc;
use rustc_hash::FxHashMap;
use crate::complex::CheckedComplex;
use crate::field::Fp;
use crate::hom::Morphism;
use crate::homspace::{HomSpace, deterministic_complement, row_times, scale_morphism, stack_rows};
use crate::linalg::DenseMat;
use crate::module::Module;
use super::chain::{
ChainHomotopy, ChainMap, ChainMapError, agrees_after_padding, checked_union_range, padded_pair,
rebase_morphism, same_complex_data, shifted_complex,
};
use super::complex::{BoundedComplex, BoundedComplexError};
#[derive(Default)]
pub(crate) struct HomSpaceMemo(FxHashMap<(usize, usize), HomSpace>);
impl HomSpaceMemo {
fn space(&mut self, source: &Module, target: &Module) -> HomSpace {
self.0
.entry((source.addr(), target.addr()))
.or_insert_with(|| {
HomSpace::new(source, target).expect("complex terms share the algebra")
})
.clone()
}
}
#[derive(Clone, Debug)]
pub struct ChainHomSpace {
source: BoundedComplex,
target: BoundedComplex,
components: Vec<HomSpace>,
flat: DenseMat,
}
fn chain_flat(map: &ChainMap, spaces: &[HomSpace]) -> Vec<Fp> {
let mut row = Vec::with_capacity(spaces.iter().map(HomSpace::dim).sum());
for (component, space) in map.components.iter().zip(spaces) {
row.extend(component_coords(component, space));
}
row
}
fn component_coords(component: &Morphism, space: &HomSpace) -> Vec<Fp> {
let rebased;
let component =
if component.source().ptr_eq(space.source()) && component.target().ptr_eq(space.target()) {
component
} else {
rebased = rebase_morphism(component, space.source(), space.target());
&rebased
};
space
.coords(component)
.expect("chain map component has matching endpoints")
}
fn component_offsets(spaces: &[HomSpace]) -> Vec<usize> {
let mut offsets = Vec::with_capacity(spaces.len());
let mut cursor = 0;
for space in spaces {
offsets.push(cursor);
cursor += space.dim();
}
offsets
}
fn chain_map_from_flat(
source: &BoundedComplex,
target: &BoundedComplex,
spaces: &[HomSpace],
row: &[Fp],
) -> ChainMap {
let mut components = Vec::with_capacity(spaces.len());
let mut offset = 0;
for space in spaces {
let end = offset + space.dim();
components.push(space.morphism(&row[offset..end]));
offset = end;
}
ChainMap::new(source, target, components)
.expect("chain Hom kernel rows satisfy the chain equations")
}
fn chain_constraints(
source: &BoundedComplex,
target: &BoundedComplex,
spaces: &[HomSpace],
homs: &mut HomSpaceMemo,
) -> DenseMat {
let width: usize = spaces.iter().map(HomSpace::dim).sum();
let offsets = component_offsets(spaces);
let mut rows: Vec<Vec<Fp>> = Vec::new();
for index in 1..source.len() {
let equation = homs.space(&source.terms[index], &target.terms[index - 1]);
let equation_dim = equation.dim();
let mut contributions: Vec<Vec<Fp>> =
vec![vec![source.terms[0].field().zero(); width]; equation_dim];
for (variable_index, space) in spaces.iter().enumerate() {
for basis_index in 0..space.dim() {
let basis = space.basis_morphism(basis_index);
let contribution = if variable_index == index - 1 {
source.differentials[index - 1]
.then(&basis)
.expect("source differential and component endpoints match")
} else if variable_index == index {
scale_morphism(
&basis
.then(&target.differentials[index - 1])
.expect("component and target differential endpoints match"),
source.terms[0].field().neg(source.terms[0].field().one()),
)
} else {
continue;
};
let coordinates = equation
.coords(&contribution)
.expect("a composite of module morphisms lies in the equation Hom space");
for (row, value) in coordinates.into_iter().enumerate() {
contributions[row][offsets[variable_index] + basis_index] = value;
}
}
}
rows.extend(contributions);
}
DenseMat::from_rows_with_cols(&rows, width)
}
fn homotopy_rows(
source: &BoundedComplex,
target: &BoundedComplex,
spaces: &[HomSpace],
ambient: &DenseMat,
homs: &mut HomSpaceMemo,
) -> DenseMat {
let field = source.terms[0].field();
let offsets = component_offsets(spaces);
let mut rows = Vec::new();
for index in 0..source.len().saturating_sub(1) {
let space = homs.space(&source.terms[index], &target.terms[index + 1]);
for homotopy in space.basis_iter() {
let lower = homotopy
.then(&target.differentials[index])
.expect("homotopy and target differential endpoints match");
let upper = source.differentials[index]
.then(&homotopy)
.expect("source differential and homotopy endpoints match");
let mut row = vec![field.zero(); ambient.cols()];
for (degree, part) in [(index, lower), (index + 1, upper)] {
let coordinates = component_coords(&part, &spaces[degree]);
row[offsets[degree]..offsets[degree] + coordinates.len()]
.copy_from_slice(&coordinates);
}
rows.push(row);
}
}
DenseMat::from_rows_with_cols(&rows, ambient.cols()).row_space_basis(&field)
}
impl ChainHomSpace {
pub fn new(
source: &BoundedComplex,
target: &BoundedComplex,
) -> Result<ChainHomSpace, ChainMapError> {
ChainHomSpace::new_in(source, target, &mut HomSpaceMemo::default())
}
fn new_in(
source: &BoundedComplex,
target: &BoundedComplex,
homs: &mut HomSpaceMemo,
) -> Result<ChainHomSpace, ChainMapError> {
let range = checked_union_range(source, target)?;
let (source, target) = padded_pair(source, target, range)?;
let components: Vec<HomSpace> = source
.terms
.iter()
.zip(&target.terms)
.map(|(source, target)| homs.space(source, target))
.collect();
let constraints = chain_constraints(&source, &target, &components, homs);
let flat = constraints.kernel_basis(&source.terms[0].field());
Ok(ChainHomSpace {
source: source.clone(),
target: target.clone(),
components,
flat,
})
}
accessor_methods! {
pub source() -> &BoundedComplex = |this| &this.source;
pub target() -> &BoundedComplex = |this| &this.target;
pub dim() -> usize = |this| this.flat.rows();
pub basis_rows() -> &DenseMat = |this| &this.flat;
}
pub fn basis_morphism(&self, index: usize) -> ChainMap {
chain_map_from_flat(
&self.source,
&self.target,
&self.components,
self.flat.row(index),
)
}
pub fn basis_iter(&self) -> impl Iterator<Item = ChainMap> + '_ {
(0..self.dim()).map(|index| self.basis_morphism(index))
}
pub fn morphism(&self, coordinates: &[Fp]) -> ChainMap {
assert_eq!(coordinates.len(), self.dim());
let row = row_times(coordinates, &self.flat, &self.source.terms[0].field());
chain_map_from_flat(&self.source, &self.target, &self.components, &row)
}
pub fn coords(&self, map: &ChainMap) -> Result<Vec<Fp>, ChainMapError> {
self.flat
.row_coords(&self.flat_row(map)?, &self.source.terms[0].field())
.ok_or(ChainMapError::OutsideHomSpace)
}
fn flat_row(&self, map: &ChainMap) -> Result<Vec<Fp>, ChainMapError> {
let map = map
.aligned_to(self.source.range)
.map_err(|_| ChainMapError::OutsideHomSpace)?;
if !same_complex_data(&self.source, &map.source)
|| !same_complex_data(&self.target, &map.target)
{
return Err(ChainMapError::OutsideHomSpace);
}
Ok(chain_flat(&map, &self.components))
}
pub fn verify(&self) -> bool {
let Ok(rebuilt) = ChainHomSpace::new(&self.source, &self.target) else {
return false;
};
rebuilt.flat == self.flat
}
pub fn quotient(&self) -> Result<ChainHomQuotient, ChainMapError> {
self.quotient_in(&mut HomSpaceMemo::default())
}
fn quotient_in(&self, homs: &mut HomSpaceMemo) -> Result<ChainHomQuotient, ChainMapError> {
let null = homotopy_rows(
&self.source,
&self.target,
&self.components,
&self.flat,
homs,
);
for row in 0..null.rows() {
if self
.flat
.row_coords(null.row(row), &self.source.terms[0].field())
.is_none()
{
return Err(ChainMapError::OutsideHomSpace);
}
}
let complement = deterministic_complement(&self.flat, &null, &self.source.terms[0].field());
Ok(ChainHomQuotient {
space: self.clone(),
null,
complement,
})
}
}
impl CheckedComplex {
pub fn bounded(&self, lower: i32) -> Result<BoundedComplex, BoundedComplexError> {
BoundedComplex::from_checked(self, lower)
}
}
#[derive(Clone, Debug)]
pub struct ChainHomQuotient {
space: ChainHomSpace,
null: DenseMat,
complement: DenseMat,
}
impl ChainHomQuotient {
accessor_methods! {
pub source() -> &BoundedComplex = |this| this.space.source();
pub target() -> &BoundedComplex = |this| this.space.target();
pub dim() -> usize = |this| this.complement.rows();
pub null_homotopic_basis() -> &DenseMat = |this| &this.null;
pub complement_basis() -> &DenseMat = |this| &this.complement;
}
pub fn verify(&self) -> bool {
self.space.verify()
&& self.space.quotient().is_ok_and(|rebuilt| {
rebuilt.null == self.null && rebuilt.complement == self.complement
})
}
pub fn representative(&self, coordinates: &[Fp]) -> ChainMap {
assert_eq!(coordinates.len(), self.dim());
let row = row_times(
coordinates,
&self.complement,
&self.space.source.terms[0].field(),
);
chain_map_from_flat(
&self.space.source,
&self.space.target,
&self.space.components,
&row,
)
}
pub fn reduce(&self, map: &ChainMap) -> Result<(Vec<Fp>, ChainMap), ChainMapError> {
let field = self.space.source.terms[0].field();
let row = self.space.flat_row(map)?;
let stacked = stack_rows(&[&self.complement, &self.null], self.complement.cols());
let Some(coordinates) = stacked.transpose().solve(&row, &field) else {
return Err(ChainMapError::OutsideHomSpace);
};
let quotient_coordinates = coordinates[..self.complement.rows()].to_vec();
let null_row = row_times(&coordinates[self.complement.rows()..], &self.null, &field);
Ok((
quotient_coordinates,
chain_map_from_flat(
&self.space.source,
&self.space.target,
&self.space.components,
&null_row,
),
))
}
}
#[derive(Clone, Debug)]
pub struct HomotopyHom {
degree: i32,
source: BoundedComplex,
target: BoundedComplex,
shifted_target: BoundedComplex,
space: ChainHomSpace,
}
impl HomotopyHom {
pub fn new(
source: &BoundedComplex,
target: &BoundedComplex,
degree: i32,
) -> Result<HomotopyHom, ChainMapError> {
HomotopyHom::new_in(source, target, degree, &mut HomSpaceMemo::default())
}
pub(crate) fn new_in(
source: &BoundedComplex,
target: &BoundedComplex,
degree: i32,
homs: &mut HomSpaceMemo,
) -> Result<HomotopyHom, ChainMapError> {
let shifted_target = shifted_complex(target, degree)?;
let space = ChainHomSpace::new_in(source, &shifted_target, homs)?;
Ok(HomotopyHom {
degree,
source: source.clone(),
target: target.clone(),
shifted_target,
space,
})
}
accessor_methods! {
pub degree() -> i32 = |this| this.degree;
pub source() -> &BoundedComplex = |this| &this.source;
pub target() -> &BoundedComplex = |this| &this.target;
pub shifted_target() -> &BoundedComplex = |this| &this.shifted_target;
pub chain_space() -> &ChainHomSpace = |this| &this.space;
pub dim() -> usize = |this| this.space.dim();
pub basis_rows() -> &DenseMat = |this| this.space.basis_rows();
}
pub fn basis_morphism(&self, index: usize) -> ChainMap {
self.space.basis_morphism(index)
}
pub fn basis_iter(&self) -> impl Iterator<Item = ChainMap> + '_ {
self.space.basis_iter()
}
pub fn morphism(&self, coordinates: &[Fp]) -> ChainMap {
self.space.morphism(coordinates)
}
pub fn coords(&self, map: &ChainMap) -> Result<Vec<Fp>, ChainMapError> {
self.space.coords(map)
}
pub fn verify(&self) -> bool {
let Ok(shifted_target) = shifted_complex(&self.target, self.degree) else {
return false;
};
agrees_after_padding(&self.source, self.space.source())
&& self.shifted_target.agrees_with(&shifted_target)
&& agrees_after_padding(&self.shifted_target, self.space.target())
&& self.space.verify()
}
pub fn quotient(&self) -> Result<HomotopyHomQuotient, ChainMapError> {
self.clone().into_quotient(&mut HomSpaceMemo::default())
}
pub(crate) fn into_quotient(
self,
homs: &mut HomSpaceMemo,
) -> Result<HomotopyHomQuotient, ChainMapError> {
let quotient = Arc::new(self.space.quotient_in(homs)?);
Ok(HomotopyHomQuotient {
hom: Arc::new(self),
quotient,
})
}
}
#[derive(Clone, Debug)]
pub struct HomotopyHomQuotient {
hom: Arc<HomotopyHom>,
quotient: Arc<ChainHomQuotient>,
}
impl HomotopyHomQuotient {
accessor_methods! {
pub hom() -> &HomotopyHom = |this| &this.hom;
pub degree() -> i32 = |this| this.hom.degree();
pub source() -> &BoundedComplex = |this| this.hom.source();
pub target() -> &BoundedComplex = |this| this.hom.target();
pub shifted_target() -> &BoundedComplex = |this| this.hom.shifted_target();
pub dim() -> usize = |this| this.quotient.dim();
pub null_homotopic_basis() -> &DenseMat = |this| this.quotient.null_homotopic_basis();
pub complement_basis() -> &DenseMat = |this| this.quotient.complement_basis();
}
pub fn verify(&self) -> bool {
self.hom.verify()
&& self.quotient.verify()
&& agrees_after_padding(self.hom.source(), self.quotient.source())
&& agrees_after_padding(self.hom.shifted_target(), self.quotient.target())
}
pub fn representative(&self, coordinates: &[Fp]) -> ChainMap {
self.quotient.representative(coordinates)
}
pub fn reduce(&self, map: &ChainMap) -> Result<(Vec<Fp>, ChainMap), ChainMapError> {
self.quotient.reduce(map)
}
}
impl ChainMap {
pub fn is_null_homotopic(&self) -> Result<bool, ChainMapError> {
let quotient = ChainHomSpace::new(&self.source, &self.target)
.map_err(|_| ChainMapError::OutsideHomSpace)?
.quotient()?;
Ok(quotient.reduce(self)?.0.iter().all(|x| x.is_zero()))
}
}
pub type DegreeComplex = BoundedComplex;
pub type Homotopy = ChainHomotopy;