algebra/module/
finitely_presented_module.rs

1use std::sync::Arc;
2
3use fp::vector::{FpSliceMut, FpVector};
4use itertools::Itertools;
5use once::OnceBiVec;
6use serde_json::Value;
7
8use crate::{
9    algebra::Algebra,
10    module::{
11        FreeModule, Module, ZeroModule,
12        homomorphism::{FreeModuleHomomorphism, ModuleHomomorphism},
13    },
14};
15
16struct FPMIndexTable {
17    gen_idx_to_fp_idx: Vec<isize>,
18    fp_idx_to_gen_idx: Vec<usize>,
19}
20
21pub struct FinitelyPresentedModule<A: Algebra> {
22    name: String,
23    min_degree: i32,
24    generators: Arc<FreeModule<A>>,
25    relations: Arc<FreeModule<A>>,
26    map: Arc<FreeModuleHomomorphism<FreeModule<A>>>,
27    index_table: OnceBiVec<FPMIndexTable>,
28}
29
30impl<A: Algebra> std::fmt::Display for FinitelyPresentedModule<A> {
31    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
32        write!(f, "{}", self.name)
33    }
34}
35
36impl<A: Algebra> PartialEq for FinitelyPresentedModule<A> {
37    fn eq(&self, _other: &Self) -> bool {
38        todo!()
39    }
40}
41
42impl<A: Algebra> Eq for FinitelyPresentedModule<A> {}
43
44impl<A: Algebra> ZeroModule for FinitelyPresentedModule<A> {
45    fn zero_module(algebra: Arc<A>, min_degree: i32) -> Self {
46        Self::new(algebra, "zero".to_string(), min_degree)
47    }
48}
49
50impl<A: Algebra> FinitelyPresentedModule<A> {
51    pub fn new(algebra: Arc<A>, name: String, min_degree: i32) -> Self {
52        let generators = Arc::new(FreeModule::new(
53            Arc::clone(&algebra),
54            format!("{name}-gens"),
55            min_degree,
56        ));
57        let relations = Arc::new(FreeModule::new(
58            Arc::clone(&algebra),
59            format!("{name}-gens"),
60            min_degree,
61        ));
62        Self {
63            name,
64            min_degree,
65            generators: Arc::clone(&generators),
66            relations: Arc::clone(&relations),
67            map: Arc::new(FreeModuleHomomorphism::new(
68                Arc::clone(&relations),
69                Arc::clone(&generators),
70                0,
71            )),
72            index_table: OnceBiVec::new(min_degree),
73        }
74    }
75
76    pub fn generators(&self) -> Arc<FreeModule<A>> {
77        Arc::clone(&self.generators)
78    }
79
80    pub fn add_generators(&mut self, degree: i32, gen_names: Vec<String>) {
81        let num_gens = gen_names.len();
82        self.generators
83            .add_generators(degree, num_gens, Some(gen_names));
84    }
85
86    pub fn add_relations(&mut self, degree: i32, relations: Vec<FpVector>) {
87        self.relations.add_generators(degree, relations.len(), None);
88        self.map.add_generators_from_rows(degree, relations);
89    }
90
91    pub fn gen_idx_to_fp_idx(&self, degree: i32, idx: usize) -> isize {
92        assert!(degree >= self.min_degree);
93        self.index_table[degree].gen_idx_to_fp_idx[idx]
94    }
95
96    pub fn fp_idx_to_gen_idx(&self, degree: i32, idx: usize) -> usize {
97        assert!(degree >= self.min_degree);
98        self.index_table[degree].fp_idx_to_gen_idx[idx]
99    }
100}
101
102impl<A: Algebra> FinitelyPresentedModule<A> {
103    pub fn from_json(algebra: Arc<A>, json: &Value) -> anyhow::Result<Self> {
104        use anyhow::anyhow;
105        use nom::{Parser, combinator::opt};
106
107        use crate::steenrod_parser::digits;
108
109        let p = algebra.prime();
110        let name = json["name"].as_str().unwrap_or("").to_string();
111        let (_, gen_names, gen_to_deg_idx) = crate::module_gens_from_json(&json["gens"]);
112
113        let min_degree = gen_names.min_degree();
114        let mut result = Self::new(Arc::clone(&algebra), name, min_degree);
115
116        for (i, gen_names) in gen_names.into_iter_enum() {
117            result.add_generators(i, gen_names);
118        }
119
120        // A list of relations, specified by the degree then the element to be killed
121        let mut relations: Vec<(i32, FpVector)> = json[algebra.prefix().to_string() + "_relations"]
122            .as_array()
123            .unwrap()
124            .iter()
125            .map(|reln| {
126                let mut deg = 0;
127                let mut v = FpVector::new(p, 0);
128
129                for term in reln.as_str().unwrap().split(" + ") {
130                    let (term, coef) = opt(digits).parse(term).unwrap();
131                    let coef: u32 = coef.unwrap_or(1);
132
133                    let (op, g) = term.rsplit_once(' ').unwrap_or(("1", term));
134                    let (op_deg, op_idx) = algebra
135                        .basis_element_from_string(op)
136                        .ok_or_else(|| anyhow!("Invalid term in relation: {term}"))?;
137                    let (gen_deg, gen_idx) = gen_to_deg_idx(g)?;
138
139                    if v.is_empty() {
140                        deg = op_deg + gen_deg;
141                        algebra.compute_basis(deg - min_degree);
142                        result.generators.compute_basis(deg);
143                        v.set_scratch_vector_size(result.generators.dimension(deg));
144                    } else if op_deg + gen_deg != deg {
145                        return Err(anyhow!(
146                            "Relation has inconsistent degree. Expected {deg} but {term} has \
147                             degree {}",
148                            op_deg + gen_deg
149                        ));
150                    }
151
152                    let idx = result
153                        .generators
154                        .operation_generator_to_index(op_deg, op_idx, gen_deg, gen_idx);
155
156                    v.add_basis_element(idx, coef);
157                }
158                Ok((deg, v))
159            })
160            .collect::<anyhow::Result<Vec<_>>>()?;
161
162        relations.sort_unstable_by_key(|x| x.0);
163        for (degree, rels) in &relations.into_iter().chunk_by(|x| x.0) {
164            for deg in result.relations.max_computed_degree() + 1..degree {
165                result.add_relations(deg, vec![]);
166            }
167            result.add_relations(degree, rels.map(|x| x.1).collect());
168        }
169        Ok(result)
170    }
171}
172
173impl<A: Algebra> Module for FinitelyPresentedModule<A> {
174    type Algebra = A;
175
176    fn algebra(&self) -> Arc<A> {
177        self.generators.algebra()
178    }
179
180    fn min_degree(&self) -> i32 {
181        self.generators.min_degree()
182    }
183
184    fn max_computed_degree(&self) -> i32 {
185        self.generators.max_computed_degree()
186    }
187
188    fn compute_basis(&self, degree: i32) {
189        self.generators.extend_by_zero(degree);
190        self.relations.extend_by_zero(degree);
191        self.map.compute_auxiliary_data_through_degree(degree);
192
193        self.index_table.extend(degree, |i| {
194            let qi = self.map.quasi_inverse(i).unwrap();
195            let mut gen_idx_to_fp_idx = Vec::new();
196            let mut fp_idx_to_gen_idx = Vec::new();
197            for (i, &pivot) in qi.pivots().unwrap().iter().enumerate() {
198                if pivot < 0 {
199                    gen_idx_to_fp_idx.push(fp_idx_to_gen_idx.len() as isize);
200                    fp_idx_to_gen_idx.push(i);
201                } else {
202                    gen_idx_to_fp_idx.push(-1);
203                }
204            }
205            FPMIndexTable {
206                gen_idx_to_fp_idx,
207                fp_idx_to_gen_idx,
208            }
209        });
210    }
211
212    fn dimension(&self, degree: i32) -> usize {
213        assert!(degree >= self.min_degree);
214        self.index_table[degree].fp_idx_to_gen_idx.len()
215    }
216
217    fn act_on_basis(
218        &self,
219        mut result: FpSliceMut,
220        coeff: u32,
221        op_degree: i32,
222        op_index: usize,
223        mod_degree: i32,
224        mod_index: usize,
225    ) {
226        let p = self.prime();
227        let gen_idx = self.fp_idx_to_gen_idx(mod_degree, mod_index);
228        let out_deg = mod_degree + op_degree;
229        let gen_dim = self.generators.dimension(out_deg);
230        let mut temp_vec = FpVector::new(p, gen_dim);
231        self.generators.act_on_basis(
232            temp_vec.as_slice_mut(),
233            coeff,
234            op_degree,
235            op_index,
236            mod_degree,
237            gen_idx,
238        );
239        let image = self.map.image(out_deg).unwrap();
240        image.reduce(temp_vec.as_slice_mut());
241        for i in 0..result.as_slice().len() {
242            let value = temp_vec.entry(self.fp_idx_to_gen_idx(out_deg, i));
243            result.add_basis_element(i, value);
244        }
245    }
246
247    fn basis_element_to_string(&self, degree: i32, idx: usize) -> String {
248        let gen_idx = self.fp_idx_to_gen_idx(degree, idx);
249        self.generators.basis_element_to_string(degree, gen_idx)
250    }
251
252    fn max_generator_degree(&self) -> Option<i32> {
253        self.generators.max_generator_degree()
254    }
255}
algebra/module/finitely_presented_module.rs

algebra/module/
finitely_presented_module.rs
