algebra/module/
quotient_module.rs

1use std::sync::Arc;
2
3use bivec::BiVec;
4use fp::{
5    matrix::Subspace,
6    vector::{FpSlice, FpSliceMut, FpVector},
7};
8
9use crate::module::{Module, ZeroModule};
10
11/// A quotient of a module truncated below a fix degree.
12pub struct QuotientModule<M: Module> {
13    /// The underlying module
14    pub module: Arc<M>,
15    /// The subspaces that we quotient out by
16    pub subspaces: BiVec<Subspace>,
17    /// For each degree `d`, `basis_list[d]` is a list of basis elements of `self.module` that
18    /// generates the quotient.
19    pub basis_list: BiVec<Vec<usize>>,
20    /// Everything above this degree is quotiented out.
21    pub truncation: i32,
22}
23
24impl<M: Module> std::fmt::Display for QuotientModule<M> {
25    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
26        write!(f, "Quotient of {}", self.module)
27    }
28}
29
30impl<M: Module> QuotientModule<M> {
31    pub fn new(module: Arc<M>, truncation: i32) -> Self {
32        module.compute_basis(truncation);
33
34        let p = module.prime();
35        let min_degree = module.min_degree();
36
37        let mut subspaces = BiVec::with_capacity(min_degree, truncation + 1);
38        let mut basis_list = BiVec::with_capacity(min_degree, truncation + 1);
39
40        for t in min_degree..=truncation {
41            let dim = module.dimension(t);
42            subspaces.push(Subspace::new(p, dim));
43            basis_list.push((0..dim).collect());
44        }
45        Self {
46            module,
47            subspaces,
48            basis_list,
49            truncation,
50        }
51    }
52
53    pub fn quotient(&mut self, degree: i32, element: FpSlice) {
54        if degree <= self.truncation {
55            self.subspaces[degree].add_vector(element);
56            self.flush(degree);
57        }
58    }
59
60    pub fn quotient_basis_elements(
61        &mut self,
62        degree: i32,
63        elements: impl std::iter::Iterator<Item = usize>,
64    ) {
65        self.subspaces[degree].add_basis_elements(elements);
66        self.flush(degree);
67    }
68
69    /// # Arguments
70    ///  - `degree`: The degree to quotient in
71    ///  - `vecs`: See [`Subspace::add_vectors`]
72    pub fn quotient_vectors(
73        &mut self,
74        degree: i32,
75        vecs: impl for<'a> FnMut(FpSliceMut<'a>) -> Option<()>,
76    ) {
77        if degree > self.truncation {
78            return;
79        }
80        self.subspaces[degree].add_vectors(vecs);
81        self.flush(degree);
82    }
83
84    fn flush(&mut self, degree: i32) {
85        self.basis_list[degree].clear();
86        self.basis_list[degree].extend(
87            self.subspaces[degree]
88                .pivots()
89                .iter()
90                .enumerate()
91                .filter_map(|(idx, &row)| if row < 0 { Some(idx) } else { None }),
92        );
93    }
94
95    pub fn quotient_all(&mut self, degree: i32) {
96        self.subspaces[degree].set_to_entire();
97        self.basis_list[degree] = Vec::new();
98    }
99
100    pub fn act_on_original_basis(
101        &self,
102        mut result: FpSliceMut,
103        coeff: u32,
104        op_degree: i32,
105        op_index: usize,
106        mod_degree: i32,
107        mod_index: usize,
108    ) {
109        if op_degree + mod_degree > self.truncation {
110            return;
111        }
112        self.module.act_on_basis(
113            result.copy(),
114            coeff,
115            op_degree,
116            op_index,
117            mod_degree,
118            mod_index,
119        );
120        self.reduce(op_degree + mod_degree, result)
121    }
122
123    pub fn reduce(&self, degree: i32, mut vec: FpSliceMut) {
124        if degree > self.truncation {
125            vec.set_to_zero()
126        } else {
127            self.subspaces[degree].reduce(vec);
128        }
129    }
130
131    pub fn old_basis_to_new(&self, degree: i32, mut new: FpSliceMut, old: FpSlice) {
132        for (i, idx) in self.basis_list[degree].iter().enumerate() {
133            new.add_basis_element(i, old.entry(*idx));
134        }
135    }
136}
137
138impl<M: Module> Module for QuotientModule<M> {
139    type Algebra = M::Algebra;
140
141    fn algebra(&self) -> Arc<Self::Algebra> {
142        self.module.algebra()
143    }
144
145    fn min_degree(&self) -> i32 {
146        self.module.min_degree()
147    }
148
149    fn max_computed_degree(&self) -> i32 {
150        self.module.max_computed_degree()
151    }
152
153    fn dimension(&self, degree: i32) -> usize {
154        if degree > self.truncation {
155            0
156        } else {
157            self.module.dimension(degree) - self.subspaces[degree].dimension()
158        }
159    }
160
161    fn act_on_basis(
162        &self,
163        result: FpSliceMut,
164        coeff: u32,
165        op_degree: i32,
166        op_index: usize,
167        mod_degree: i32,
168        mod_index: usize,
169    ) {
170        let target_deg = op_degree + mod_degree;
171        if target_deg > self.truncation {
172            return;
173        }
174
175        let mut result_ = FpVector::new(self.prime(), self.module.dimension(target_deg));
176        self.act_on_original_basis(
177            result_.as_slice_mut(),
178            coeff,
179            op_degree,
180            op_index,
181            mod_degree,
182            self.basis_list[mod_degree][mod_index],
183        );
184        self.reduce(target_deg, result_.as_slice_mut());
185        self.old_basis_to_new(target_deg, result, result_.as_slice());
186    }
187
188    fn basis_element_to_string(&self, degree: i32, idx: usize) -> String {
189        self.module
190            .basis_element_to_string(degree, self.basis_list[degree][idx])
191    }
192
193    fn max_degree(&self) -> Option<i32> {
194        Some(match self.module.max_degree() {
195            Some(max_degree) => std::cmp::min(max_degree, self.truncation),
196            None => self.truncation,
197        })
198    }
199}
200
201impl<M: ZeroModule> ZeroModule for QuotientModule<M> {
202    fn zero_module(algebra: Arc<M::Algebra>, min_degree: i32) -> Self {
203        Self::new(Arc::new(M::zero_module(algebra, min_degree)), min_degree)
204    }
205}
algebra/module/quotient_module.rs

algebra/module/
quotient_module.rs
