mod integer;
mod witness;
pub use witness::{DerivedInequivalenceWitness, WitnessError};
use std::sync::Arc;
use crate::algebra::Algebra;
use crate::control::ComputationControl;
use crate::gentle::{AagFunction, GentleError, GentlePresentation, WindingClass};
use crate::hochschild::{
BarBudgetDiagnostics, BarLimits, HochschildDegree, HochschildError, HochschildOutcome,
bar_hochschild,
};
use integer::{Checked, Overflow};
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[non_exhaustive]
pub enum DerivedInvariantKind {
VertexCount,
CartanDeterminant,
CartanFactors,
SymmetricFactors,
SkewFactors,
CartanPencil,
AagFunction,
WindingClass,
HochschildDimensions,
CenterDimension,
}
impl DerivedInvariantKind {
pub const ALL: [DerivedInvariantKind; 10] = [
DerivedInvariantKind::VertexCount,
DerivedInvariantKind::CartanDeterminant,
DerivedInvariantKind::CartanFactors,
DerivedInvariantKind::SymmetricFactors,
DerivedInvariantKind::SkewFactors,
DerivedInvariantKind::CartanPencil,
DerivedInvariantKind::AagFunction,
DerivedInvariantKind::WindingClass,
DerivedInvariantKind::HochschildDimensions,
DerivedInvariantKind::CenterDimension,
];
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum InvariantValue {
Count(usize),
Integer(i128),
Factors(Vec<i128>),
Polynomial(Vec<i128>),
AagFunction(AagFunction),
WindingClass(WindingClass),
Dimensions(Vec<usize>),
}
impl InvariantValue {
pub fn differs_from(&self, other: &InvariantValue) -> bool {
match (self, other) {
(InvariantValue::Dimensions(left), InvariantValue::Dimensions(right)) => {
left.iter().zip(right).any(|(left, right)| left != right)
}
_ => self != other,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum InvariantStop {
Overflow,
BarCut(Box<BarBudgetDiagnostics>),
Cancelled,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum InvariantReading {
Finished(InvariantValue),
Stopped(InvariantStop),
NotApplicable(GentleError),
}
impl InvariantReading {
pub fn separates(&self, other: &InvariantReading) -> bool {
matches!(
(self, other),
(InvariantReading::Finished(left), InvariantReading::Finished(right))
if left.differs_from(right)
)
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct InvariantLimits {
pub hochschild_degree: usize,
pub bar: BarLimits,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum HochschildEnd {
Complete,
Stopped(InvariantStop),
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct HochschildDimensions {
requested_degree: usize,
dimensions: Vec<usize>,
end: HochschildEnd,
}
impl HochschildDimensions {
accessor_methods! {
pub requested_degree() -> usize = |this| this.requested_degree;
pub dimensions() -> &[usize] = |this| &this.dimensions;
pub end() -> &HochschildEnd = |this| &this.end;
}
fn compute(
algebra: &Arc<Algebra>,
limits: InvariantLimits,
control: &ComputationControl,
) -> Result<HochschildDimensions, HochschildError> {
let requested_degree = limits.hochschild_degree;
let dimensions = |degrees: &[HochschildDegree]| degrees.iter().map(|d| d.dim()).collect();
let (dimensions, end) = if control.is_cancelled() {
(Vec::new(), HochschildEnd::Stopped(InvariantStop::Cancelled))
} else {
match bar_hochschild(algebra, requested_degree, limits.bar)? {
HochschildOutcome::Complete(value) => {
(dimensions(value.degrees()), HochschildEnd::Complete)
}
HochschildOutcome::Cut(cut) => (
dimensions(cut.completed_degrees()),
HochschildEnd::Stopped(InvariantStop::BarCut(Box::new(
cut.diagnostics().clone(),
))),
),
}
};
Ok(HochschildDimensions {
requested_degree,
dimensions,
end,
})
}
fn dimensions_reading(&self) -> InvariantReading {
let finished = !self.dimensions.is_empty();
self.reading(finished.then(|| InvariantValue::Dimensions(self.dimensions.clone())))
}
fn center_reading(&self) -> InvariantReading {
self.reading(self.dimensions.first().copied().map(InvariantValue::Count))
}
fn reading(&self, value: Option<InvariantValue>) -> InvariantReading {
match (value, &self.end) {
(Some(value), _) => InvariantReading::Finished(value),
(None, HochschildEnd::Stopped(stop)) => InvariantReading::Stopped(stop.clone()),
(None, HochschildEnd::Complete) => unreachable!("a complete bar result has HH^0"),
}
}
}
#[derive(Clone, Debug)]
pub struct DerivedInvariants {
algebra: Arc<Algebra>,
limits: InvariantLimits,
readings: Vec<InvariantReading>,
hochschild: HochschildDimensions,
}
impl DerivedInvariants {
pub fn compute(
algebra: &Arc<Algebra>,
limits: InvariantLimits,
control: &ComputationControl,
) -> Result<DerivedInvariants, HochschildError> {
let mut evaluator = Evaluator::new(algebra, limits, control);
let readings = DerivedInvariantKind::ALL
.iter()
.map(|&kind| evaluator.reading(kind))
.collect::<Result<Vec<_>, _>>()?;
let hochschild = evaluator.hochschild()?.clone();
Ok(DerivedInvariants {
algebra: algebra.clone(),
limits,
readings,
hochschild,
})
}
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.algebra;
pub limits() -> InvariantLimits = |this| this.limits;
pub hochschild() -> &HochschildDimensions = |this| &this.hochschild;
pub reading(kind: DerivedInvariantKind) -> &InvariantReading = |this| &this.readings[kind as usize];
}
}
pub fn derived_invariant(
algebra: &Arc<Algebra>,
kind: DerivedInvariantKind,
limits: InvariantLimits,
control: &ComputationControl,
) -> Result<InvariantReading, HochschildError> {
Evaluator::new(algebra, limits, control).reading(kind)
}
pub fn first_difference(
left: &DerivedInvariants,
right: &DerivedInvariants,
) -> Option<DerivedInvariantKind> {
DerivedInvariantKind::ALL
.into_iter()
.find(|&kind| left.reading(kind).separates(right.reading(kind)))
}
struct Evaluator<'a> {
algebra: &'a Arc<Algebra>,
limits: InvariantLimits,
control: &'a ComputationControl,
cartan: Checked<Vec<Vec<i128>>>,
hochschild: Option<HochschildDimensions>,
}
impl<'a> Evaluator<'a> {
fn new(
algebra: &'a Arc<Algebra>,
limits: InvariantLimits,
control: &'a ComputationControl,
) -> Evaluator<'a> {
let cartan = algebra
.cartan_matrix()
.into_iter()
.map(|row| {
row.into_iter()
.map(|e| i128::try_from(e).map_err(|_| Overflow))
.collect()
})
.collect();
Evaluator {
algebra,
limits,
control,
cartan,
hochschild: None,
}
}
fn hochschild(&mut self) -> Result<&HochschildDimensions, HochschildError> {
let value = match self.hochschild.take() {
Some(value) => value,
None => HochschildDimensions::compute(self.algebra, self.limits, self.control)?,
};
Ok(self.hochschild.insert(value))
}
fn integer(
&self,
value: impl FnOnce(&[Vec<i128>]) -> Checked<InvariantValue>,
) -> InvariantReading {
match self
.cartan
.as_deref()
.map_err(|&error| error)
.and_then(value)
{
Ok(value) => InvariantReading::Finished(value),
Err(Overflow) => InvariantReading::Stopped(InvariantStop::Overflow),
}
}
fn reading(&mut self, kind: DerivedInvariantKind) -> Result<InvariantReading, HochschildError> {
use DerivedInvariantKind as Kind;
Ok(match kind {
Kind::VertexCount => InvariantReading::Finished(InvariantValue::Count(
self.algebra.quiver().num_vertices() as usize,
)),
Kind::CartanDeterminant
| Kind::CartanFactors
| Kind::SymmetricFactors
| Kind::SkewFactors
| Kind::CartanPencil => self.integer(|cartan| cartan_value(kind, cartan)),
Kind::AagFunction => gentle_reading(self.algebra, |gentle| {
InvariantValue::AagFunction(gentle.aag_function())
}),
Kind::WindingClass => gentle_reading(self.algebra, |gentle| {
InvariantValue::WindingClass(gentle.complete_invariant().winding_class())
}),
Kind::HochschildDimensions => self.hochschild()?.dimensions_reading(),
Kind::CenterDimension => self.hochschild()?.center_reading(),
})
}
}
fn cartan_value(kind: DerivedInvariantKind, cartan: &[Vec<i128>]) -> Checked<InvariantValue> {
use DerivedInvariantKind as Kind;
match kind {
Kind::CartanDeterminant => integer::determinant(cartan).map(InvariantValue::Integer),
Kind::CartanFactors => integer::invariant_factors(cartan).map(InvariantValue::Factors),
Kind::SymmetricFactors => transpose_factors(cartan, 1),
Kind::SkewFactors => transpose_factors(cartan, -1),
Kind::CartanPencil => integer::pencil(cartan).map(InvariantValue::Polynomial),
Kind::VertexCount
| Kind::AagFunction
| Kind::WindingClass
| Kind::HochschildDimensions
| Kind::CenterDimension => {
unreachable!("{kind:?} is not read from the Cartan matrix")
}
}
}
fn gentle_reading(
algebra: &Arc<Algebra>,
value: impl FnOnce(&GentlePresentation) -> InvariantValue,
) -> InvariantReading {
match GentlePresentation::new(algebra) {
Ok(presentation) => InvariantReading::Finished(value(&presentation)),
Err(error) => InvariantReading::NotApplicable(error),
}
}
fn transpose_factors(matrix: &[Vec<i128>], sign: i128) -> Checked<InvariantValue> {
integer::invariant_factors(&integer::with_transpose(matrix, 1, sign)?)
.map(InvariantValue::Factors)
}
#[cfg(test)]
mod tests;