algebra/module/
block_structure.rs

1use std::ops::Range;
2
3use bivec::BiVec;
4use fp::vector::{FpSlice, FpSliceMut};
5
6#[derive(Debug)]
7pub struct GeneratorBasisEltPair {
8    pub generator_degree: i32,
9    pub generator_index: usize,
10    pub basis_index: usize,
11}
12
13/// A structure that makes it efficient to convert between an index into a sum of vector spaces and
14/// an index into an individual one.
15///
16/// For instance, a FreeModule has some collection of generators in various degrees and a general
17/// element is a homogenous sum \sum Op^i x_i. The basis for the FreeModule is divided into a block
18/// for each generator x_i. The entries in the block correspond to a basis for the algebra. In order
19/// to multiply by a steenrod operation, we have to pull out each block and multiply each block
20/// separately by the steenrod operation.
21#[derive(Debug)]
22pub struct BlockStructure {
23    basis_element_to_block_idx: Vec<GeneratorBasisEltPair>,
24    blocks: BiVec<Vec<Range<usize>>>, // generator_degree --> generator_index --> (index, size)
25}
26
27impl BlockStructure {
28    pub fn new(block_sizes: &BiVec<Vec<usize>>) -> Self {
29        let mut total_dimension = 0;
30        let mut blocks = BiVec::with_capacity(block_sizes.min_degree(), block_sizes.len());
31        let mut basis_element_to_block_idx = Vec::new();
32        for (degree, block_sizes) in block_sizes.iter_enum() {
33            let mut block_starts_entry = Vec::with_capacity(block_sizes.len());
34            for (i, size) in block_sizes.iter().enumerate() {
35                block_starts_entry.push(total_dimension..total_dimension + size);
36                for j in 0..*size {
37                    basis_element_to_block_idx.push(GeneratorBasisEltPair {
38                        generator_degree: degree,
39                        generator_index: i,
40                        basis_index: j,
41                    });
42                }
43                total_dimension += size;
44            }
45            blocks.push(block_starts_entry);
46        }
47        Self {
48            basis_element_to_block_idx,
49            blocks,
50        }
51    }
52
53    /// Find the block corresponding to a given generator.
54    pub fn generator_to_block(&self, gen_deg: i32, gen_idx: usize) -> Range<usize> {
55        self.blocks[gen_deg][gen_idx].clone()
56    }
57
58    /// Convert (generator, basis element) to basis element of the sum.
59    pub fn generator_basis_elt_to_index(
60        &self,
61        gen_deg: i32,
62        gen_idx: usize,
63        basis_elt: usize,
64    ) -> usize {
65        self.blocks[gen_deg][gen_idx].start + basis_elt
66    }
67
68    /// Find the (generator, basis element) pair corresponding to a given basis element of the block structure.
69    /// For the FreeModule application, index => (free module generator, Steenrod algebra basis element)
70    pub fn index_to_generator_basis_elt(&self, idx: usize) -> &GeneratorBasisEltPair {
71        &self.basis_element_to_block_idx[idx]
72    }
73
74    /// Add source vector "source" to the block indicated by (gen_deg, gen_idx).
75    pub fn add_block(
76        &self,
77        mut target: FpSliceMut,
78        coeff: u32,
79        gen_deg: i32,
80        gen_idx: usize,
81        source: FpSlice,
82    ) {
83        let range = &self.blocks[gen_deg][gen_idx];
84        assert!(source.len() == range.len());
85        target.slice_mut(range.start, range.end).add(source, coeff);
86    }
87
88    pub fn total_dimension(&self) -> usize {
89        self.basis_element_to_block_idx.len()
90    }
91}
algebra/module/block_structure.rs

algebra/module/
block_structure.rs
