algebra/module/homomorphism/
free_module_homomorphism.rs

1use std::sync::Arc;
2
3use fp::{
4    matrix::{MatrixSliceMut, QuasiInverse, Subspace},
5    vector::{FpSlice, FpSliceMut, FpVector},
6};
7use once::OnceBiVec;
8
9use crate::{
10    algebra::MuAlgebra,
11    module::{
12        Module, MuFreeModule,
13        free_module::OperationGeneratorPair,
14        homomorphism::{ModuleHomomorphism, ZeroHomomorphism},
15    },
16};
17
18pub type FreeModuleHomomorphism<M> = MuFreeModuleHomomorphism<false, M>;
19pub type UnstableFreeModuleHomomorphism<M> = MuFreeModuleHomomorphism<true, M>;
20
21pub struct MuFreeModuleHomomorphism<const U: bool, M: Module>
22where
23    M::Algebra: MuAlgebra<U>,
24{
25    source: Arc<MuFreeModule<U, M::Algebra>>,
26    target: Arc<M>,
27    outputs: OnceBiVec<Vec<FpVector>>, // degree --> input_idx --> output
28    pub images: OnceBiVec<Option<Subspace>>,
29    pub kernels: OnceBiVec<Option<Subspace>>,
30    pub quasi_inverses: OnceBiVec<Option<QuasiInverse>>,
31    min_degree: i32,
32    /// degree shift, such that ouptut_degree = input_degree - degree_shift
33    degree_shift: i32,
34}
35
36impl<const U: bool, M: Module> ModuleHomomorphism for MuFreeModuleHomomorphism<U, M>
37where
38    M::Algebra: MuAlgebra<U>,
39{
40    type Source = MuFreeModule<U, M::Algebra>;
41    type Target = M;
42
43    fn source(&self) -> Arc<Self::Source> {
44        Arc::clone(&self.source)
45    }
46
47    fn target(&self) -> Arc<Self::Target> {
48        Arc::clone(&self.target)
49    }
50
51    fn degree_shift(&self) -> i32 {
52        self.degree_shift
53    }
54
55    fn apply_to_basis_element(
56        &self,
57        result: FpSliceMut,
58        coeff: u32,
59        input_degree: i32,
60        input_index: usize,
61    ) {
62        assert!(input_degree >= self.source.min_degree());
63        assert!(input_index < self.source.dimension(input_degree));
64        let output_degree = input_degree - self.degree_shift;
65        assert_eq!(
66            self.target.dimension(output_degree),
67            result.as_slice().len()
68        );
69        let OperationGeneratorPair {
70            operation_degree,
71            generator_degree,
72            operation_index,
73            generator_index,
74        } = *self.source.index_to_op_gen(input_degree, input_index);
75
76        if generator_degree >= self.min_degree() {
77            let output_on_generator = self.output(generator_degree, generator_index);
78            self.target.act(
79                result,
80                coeff,
81                operation_degree,
82                operation_index,
83                generator_degree - self.degree_shift,
84                output_on_generator.as_slice(),
85            );
86        }
87    }
88
89    fn quasi_inverse(&self, degree: i32) -> Option<&QuasiInverse> {
90        self.quasi_inverses.get(degree).and_then(Option::as_ref)
91    }
92
93    fn kernel(&self, degree: i32) -> Option<&Subspace> {
94        self.kernels.get(degree).and_then(Option::as_ref)
95    }
96
97    fn image(&self, degree: i32) -> Option<&Subspace> {
98        self.images.get(degree).and_then(Option::as_ref)
99    }
100
101    fn compute_auxiliary_data_through_degree(&self, degree: i32) {
102        self.kernels.extend(degree, |i| {
103            let (image, kernel, qi) = self.auxiliary_data(i);
104            self.images.push_checked(Some(image), i);
105            self.quasi_inverses.push_checked(Some(qi), i);
106            Some(kernel)
107        });
108    }
109}
110
111impl<const U: bool, M: Module> MuFreeModuleHomomorphism<U, M>
112where
113    M::Algebra: MuAlgebra<U>,
114{
115    pub fn new(
116        source: Arc<MuFreeModule<U, M::Algebra>>,
117        target: Arc<M>,
118        degree_shift: i32,
119    ) -> Self {
120        let min_degree = std::cmp::max(source.min_degree(), target.min_degree() + degree_shift);
121        let outputs = OnceBiVec::new(min_degree);
122        let kernels = OnceBiVec::new(min_degree);
123        let images = OnceBiVec::new(min_degree);
124        let quasi_inverses = OnceBiVec::new(min_degree);
125        Self {
126            source,
127            target,
128            outputs,
129            images,
130            kernels,
131            quasi_inverses,
132            min_degree,
133            degree_shift,
134        }
135    }
136
137    pub fn degree_shift(&self) -> i32 {
138        self.degree_shift
139    }
140
141    pub fn min_degree(&self) -> i32 {
142        self.min_degree
143    }
144
145    pub fn next_degree(&self) -> i32 {
146        self.outputs.len()
147    }
148
149    pub fn output(&self, generator_degree: i32, generator_index: usize) -> &FpVector {
150        assert!(
151            generator_degree >= self.min_degree(),
152            "generator_degree {} less than min degree {}",
153            generator_degree,
154            self.min_degree()
155        );
156        assert!(
157            generator_index < self.source.number_of_gens_in_degree(generator_degree),
158            "generator_index {} greater than number of generators {}",
159            generator_index,
160            self.source.number_of_gens_in_degree(generator_degree)
161        );
162        &self.outputs[generator_degree][generator_index]
163    }
164
165    pub fn differential_density(&self, degree: i32) -> f32 {
166        let outputs = &self.outputs[degree];
167        if outputs.is_empty() {
168            f32::NAN
169        } else {
170            outputs.iter().map(FpVector::density).sum::<f32>() / outputs.len() as f32
171        }
172    }
173
174    pub fn extend_by_zero(&self, degree: i32) {
175        let p = self.prime();
176        self.outputs.extend(degree, |i| {
177            let num_gens = self.source.number_of_gens_in_degree(i);
178            let dimension = self.target.dimension(i - self.degree_shift);
179            let mut new_outputs: Vec<FpVector> = Vec::with_capacity(num_gens);
180            for _ in 0..num_gens {
181                new_outputs.push(FpVector::new(p, dimension));
182            }
183            new_outputs
184        });
185    }
186
187    pub fn add_generators_from_big_vector(&self, degree: i32, outputs_vectors: FpSlice) {
188        let p = self.prime();
189        let new_generators = self.source.number_of_gens_in_degree(degree);
190        let target_dimension = self.target.dimension(degree - self.degree_shift);
191        let mut new_outputs: Vec<FpVector> = Vec::with_capacity(new_generators);
192        for _ in 0..new_generators {
193            new_outputs.push(FpVector::new(p, target_dimension));
194        }
195        if target_dimension == 0 {
196            self.outputs.push_checked(new_outputs, degree);
197            return;
198        }
199        for (i, new_output) in new_outputs.iter_mut().enumerate() {
200            new_output
201                .as_slice_mut()
202                .assign(outputs_vectors.restrict(target_dimension * i, target_dimension * (i + 1)));
203        }
204        self.outputs.push_checked(new_outputs, degree);
205    }
206
207    /// A MatrixSlice will do but there is no application of this struct, so it doesn't exist yet...
208    pub fn add_generators_from_matrix_rows(&self, degree: i32, mut matrix: MatrixSliceMut) {
209        let p = self.prime();
210        let new_generators = self.source.number_of_gens_in_degree(degree);
211        let target_dimension = self.target.dimension(degree - self.degree_shift);
212
213        let mut new_outputs: Vec<FpVector> = Vec::with_capacity(new_generators);
214        for _ in 0..new_generators {
215            new_outputs.push(FpVector::new(p, target_dimension));
216        }
217        if target_dimension == 0 {
218            self.outputs.push_checked(new_outputs, degree);
219            return;
220        }
221        for (i, new_output) in new_outputs.iter_mut().enumerate() {
222            new_output.as_slice_mut().assign(matrix.row(i));
223        }
224        self.outputs.push_checked(new_outputs, degree);
225    }
226
227    pub fn add_generators_from_rows(&self, degree: i32, rows: Vec<FpVector>) {
228        self.outputs.push_checked(rows, degree);
229    }
230
231    /// Add the image of a bidegree out of order. See
232    /// [`OnceVec::push_ooo`](once::OnceVec::push_ooo) for details on return value.
233    pub fn add_generators_from_rows_ooo(
234        &self,
235        degree: i32,
236        rows: Vec<FpVector>,
237    ) -> std::ops::Range<i32> {
238        self.outputs.push_ooo(rows, degree)
239    }
240
241    /// List of outputs that have been added out of order
242    pub fn ooo_outputs(&self) -> Vec<i32> {
243        self.outputs.ooo_elements()
244    }
245
246    pub fn apply_to_generator(&self, result: &mut FpVector, coeff: u32, degree: i32, idx: usize) {
247        let output_on_gen = self.output(degree, idx);
248        result.add(output_on_gen, coeff);
249    }
250
251    pub fn set_image(&self, degree: i32, image: Option<Subspace>) {
252        self.images.push_checked(image, degree);
253    }
254
255    pub fn set_kernel(&self, degree: i32, kernel: Option<Subspace>) {
256        self.kernels.push_checked(kernel, degree);
257    }
258
259    pub fn set_quasi_inverse(&self, degree: i32, quasi_inverse: Option<QuasiInverse>) {
260        self.quasi_inverses.push_checked(quasi_inverse, degree);
261    }
262}
263
264impl<const U: bool, M: Module> ZeroHomomorphism<MuFreeModule<U, M::Algebra>, M>
265    for MuFreeModuleHomomorphism<U, M>
266where
267    M::Algebra: MuAlgebra<U>,
268{
269    fn zero_homomorphism(
270        source: Arc<MuFreeModule<U, M::Algebra>>,
271        target: Arc<M>,
272        degree_shift: i32,
273    ) -> Self {
274        Self::new(source, target, degree_shift)
275    }
276}
277
278impl<const U: bool, A: MuAlgebra<U>> MuFreeModuleHomomorphism<U, MuFreeModule<U, A>> {
279    /// Given f: M -> N, compute the dual f*: Hom(N, k) -> Hom(M, k) in source (N) degree t.
280    pub fn hom_k(&self, t: i32) -> Vec<Vec<u32>> {
281        let source_dim = self.source.number_of_gens_in_degree(t + self.degree_shift);
282        let target_dim = self.target.number_of_gens_in_degree(t);
283        if target_dim == 0 {
284            return vec![];
285        }
286        let mut result = vec![vec![0; source_dim]; target_dim];
287
288        let offset = self.target.generator_offset(t, t, 0);
289        #[allow(clippy::needless_range_loop)]
290        for i in 0..source_dim {
291            let output = self.output(t + self.degree_shift, i);
292            #[allow(clippy::needless_range_loop)]
293            for j in 0..target_dim {
294                result[j][i] = output.entry(offset + j);
295            }
296        }
297        result
298    }
299}
algebra/module/homomorphism/free_module_homomorphism.rs

algebra/module/homomorphism/
free_module_homomorphism.rs
