ext/chain_complex/
chain_homotopy.rs

1use std::sync::{Arc, Mutex};
2
3use algebra::module::{
4    Module,
5    homomorphism::{FreeModuleHomomorphism, ModuleHomomorphism},
6};
7use fp::{prime::ValidPrime, vector::FpVector};
8use maybe_rayon::prelude::*;
9use once::OnceBiVec;
10use sseq::coordinates::{Bidegree, BidegreeRange};
11
12use crate::{
13    chain_complex::{ChainComplex, FreeChainComplex},
14    resolution_homomorphism::ResolutionHomomorphism,
15    save::{SaveDirectory, SaveKind},
16};
17
18// Another instance of https://github.com/rust-lang/rust/issues/91380
19/// A chain homotopy from $f to g$, or equivalently a null-homotopy of $h = f - g$. A chain map is
20/// a priori a collection of free module homomorphisms. However, instead of providing
21/// FreeModuleHomomorphism objects, the user is expected to give a function that computes the value
22/// of $h$ on each generator.
23#[doc(hidden)]
24pub struct ChainHomotopy<
25    S: FreeChainComplex,
26    T: FreeChainComplex<Algebra = S::Algebra> + Sync,
27    U: ChainComplex<Algebra = S::Algebra> + Sync,
28> {
29    left: Arc<ResolutionHomomorphism<S, T>>,
30    right: Arc<ResolutionHomomorphism<T, U>>,
31    lock: Mutex<()>,
32    /// Homotopies, indexed by the filtration of the target of f - g.
33    homotopies: OnceBiVec<Arc<FreeModuleHomomorphism<U::Module>>>,
34    save_dir: SaveDirectory,
35}
36
37impl<
38    S: FreeChainComplex,
39    T: FreeChainComplex<Algebra = S::Algebra> + Sync,
40    U: ChainComplex<Algebra = S::Algebra> + Sync,
41> ChainHomotopy<S, T, U>
42{
43    pub fn new(
44        left: Arc<ResolutionHomomorphism<S, T>>,
45        right: Arc<ResolutionHomomorphism<T, U>>,
46    ) -> Self {
47        let save_dir = if left.source.save_dir().is_some()
48            && !left.name().is_empty()
49            && !right.name().is_empty()
50        {
51            let mut save_dir = left.source.save_dir().clone();
52            save_dir.push(format!("massey/{},{}/", left.name(), right.name()));
53
54            SaveKind::ChainHomotopy
55                .create_dir(save_dir.write().unwrap())
56                .unwrap();
57
58            save_dir
59        } else {
60            SaveDirectory::None
61        };
62
63        assert!(Arc::ptr_eq(&left.target, &right.source));
64        Self {
65            homotopies: OnceBiVec::new((left.shift + right.shift).s() - 1),
66            left,
67            right,
68            lock: Mutex::new(()),
69            save_dir,
70        }
71    }
72
73    pub fn prime(&self) -> ValidPrime {
74        self.left.source.prime()
75    }
76
77    pub fn shift(&self) -> Bidegree {
78        self.left.shift + self.right.shift
79    }
80
81    pub fn left(&self) -> Arc<ResolutionHomomorphism<S, T>> {
82        Arc::clone(&self.left)
83    }
84
85    pub fn right(&self) -> Arc<ResolutionHomomorphism<T, U>> {
86        Arc::clone(&self.right)
87    }
88
89    /// Lift maps so that the chain *homotopy* is defined on `max_source`.
90    pub fn extend(&self, max_source: Bidegree) {
91        self.extend_profile(BidegreeRange::new(&(), max_source.s() + 1, &|_, s| {
92            max_source.t() - max_source.s() + s + 1
93        }));
94    }
95
96    /// Lift maps so that the chain homotopy is defined on as many bidegrees as possible
97    pub fn extend_all(&self) {
98        self.extend_profile(BidegreeRange::new(
99            &self,
100            std::cmp::min(
101                self.left.source.next_homological_degree(),
102                self.right.target.next_homological_degree() + self.shift().s(),
103            ),
104            &|selff, s| {
105                std::cmp::min(
106                    selff.left.source.module(s).max_computed_degree() + 1,
107                    selff
108                        .right
109                        .target
110                        .module(s + 1 - selff.shift().s())
111                        .max_computed_degree()
112                        + selff.shift().t()
113                        + 1,
114                )
115            },
116        ));
117    }
118
119    /// Initialize self.homotopies to contain [`FreeModuleHomomorphisms`]s up to but excluding
120    /// `max_source_s`, which can be returned by [`Self::homotopy`]. This does not actually lift
121    /// the maps, which is done by [`Self::extend_all`] and [`Self::extend`].
122    pub fn initialize_homotopies(&self, max_source_s: i32) {
123        self.homotopies.extend(max_source_s - 1, |s| {
124            Arc::new(FreeModuleHomomorphism::new(
125                self.left.source.module(s),
126                self.right.target.module(s + 1 - self.shift().s()),
127                self.shift().t(),
128            ))
129        });
130    }
131
132    /// Exclusive bounds
133    fn extend_profile<AUX: Sync>(&self, max_source: BidegreeRange<AUX>) {
134        let shift = self.shift();
135
136        if max_source.s() == shift.s() - 1 {
137            return;
138        }
139
140        let _lock = self.lock.lock();
141
142        self.initialize_homotopies(max_source.s());
143
144        let min = Bidegree::s_t(
145            shift.s() - 1,
146            std::cmp::min(
147                self.left.source.min_degree(),
148                self.right.target.min_degree() + shift.t(),
149            ),
150        );
151
152        sseq::coordinates::iter_s_t(&|b| self.extend_step(b), min, max_source);
153    }
154
155    fn extend_step(&self, source: Bidegree) -> std::ops::Range<i32> {
156        let p = self.prime();
157        let shift = self.shift();
158        let target = source + Bidegree::s_t(1, 0) - shift;
159
160        if self.homotopies[source.s()].next_degree() > source.t() {
161            return source.t()..source.t() + 1;
162        }
163
164        let num_gens = self
165            .left
166            .source
167            .module(source.s())
168            .number_of_gens_in_degree(source.t());
169
170        let target_dim = self.right.target.module(target.s()).dimension(target.t());
171
172        // Default to the zero homotopy for the bottom-most homotopy. For computing normal Massey
173        // products, any choice works, and it is conventional to choose zero. For secondary Massey
174        // products, this may have to be non-zero, in which case the user should manually set up
175        // these values.
176        if target.s() == 0 || target_dim == 0 || num_gens == 0 {
177            let outputs = vec![FpVector::new(p, target_dim); num_gens];
178            return self.homotopies[source.s()].add_generators_from_rows_ooo(source.t(), outputs);
179        }
180
181        if let Some(dir) = self.save_dir.read()
182            && let Some(mut f) = self
183                .left
184                .source
185                .save_file(SaveKind::ChainHomotopy, source)
186                .open_file(dir.to_owned())
187        {
188            let mut outputs = Vec::with_capacity(num_gens);
189            for _ in 0..num_gens {
190                outputs.push(FpVector::from_bytes(p, target_dim, &mut f).unwrap());
191            }
192            return self.homotopies[source.s()].add_generators_from_rows_ooo(source.t(), outputs);
193        }
194
195        let mut outputs = vec![FpVector::new(p, target_dim); num_gens];
196
197        let f = |i| {
198            let mut scratch = FpVector::new(
199                p,
200                self.right
201                    .target
202                    .module(target.s() - 1)
203                    .dimension(target.t()),
204            );
205            let left_shifted_b = source - self.left.shift;
206            self.right.get_map(left_shifted_b.s()).apply(
207                scratch.as_slice_mut(),
208                1,
209                left_shifted_b.t(),
210                self.left
211                    .get_map(source.s())
212                    .output(source.t(), i)
213                    .as_slice(),
214            );
215
216            self.homotopies[source.s() - 1].apply(
217                scratch.as_slice_mut(),
218                p - 1,
219                source.t(),
220                self.left
221                    .source
222                    .differential(source.s())
223                    .output(source.t(), i)
224                    .as_slice(),
225            );
226
227            #[cfg(debug_assertions)]
228            if target.s() > 1
229                && self
230                    .right
231                    .target
232                    .has_computed_bidegree(target - Bidegree::s_t(2, 0))
233            {
234                let mut r = FpVector::new(
235                    p,
236                    self.right
237                        .target
238                        .module(target.s() - 2)
239                        .dimension(target.t()),
240                );
241                self.right.target.differential(target.s() - 1).apply(
242                    r.as_slice_mut(),
243                    1,
244                    target.t(),
245                    scratch.as_slice(),
246                );
247                assert!(
248                    r.is_zero(),
249                    "Failed to lift at {target_prev}",
250                    target_prev = target - Bidegree::s_t(1, 0)
251                );
252            }
253
254            scratch
255        };
256
257        let scratches: Vec<FpVector> = (0..num_gens).into_maybe_par_iter().map(f).collect();
258
259        assert!(U::apply_quasi_inverse(
260            &*self.right.target,
261            &mut outputs,
262            target,
263            &scratches,
264        ));
265
266        if let Some(dir) = self.save_dir.write() {
267            let mut f = self
268                .left
269                .source
270                .save_file(SaveKind::ChainHomotopy, source)
271                .create_file(dir.to_owned(), false);
272            for row in &outputs {
273                row.to_bytes(&mut f).unwrap();
274            }
275        }
276        self.homotopies[source.s()].add_generators_from_rows_ooo(source.t(), outputs)
277    }
278
279    pub fn homotopy(&self, source_s: i32) -> Arc<FreeModuleHomomorphism<U::Module>> {
280        Arc::clone(&self.homotopies[source_s])
281    }
282
283    pub fn save_dir(&self) -> &SaveDirectory {
284        &self.save_dir
285    }
286}
ext/chain_complex/chain_homotopy.rs

ext/chain_complex/
chain_homotopy.rs
