algebra/module/homomorphism/
hom_pullback.rs

1use std::sync::Arc;
2
3use fp::{
4    matrix::{QuasiInverse, Subspace},
5    vector::FpSliceMut,
6};
7use once::OnceBiVec;
8
9use crate::module::{
10    FreeModule, HomModule, Module,
11    block_structure::GeneratorBasisEltPair,
12    homomorphism::{FreeModuleHomomorphism, ModuleHomomorphism},
13};
14
15/// Given a map $\mathtt{map}: A \to B$ and hom modules $\mathtt{source} = \Hom(B, X)$, $\mathtt{target} = \Hom(A, X)$, produce the induced pullback map $\Hom(B, X) \to \Hom(A, X)$.
16pub struct HomPullback<M: Module> {
17    source: Arc<HomModule<M>>,
18    target: Arc<HomModule<M>>,
19    map: Arc<FreeModuleHomomorphism<FreeModule<M::Algebra>>>,
20    images: OnceBiVec<Subspace>,
21    kernels: OnceBiVec<Subspace>,
22    quasi_inverses: OnceBiVec<QuasiInverse>,
23}
24
25impl<M: Module> HomPullback<M> {
26    pub fn new(
27        source: Arc<HomModule<M>>,
28        target: Arc<HomModule<M>>,
29        map: Arc<FreeModuleHomomorphism<FreeModule<M::Algebra>>>,
30    ) -> Self {
31        assert!(Arc::ptr_eq(&source.source(), &map.target()));
32        assert!(Arc::ptr_eq(&target.source(), &map.source()));
33        assert!(Arc::ptr_eq(&source.target(), &target.target()));
34
35        let min_degree = source.min_degree();
36        Self {
37            source,
38            target,
39            map,
40            images: OnceBiVec::new(min_degree),
41            kernels: OnceBiVec::new(min_degree),
42            quasi_inverses: OnceBiVec::new(min_degree),
43        }
44    }
45}
46
47impl<M: Module> ModuleHomomorphism for HomPullback<M> {
48    type Source = HomModule<M>;
49    type Target = HomModule<M>;
50
51    fn source(&self) -> Arc<Self::Source> {
52        Arc::clone(&self.source)
53    }
54
55    fn target(&self) -> Arc<Self::Target> {
56        Arc::clone(&self.target)
57    }
58
59    fn degree_shift(&self) -> i32 {
60        -self.map.degree_shift()
61    }
62
63    fn min_degree(&self) -> i32 {
64        self.source().min_degree()
65    }
66
67    fn apply_to_basis_element(
68        &self,
69        mut result: FpSliceMut,
70        coeff: u32,
71        fn_degree: i32,
72        fn_idx: usize,
73    ) {
74        let GeneratorBasisEltPair {
75            generator_degree,
76            generator_index,
77            basis_index,
78        } = self.source.block_structures[fn_degree].index_to_generator_basis_elt(fn_idx);
79
80        let target_module = self.target.target(); // == self.source.target()
81        let source_free_module = self.source.source();
82        let target_free_module = self.target.source();
83        let degree_shift = self.map.degree_shift();
84
85        let max_degree = fn_degree + degree_shift + target_module.max_degree().unwrap();
86        let min_degree = std::cmp::max(
87            *generator_degree + degree_shift,
88            fn_degree + degree_shift + target_module.min_degree(),
89        );
90
91        for (target_gen_deg, target_gen_idx) in target_free_module
92            .iter_gens(max_degree)
93            .filter(|(t, _)| *t >= min_degree)
94        {
95            let target_range = self.target.block_structures[fn_degree + degree_shift]
96                .generator_to_block(target_gen_deg, target_gen_idx);
97
98            let slice = source_free_module.slice_vector(
99                target_gen_deg - degree_shift,
100                *generator_degree,
101                *generator_index,
102                self.map.output(target_gen_deg, target_gen_idx).as_slice(),
103            );
104
105            // Needed if the output is shorter due to resolve_through_stem
106            if slice.is_empty() {
107                continue;
108            }
109            target_module.act_by_element_on_basis(
110                result.slice_mut(target_range.start, target_range.end),
111                coeff,
112                target_gen_deg - degree_shift - *generator_degree,
113                slice,
114                *generator_degree - fn_degree,
115                *basis_index,
116            );
117        }
118    }
119
120    fn compute_auxiliary_data_through_degree(&self, degree: i32) {
121        self.kernels.extend(degree, |i| {
122            let (image, kernel, qi) = self.auxiliary_data(i);
123            self.images.push_checked(image, i);
124            self.quasi_inverses.push_checked(qi, i);
125            kernel
126        });
127    }
128
129    fn quasi_inverse(&self, degree: i32) -> Option<&QuasiInverse> {
130        self.quasi_inverses.get(degree)
131    }
132
133    fn kernel(&self, degree: i32) -> Option<&Subspace> {
134        self.kernels.get(degree)
135    }
136
137    fn image(&self, degree: i32) -> Option<&Subspace> {
138        self.images.get(degree)
139    }
140}
141
142#[cfg(test)]
143mod tests {
144    use bivec::BiVec;
145    use fp::{matrix::Matrix, vector::FpVector};
146
147    use super::*;
148    use crate::{MilnorAlgebra, module::FDModule};
149
150    #[test]
151    fn test_pullback_id() {
152        const SHIFT: i32 = 2;
153        const NUM_GENS: [usize; 3] = [1, 2, 1];
154
155        let p = fp::prime::TWO;
156
157        let algebra = Arc::new(MilnorAlgebra::new(p, false));
158        let f0 = Arc::new(FreeModule::new(Arc::clone(&algebra), "F0".to_string(), 0));
159        let f1 = Arc::new(FreeModule::new(
160            Arc::clone(&algebra),
161            "F1".to_string(),
162            SHIFT,
163        ));
164        let m = Arc::new(
165            FDModule::from_json(Arc::clone(&algebra), &crate::tests::joker_json()).unwrap(),
166        );
167
168        let d = Arc::new(FreeModuleHomomorphism::new(
169            Arc::clone(&f1),
170            Arc::clone(&f0),
171            SHIFT,
172        ));
173
174        f0.compute_basis(NUM_GENS.len() as i32);
175        f1.compute_basis(NUM_GENS.len() as i32 + SHIFT);
176
177        for (deg, num_gens) in NUM_GENS.into_iter().enumerate() {
178            f0.add_generators(deg as i32, num_gens, None);
179            f1.add_generators(deg as i32 + SHIFT, num_gens, None);
180            let mut rows = vec![FpVector::new(p, f0.dimension(deg as i32)); num_gens];
181            for (i, row) in rows.iter_mut().enumerate() {
182                row.add_basis_element(row.len() - num_gens + i, 1);
183            }
184            d.add_generators_from_rows(deg as i32 + SHIFT, rows);
185        }
186
187        let pb = HomPullback::new(
188            Arc::new(HomModule::new(f0, Arc::clone(&m))),
189            Arc::new(HomModule::new(f1, Arc::clone(&m))),
190            d,
191        );
192
193        pb.source.compute_basis(-2);
194        pb.target.compute_basis(-2 + SHIFT);
195
196        for deg in pb.source.min_degree()..=pb.source.max_computed_degree() {
197            let dim = pb.source.dimension(deg);
198            let mut matrix = Matrix::new(p, dim, dim);
199            pb.get_matrix(matrix.as_slice_mut(), deg);
200            assert_eq!(matrix, Matrix::identity(p, dim));
201        }
202    }
203
204    #[test]
205    fn test_pullback() {
206        const SHIFT: i32 = 3;
207        const NUM_GENS: [usize; 3] = [1, 1, 1];
208
209        let p = fp::prime::TWO;
210
211        let algebra = Arc::new(MilnorAlgebra::new(p, false));
212        let f0 = Arc::new(FreeModule::new(Arc::clone(&algebra), "F0".to_string(), 0));
213        let f1 = Arc::new(FreeModule::new(
214            Arc::clone(&algebra),
215            "F1".to_string(),
216            SHIFT,
217        ));
218        let m = Arc::new(
219            FDModule::from_json(Arc::clone(&algebra), &crate::tests::joker_json()).unwrap(),
220        );
221
222        let d = Arc::new(FreeModuleHomomorphism::new(
223            Arc::clone(&f1),
224            Arc::clone(&f0),
225            SHIFT,
226        ));
227
228        f0.compute_basis(NUM_GENS.len() as i32);
229        f1.compute_basis(NUM_GENS.len() as i32 + SHIFT);
230
231        for (deg, num_gens) in NUM_GENS.into_iter().enumerate() {
232            f0.add_generators(deg as i32, num_gens, None);
233            f1.add_generators(deg as i32 + SHIFT, num_gens, None);
234        }
235
236        d.add_generators_from_rows(SHIFT, vec![FpVector::from_slice(p, &[1])]);
237        d.add_generators_from_rows(SHIFT + 1, vec![FpVector::from_slice(p, &[0, 1])]);
238        d.add_generators_from_rows(SHIFT + 2, vec![FpVector::from_slice(p, &[1, 1, 1])]);
239
240        let pb = HomPullback::new(
241            Arc::new(HomModule::new(f0, Arc::clone(&m))),
242            Arc::new(HomModule::new(f1, Arc::clone(&m))),
243            d,
244        );
245
246        pb.source.compute_basis(-2);
247        pb.target.compute_basis(-2 + SHIFT);
248
249        let outputs = BiVec::from_vec(
250            -4,
251            vec![
252                Matrix::from_vec(p, &[vec![1]]),
253                Matrix::from_vec(p, &[vec![1, 0], vec![0, 1]]),
254                Matrix::from_vec(p, &[vec![1, 0, 1], vec![0, 1, 1], vec![0, 0, 1]]),
255            ],
256        );
257
258        for deg in pb.source.min_degree()..=pb.source.max_computed_degree() {
259            let dim = pb.source.dimension(deg);
260            let mut matrix = Matrix::new(p, dim, dim);
261            pb.get_matrix(matrix.as_slice_mut(), deg);
262            assert_eq!(matrix, outputs[deg]);
263        }
264    }
265}
algebra/module/homomorphism/hom_pullback.rs

algebra/module/homomorphism/
hom_pullback.rs
