ext/chain_complex/
mod.rs

1mod chain_homotopy;
2mod finite_chain_complex;
3
4use std::sync::Arc;
5
6use algebra::{
7    Algebra, MuAlgebra,
8    module::{
9        Module, MuFreeModule,
10        homomorphism::{ModuleHomomorphism, MuFreeModuleHomomorphism},
11    },
12};
13// pub use hom_complex::HomComplex;
14pub use chain_homotopy::ChainHomotopy;
15pub use finite_chain_complex::{FiniteAugmentedChainComplex, FiniteChainComplex};
16use fp::{
17    matrix::Matrix,
18    prime::ValidPrime,
19    vector::{FpSlice, FpSliceMut},
20};
21use itertools::Itertools;
22use sseq::coordinates::{Bidegree, BidegreeGenerator};
23
24use crate::{save::SaveDirectory, utils::unicode_num};
25
26pub enum ChainComplexGrading {
27    Homological,
28    Cohomological,
29}
30
31pub trait FreeChainComplex<const U: bool = false>:
32    ChainComplex<
33        Module = MuFreeModule<U, <Self as ChainComplex>::Algebra>,
34        Homomorphism = MuFreeModuleHomomorphism<
35            U,
36            MuFreeModule<U, <Self as ChainComplex>::Algebra>,
37        >,
38    >
39where
40    <Self as ChainComplex>::Algebra: MuAlgebra<U>,
41{
42    fn graded_dimension_string(&self) -> String {
43        let mut result = String::new();
44        let min_degree = self.min_degree();
45        for s in (0..self.next_homological_degree()).rev() {
46            let module = self.module(s);
47
48            for t in min_degree + s..=module.max_computed_degree() {
49                result.push(unicode_num(module.number_of_gens_in_degree(t)));
50                result.push(' ');
51            }
52            result.push('\n');
53            // If it is empty so far, don't print anything
54            if result.trim_start().is_empty() {
55                result.clear()
56            }
57        }
58        result
59    }
60
61    fn to_sseq(&self) -> sseq::Sseq<2, sseq::Adams> {
62        let p = self.prime();
63        let mut sseq = sseq::Sseq::new(p);
64        for b in self.iter_stem() {
65            sseq.set_dimension(b, self.number_of_gens_in_bidegree(b));
66        }
67        sseq
68    }
69
70    fn filtration_one_products(&self, op_deg: i32, op_idx: usize) -> sseq::Product<2> {
71        let p = self.prime();
72        let matrices = once::MultiIndexed::new();
73        for x in self.min_degree()..self.module(0).max_computed_degree() - op_deg + 2 {
74            let mut b = Bidegree::n_s(x, 0);
75            while self.has_computed_bidegree(b + Bidegree::s_t(1, op_deg)) {
76                if let Some(m) = self.filtration_one_product(op_deg, op_idx, b) {
77                    matrices.insert(b, Matrix::from_vec(p, &m));
78                }
79                b = b + Bidegree::n_s(0, 1);
80            }
81        }
82
83        sseq::Product {
84            b: Bidegree::x_y(op_deg - 1, 1),
85            left: true,
86            matrices,
87        }
88    }
89
90    /// Computes the filtration one product.
91    ///
92    /// # Returns
93    /// If the chain complex is stable, this always returns `Some`. If it is unstable, this returns
94    /// `None` if the product is not defined.
95    fn filtration_one_product(
96        &self,
97        op_deg: i32,
98        op_idx: usize,
99        source: Bidegree,
100    ) -> Option<Vec<Vec<u32>>> {
101        let target = source + Bidegree::s_t(1, op_deg);
102        if !self.has_computed_bidegree(target) {
103            return None;
104        }
105
106        let source_mod = self.module(target.s() - 1);
107        let target_mod = self.module(target.s());
108
109        if U && op_idx >= self.algebra().dimension_unstable(op_deg, source.t()) {
110            return None;
111        }
112
113        let source_dim = source_mod.number_of_gens_in_degree(source.t());
114        let target_dim = target_mod.number_of_gens_in_degree(target.t());
115
116        let d = self.differential(target.s());
117
118        let mut products = vec![Vec::with_capacity(target_dim); source_dim];
119        for i in 0..target_dim {
120            let dx = d.output(target.t(), i);
121
122            for (j, row) in products.iter_mut().enumerate() {
123                let idx = source_mod.operation_generator_to_index(op_deg, op_idx, source.t(), j);
124                row.push(dx.entry(idx));
125            }
126        }
127
128        Some(products)
129    }
130
131    fn number_of_gens_in_bidegree(&self, b: Bidegree) -> usize {
132        self.module(b.s()).number_of_gens_in_degree(b.t())
133    }
134
135    /// Iterate through all nonzero bidegrees in increasing order of stem.
136    fn iter_nonzero_stem(&self) -> impl Iterator<Item = Bidegree> + '_ {
137        self.iter_stem()
138            .filter(move |&b| self.number_of_gens_in_bidegree(b) > 0)
139    }
140
141    /// Get a string representation of d(gen), where d is the differential of the resolution.
142    fn boundary_string(&self, g: BidegreeGenerator) -> String {
143        let d = self.differential(g.s());
144        let target = d.target();
145        let result_vector = d.output(g.t(), g.idx());
146
147        target.element_to_string(g.t(), result_vector.as_slice())
148    }
149}
150
151impl<const U: bool, CC> FreeChainComplex<U> for CC
152where
153    CC: ChainComplex<
154            Module = MuFreeModule<U, Self::Algebra>,
155            Homomorphism = MuFreeModuleHomomorphism<U, MuFreeModule<U, Self::Algebra>>,
156        >,
157    Self::Algebra: MuAlgebra<U>,
158{
159}
160
161/// A chain complex is defined to start in degree 0. The min_degree is the min_degree of the
162/// modules in the chain complex, all of which must be the same.
163pub trait ChainComplex: Send + Sync {
164    type Algebra: Algebra;
165    type Module: Module<Algebra = Self::Algebra>;
166    type Homomorphism: ModuleHomomorphism<Source = Self::Module, Target = Self::Module>;
167
168    fn prime(&self) -> ValidPrime {
169        self.algebra().prime()
170    }
171
172    fn algebra(&self) -> Arc<Self::Algebra>;
173    fn min_degree(&self) -> i32;
174    fn zero_module(&self) -> Arc<Self::Module>;
175    fn module(&self, homological_degree: i32) -> Arc<Self::Module>;
176
177    /// This returns the differential starting from the sth module.
178    fn differential(&self, s: i32) -> Arc<Self::Homomorphism>;
179
180    /// If the complex has been computed at bidegree (s, t). This means the module has been
181    /// computed at (s, t), and so has the differential at (s, t). In the case of a free module,
182    /// the target of the differential, namely the bidegree (s - 1, t), need not be computed, as
183    /// long as all the generators hit by the differential have already been computed.
184    fn has_computed_bidegree(&self, b: Bidegree) -> bool;
185
186    /// Ensure all bidegrees less than or equal to (s, t) have been computed
187    fn compute_through_bidegree(&self, b: Bidegree);
188
189    /// The first s such that `self.module(s)` is not defined.
190    fn next_homological_degree(&self) -> i32;
191
192    /// Iterate through all defined bidegrees in increasing order of stem.
193    fn iter_stem(&self) -> StemIterator<'_, Self> {
194        StemIterator {
195            cc: self,
196            current: Bidegree::n_s(self.min_degree(), 0),
197            max_s: self.next_homological_degree(),
198        }
199    }
200
201    /// Apply the quasi-inverse of the (s, t)th differential to the list of inputs and results.
202    /// This defaults to applying `self.differentials(s).quasi_inverse(t)`, but in some cases
203    /// the quasi-inverse might be stored separately on disk.
204    ///
205    /// This returns whether the application was successful
206    #[must_use]
207    fn apply_quasi_inverse<T, S>(&self, results: &mut [T], b: Bidegree, inputs: &[S]) -> bool
208    where
209        for<'a> &'a mut T: Into<FpSliceMut<'a>>,
210        for<'a> &'a S: Into<FpSlice<'a>>,
211    {
212        assert_eq!(results.len(), inputs.len());
213        if results.is_empty() {
214            return true;
215        }
216
217        let mut iter = inputs.iter().zip_eq(results);
218        let (input, result) = iter.next().unwrap();
219        let d = self.differential(b.s());
220        if d.apply_quasi_inverse(result.into(), b.t(), input.into()) {
221            for (input, result) in iter {
222                assert!(d.apply_quasi_inverse(result.into(), b.t(), input.into()));
223            }
224            true
225        } else {
226            false
227        }
228    }
229
230    /// A directory used to save information about the chain complex.
231    fn save_dir(&self) -> &SaveDirectory {
232        &SaveDirectory::None
233    }
234
235    /// Get the save file of a bidegree
236    fn save_file(
237        &self,
238        kind: crate::save::SaveKind,
239        b: Bidegree,
240    ) -> crate::save::SaveFile<Self::Algebra> {
241        crate::save::SaveFile {
242            algebra: self.algebra(),
243            kind,
244            b,
245            idx: None,
246        }
247    }
248}
249
250/// An iterator returned by [`ChainComplex::iter_stem`]
251pub struct StemIterator<'a, CC: ?Sized> {
252    cc: &'a CC,
253    current: Bidegree,
254    max_s: i32,
255}
256
257impl<CC: ChainComplex + ?Sized> Iterator for StemIterator<'_, CC> {
258    type Item = Bidegree;
259
260    fn next(&mut self) -> Option<Self::Item> {
261        if self.max_s == 0 {
262            return None;
263        }
264        let cur = self.current;
265
266        if cur.s() == self.max_s {
267            self.current = Bidegree::n_s(cur.n() + 1, 0);
268            return self.next();
269        }
270        if cur.t() > self.cc.module(cur.s()).max_computed_degree() {
271            if cur.s() == 0 {
272                return None;
273            } else {
274                self.current = Bidegree::n_s(cur.n() + 1, 0);
275                return self.next();
276            }
277        }
278        self.current = cur + Bidegree::n_s(0, 1);
279        Some(cur)
280    }
281}
282
283/// An augmented chain complex is a map of chain complexes C -> D that is a *quasi-isomorphism*. We
284/// usually think of C as a resolution of D. The chain map must be a map of degree shift 0.
285pub trait AugmentedChainComplex: ChainComplex {
286    type TargetComplex: ChainComplex<Algebra = Self::Algebra>;
287    type ChainMap: ModuleHomomorphism<
288            Source = Self::Module,
289            Target = <Self::TargetComplex as ChainComplex>::Module,
290        >;
291
292    fn target(&self) -> Arc<Self::TargetComplex>;
293    fn chain_map(&self, s: i32) -> Arc<Self::ChainMap>;
294}
295
296/// A bounded chain complex is a chain complex C for which C_s = 0 for all s >= max_s
297pub trait BoundedChainComplex: ChainComplex {
298    fn max_s(&self) -> i32;
299
300    fn euler_characteristic(&self, t: i32) -> isize {
301        (0..self.max_s())
302            .map(|s| (if s % 2 == 0 { 1 } else { -1 }) * self.module(s).dimension(t) as isize)
303            .sum()
304    }
305}
306
307/// `chain_maps` is required to be non-empty
308pub struct ChainMap<F: ModuleHomomorphism> {
309    pub s_shift: i32,
310    pub chain_maps: Vec<F>,
311}
ext/chain_complex/mod.rs

ext/chain_complex/
mod.rs
