algebra/module/homomorphism/
full_module_homomorphism.rs

1use std::sync::Arc;
2
3use bivec::BiVec;
4use fp::{
5    matrix::{Matrix, QuasiInverse, Subspace},
6    vector::FpSliceMut,
7};
8use once::OnceBiVec;
9
10use crate::{
11    algebra::Algebra,
12    module::{
13        Module,
14        homomorphism::{IdentityHomomorphism, ModuleHomomorphism, ZeroHomomorphism},
15    },
16};
17
18/// A ModuleHomomorphism that simply records the matrix of the homomorphism in every degree.
19/// This is currently rather bare bones.
20pub struct FullModuleHomomorphism<S: Module, T: Module<Algebra = S::Algebra> = S> {
21    source: Arc<S>,
22    target: Arc<T>,
23    degree_shift: i32,
24    /// The matrices of the module homomorphism. Unspecified matrices are assumed to be zero
25    matrices: OnceBiVec<Matrix>,
26    quasi_inverses: OnceBiVec<QuasiInverse>,
27    kernels: OnceBiVec<Subspace>,
28    images: OnceBiVec<Subspace>,
29}
30
31impl<S: Module, T: Module<Algebra = S::Algebra>> Clone for FullModuleHomomorphism<S, T> {
32    fn clone(&self) -> Self {
33        Self {
34            source: Arc::clone(&self.source),
35            target: Arc::clone(&self.target),
36            degree_shift: self.degree_shift,
37            matrices: self.matrices.clone(),
38            quasi_inverses: self.quasi_inverses.clone(),
39            kernels: self.kernels.clone(),
40            images: self.images.clone(),
41        }
42    }
43}
44
45impl<S: Module, T: Module<Algebra = S::Algebra>> ModuleHomomorphism
46    for FullModuleHomomorphism<S, T>
47{
48    type Source = S;
49    type Target = T;
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.degree_shift
61    }
62
63    fn apply_to_basis_element(
64        &self,
65        mut result: FpSliceMut,
66        coeff: u32,
67        input_degree: i32,
68        input_idx: usize,
69    ) {
70        let output_degree = input_degree - self.degree_shift;
71        if let Some(matrix) = self.matrices.get(output_degree) {
72            result.add(matrix.row(input_idx), coeff);
73        }
74    }
75
76    fn image(&self, degree: i32) -> Option<&Subspace> {
77        self.images.get(degree)
78    }
79
80    fn quasi_inverse(&self, degree: i32) -> Option<&QuasiInverse> {
81        self.quasi_inverses.get(degree)
82    }
83
84    fn kernel(&self, degree: i32) -> Option<&Subspace> {
85        self.kernels.get(degree)
86    }
87
88    fn compute_auxiliary_data_through_degree(&self, degree: i32) {
89        let degree = std::cmp::min(degree, self.matrices.len() - 1);
90        self.kernels.extend(degree, |i| {
91            let (image, kernel, qi) = self.auxiliary_data(i);
92            self.images.push_checked(image, i);
93            self.quasi_inverses.push_checked(qi, i);
94            kernel
95        });
96    }
97}
98
99impl<A, S, T> FullModuleHomomorphism<S, T>
100where
101    A: Algebra,
102    S: Module<Algebra = A>,
103    T: Module<Algebra = A>,
104{
105    pub fn new(source: Arc<S>, target: Arc<T>, degree_shift: i32) -> Self {
106        let min_degree = source.min_degree();
107        Self::from_matrices(source, target, degree_shift, BiVec::new(min_degree))
108    }
109
110    pub fn from_matrices(
111        source: Arc<S>,
112        target: Arc<T>,
113        degree_shift: i32,
114        matrices: BiVec<Matrix>,
115    ) -> Self {
116        let min_degree = target.min_degree();
117        Self {
118            source,
119            target,
120            degree_shift,
121            matrices: OnceBiVec::from_bivec(matrices),
122            quasi_inverses: OnceBiVec::new(min_degree),
123            kernels: OnceBiVec::new(min_degree),
124            images: OnceBiVec::new(min_degree),
125        }
126    }
127
128    pub fn from<F: ModuleHomomorphism<Source = S, Target = T>>(f: &F) -> Self {
129        let source = f.source();
130        let target = f.target();
131        let degree_shift = f.degree_shift();
132        let p = f.prime();
133
134        let min_degree = f.target().min_degree();
135        let max_degree = f
136            .source()
137            .max_degree()
138            .expect("FullModuleHomomorphism::from requires source to be bonuded")
139            - degree_shift;
140
141        source.compute_basis(max_degree);
142        target.compute_basis(max_degree);
143
144        let matrices = OnceBiVec::new(min_degree);
145
146        for target_deg in min_degree..=max_degree {
147            let source_deg = target_deg + degree_shift;
148            // Here we use `Module::dimension(&*m, i)` instead of `m.dimension(i)` because there are
149            // multiple `dimension` methods in scope and rust-analyzer gets confused if we're not
150            // explicit enough.
151            let source_dim = Module::dimension(&*source, source_deg);
152            let target_dim = Module::dimension(&*target, target_deg);
153
154            let mut matrix = Matrix::new(p, source_dim, target_dim);
155            f.get_matrix(matrix.as_slice_mut(), source_deg);
156            matrices.push_checked(matrix, target_deg);
157        }
158
159        Self {
160            source,
161            target,
162            degree_shift,
163            matrices,
164            quasi_inverses: OnceBiVec::new(min_degree),
165            kernels: OnceBiVec::new(min_degree),
166            images: OnceBiVec::new(min_degree),
167        }
168    }
169
170    /// This function replaces the source of the ModuleHomomorphism and does nothing else.
171    /// This is useful for changing the type of the source (but not the mathematical module
172    /// itself).
173    pub fn replace_source<S_: Module<Algebra = A>>(
174        self,
175        source: Arc<S_>,
176    ) -> FullModuleHomomorphism<S_, T> {
177        FullModuleHomomorphism {
178            source,
179            target: self.target,
180            degree_shift: self.degree_shift,
181            matrices: self.matrices,
182            quasi_inverses: self.quasi_inverses,
183            kernels: self.kernels,
184            images: self.images,
185        }
186    }
187
188    /// See `replace_source`
189    pub fn replace_target<T_: Module<Algebra = A>>(
190        self,
191        target: Arc<T_>,
192    ) -> FullModuleHomomorphism<S, T_> {
193        FullModuleHomomorphism {
194            source: self.source,
195            target,
196            degree_shift: self.degree_shift,
197            matrices: self.matrices,
198            quasi_inverses: self.quasi_inverses,
199            kernels: self.kernels,
200            images: self.images,
201        }
202    }
203}
204
205impl<S: Module, T: Module<Algebra = S::Algebra>> ZeroHomomorphism<S, T>
206    for FullModuleHomomorphism<S, T>
207{
208    fn zero_homomorphism(source: Arc<S>, target: Arc<T>, degree_shift: i32) -> Self {
209        Self::new(source, target, degree_shift)
210    }
211}
212
213impl<S: Module> IdentityHomomorphism<S> for FullModuleHomomorphism<S, S> {
214    fn identity_homomorphism(source: Arc<S>) -> Self {
215        let p = source.prime();
216        let min_degree = source.min_degree();
217        let max_degree = source
218            .max_degree()
219            .expect("FullModuleHomomorphism::identity_homomorphism requires a bounded module");
220
221        let mut matrices = BiVec::with_capacity(min_degree, max_degree + 1);
222
223        for i in min_degree..=max_degree {
224            let dim = source.dimension(i);
225            let mut matrix = Matrix::new(p, dim, dim);
226            for k in 0..dim {
227                matrix.row_mut(k).set_entry(k, 1);
228            }
229            matrices.push(matrix);
230        }
231
232        Self::from_matrices(Arc::clone(&source), source, 0, matrices)
233    }
234}
algebra/module/homomorphism/full_module_homomorphism.rs

algebra/module/homomorphism/
full_module_homomorphism.rs
