algebra/module/homomorphism/
mod.rs

1use std::sync::Arc;
2
3use fp::{
4    matrix::{AugmentedMatrix, Matrix, MatrixSliceMut, QuasiInverse, Subspace},
5    prime::ValidPrime,
6    vector::{FpSlice, FpSliceMut},
7};
8
9use crate::module::Module;
10
11mod free_module_homomorphism;
12mod full_module_homomorphism;
13mod generic_zero_homomorphism;
14mod hom_pullback;
15mod quotient_homomorphism;
16
17pub use free_module_homomorphism::{
18    FreeModuleHomomorphism, MuFreeModuleHomomorphism, UnstableFreeModuleHomomorphism,
19};
20pub use full_module_homomorphism::FullModuleHomomorphism;
21pub use generic_zero_homomorphism::GenericZeroHomomorphism;
22pub use hom_pullback::HomPullback;
23// If `concurrent` is disabled, `MaybeIndexedParallelIterator` implements `Iterator`, and so has an
24// `enumerate` method. However, if it is disabled, it does *not* implement `Iterator`, and the
25// `enumerate` method is provided by `rayon::prelude::IndexedParallelIterator`, which is loaded in
26// the `maybe_rayon` prelude.
27#[allow(unused_imports)]
28use maybe_rayon::prelude::*;
29pub use quotient_homomorphism::{QuotientHomomorphism, QuotientHomomorphismSource};
30
31/// A trait that represents a homomorphism between two modules.
32///
33/// Each `ModuleHomomorphism` may come with auxiliary data, namely the kernel, image and
34/// quasi_inverse at each degree (the quasi-inverse is a map that is a right inverse when restricted
35/// to the image). These are computed via
36/// [`ModuleHomomorphism::compute_auxiliary_data_through_degree`] and retrieved through
37/// [`ModuleHomomorphism::kernel`], [`ModuleHomomorphism::quasi_inverse`] and
38/// [`ModuleHomomorphism::image`].
39///
40/// Note that an instance of a `ModuleHomomorphism` need not have the data available, even after
41/// `compute_auxiliary_data_through_degree` is invoked.
42pub trait ModuleHomomorphism: Send + Sync {
43    type Source: Module;
44    type Target: Module<Algebra = <Self::Source as Module>::Algebra>;
45
46    fn source(&self) -> Arc<Self::Source>;
47    fn target(&self) -> Arc<Self::Target>;
48    fn degree_shift(&self) -> i32;
49
50    /// Calling this function when `input_idx < source().dimension(input_degree)` results in
51    /// undefined behaviour. Implementations are encouraged to panic when this happens (this is
52    /// usually the case because of out-of-bounds errors.
53    fn apply_to_basis_element(
54        &self,
55        result: FpSliceMut,
56        coeff: u32,
57        input_degree: i32,
58        input_idx: usize,
59    );
60
61    #[allow(unused_variables)]
62    fn kernel(&self, degree: i32) -> Option<&Subspace> {
63        None
64    }
65
66    #[allow(unused_variables)]
67    fn quasi_inverse(&self, degree: i32) -> Option<&QuasiInverse> {
68        None
69    }
70
71    #[allow(unused_variables)]
72    fn image(&self, degree: i32) -> Option<&Subspace> {
73        None
74    }
75
76    #[allow(unused_variables)]
77    fn compute_auxiliary_data_through_degree(&self, degree: i32) {}
78
79    fn apply(&self, mut result: FpSliceMut, coeff: u32, input_degree: i32, input: FpSlice) {
80        let p = self.prime();
81        for (i, v) in input.iter_nonzero() {
82            self.apply_to_basis_element(result.copy(), (coeff * v) % p, input_degree, i);
83        }
84    }
85
86    fn prime(&self) -> ValidPrime {
87        self.source().prime()
88    }
89
90    fn min_degree(&self) -> i32 {
91        self.source().min_degree()
92    }
93
94    /// Compute the auxiliary data associated to the homomorphism at input degree `degree`. Returns
95    /// it in the order image, kernel, quasi_inverse
96    fn auxiliary_data(&self, degree: i32) -> (Subspace, Subspace, QuasiInverse) {
97        let p = self.prime();
98        let output_degree = degree - self.degree_shift();
99        self.source().compute_basis(degree);
100        self.target().compute_basis(output_degree);
101        let source_dimension = self.source().dimension(degree);
102        let target_dimension = self.target().dimension(output_degree);
103        let mut matrix =
104            AugmentedMatrix::<2>::new(p, source_dimension, [target_dimension, source_dimension]);
105
106        self.get_matrix(matrix.segment(0, 0), degree);
107        matrix.segment(1, 1).add_identity();
108
109        matrix.row_reduce();
110
111        (
112            matrix.compute_image(),
113            matrix.compute_kernel(),
114            matrix.compute_quasi_inverse(),
115        )
116    }
117
118    /// Write the matrix of the homomorphism at input degree `degree` to `matrix`.
119    ///
120    /// The (sliced) dimensions of `matrix` must be equal to source_dimension x
121    /// target_dimension
122    fn get_matrix(&self, mut matrix: MatrixSliceMut, degree: i32) {
123        assert_eq!(self.source().dimension(degree), matrix.rows());
124        assert_eq!(
125            self.target().dimension(degree - self.degree_shift()),
126            matrix.columns()
127        );
128
129        if matrix.columns() == 0 {
130            return;
131        }
132
133        matrix
134            .maybe_par_iter_mut()
135            .enumerate()
136            .for_each(|(i, row)| self.apply_to_basis_element(row, 1, degree, i));
137    }
138
139    /// Get the values of the homomorphism on the specified inputs to `matrix`.
140    fn get_partial_matrix(&self, degree: i32, inputs: &[usize]) -> Matrix {
141        let mut matrix = Matrix::new(self.prime(), inputs.len(), self.target().dimension(degree));
142
143        if matrix.columns() == 0 {
144            return matrix;
145        }
146
147        matrix
148            .maybe_par_iter_mut()
149            .enumerate()
150            .for_each(|(i, row)| self.apply_to_basis_element(row, 1, degree, inputs[i]));
151
152        matrix
153    }
154
155    /// Attempt to apply quasi inverse to the input. Returns whether the operation was
156    /// successful. This is required to either always succeed or always fail for each degree.
157    #[must_use]
158    fn apply_quasi_inverse(&self, result: FpSliceMut, degree: i32, input: FpSlice) -> bool {
159        if let Some(qi) = self.quasi_inverse(degree) {
160            qi.apply(result, 1, input);
161            true
162        } else {
163            false
164        }
165    }
166}
167
168pub trait ZeroHomomorphism<S: Module, T: Module<Algebra = S::Algebra>>:
169    ModuleHomomorphism<Source = S, Target = T>
170{
171    fn zero_homomorphism(s: Arc<S>, t: Arc<T>, degree_shift: i32) -> Self;
172}
173
174pub trait IdentityHomomorphism<S: Module>: ModuleHomomorphism<Source = S, Target = S> {
175    fn identity_homomorphism(s: Arc<S>) -> Self;
176}
algebra/module/homomorphism/mod.rs

algebra/module/homomorphism/
mod.rs
