fp/matrix/
quasi_inverse.rs

1use std::io;
2
3use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
4use itertools::Itertools;
5use serde::{Deserialize, Serialize};
6
7use super::Matrix;
8use crate::{
9    prime::ValidPrime,
10    vector::{FpSlice, FpSliceMut, FpVector},
11};
12
13/// Given a matrix M, a quasi-inverse Q is a map from the co-domain to the domain such that xQM = x
14/// for all x in the image (recall our matrices act on the right).
15///
16/// # Fields
17///  * `image` - The image of the original matrix. If the image is omitted, it is assumed to be
18///    everything (with the standard basis).
19///  * `preimage` - The actual quasi-inverse, where the basis of the image is that given by
20///    `image`.
21#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
22pub struct QuasiInverse {
23    image: Option<Vec<isize>>,
24    preimage: Matrix,
25}
26
27impl QuasiInverse {
28    pub fn new(image: Option<Vec<isize>>, preimage: Matrix) -> Self {
29        Self { image, preimage }
30    }
31
32    pub fn image_dimension(&self) -> usize {
33        self.preimage.rows()
34    }
35
36    pub fn source_dimension(&self) -> usize {
37        self.preimage.columns()
38    }
39
40    pub fn target_dimension(&self) -> usize {
41        match self.image.as_ref() {
42            Some(v) => v.len(),
43            None => self.image_dimension(),
44        }
45    }
46
47    pub fn to_bytes(&self, buffer: &mut impl io::Write) -> io::Result<()> {
48        buffer.write_u64::<LittleEndian>(self.source_dimension() as u64)?;
49        buffer.write_u64::<LittleEndian>(self.target_dimension() as u64)?;
50        buffer.write_u64::<LittleEndian>(self.image_dimension() as u64)?;
51
52        match self.image.as_ref() {
53            None => {
54                for i in 0..self.preimage.rows() {
55                    buffer.write_i64::<LittleEndian>(i as i64)?;
56                }
57            }
58            Some(v) => {
59                Matrix::write_pivot(v, buffer)?;
60            }
61        }
62        self.preimage.to_bytes(buffer)
63    }
64
65    pub fn from_bytes(p: ValidPrime, data: &mut impl io::Read) -> io::Result<Self> {
66        let source_dim = data.read_u64::<LittleEndian>()? as usize;
67        let target_dim = data.read_u64::<LittleEndian>()? as usize;
68        let image_dim = data.read_u64::<LittleEndian>()? as usize;
69
70        let image = Matrix::read_pivot(target_dim, data)?;
71        let preimage = Matrix::from_bytes(p, image_dim, source_dim, data)?;
72        Ok(Self {
73            image: Some(image),
74            preimage,
75        })
76    }
77
78    /// Given a data file containing a quasi-inverse, apply it to all the vectors in `input`
79    /// and write the results to the corresponding vectors in `results`. This reads in the
80    /// quasi-inverse row by row to minimize memory usage.
81    pub fn stream_quasi_inverse<T, S>(
82        p: ValidPrime,
83        data: &mut impl io::Read,
84        results: &mut [T],
85        inputs: &[S],
86    ) -> io::Result<()>
87    where
88        for<'a> &'a mut T: Into<FpSliceMut<'a>>,
89        for<'a> &'a S: Into<FpSlice<'a>>,
90    {
91        let source_dim = data.read_u64::<LittleEndian>()? as usize;
92        let target_dim = data.read_u64::<LittleEndian>()? as usize;
93        let _image_dim = data.read_u64::<LittleEndian>()? as usize;
94
95        let image = Matrix::read_pivot(target_dim, data)?;
96        let mut v = FpVector::new(p, source_dim);
97
98        assert_eq!(results.len(), inputs.len());
99        for result in &mut *results {
100            assert_eq!(result.into().as_slice().len(), source_dim);
101        }
102
103        for (i, r) in image.into_iter().enumerate() {
104            if r < 0 {
105                continue;
106            }
107
108            v.update_from_bytes(data)?;
109            for (input, result) in inputs.iter().zip_eq(&mut *results) {
110                result.into().add(v.as_slice(), input.into().entry(i));
111            }
112        }
113        Ok(())
114    }
115
116    pub fn preimage(&self) -> &Matrix {
117        &self.preimage
118    }
119
120    pub fn pivots(&self) -> Option<&[isize]> {
121        self.image.as_deref()
122    }
123
124    pub fn prime(&self) -> ValidPrime {
125        self.preimage.prime()
126    }
127
128    /// Apply the quasi-inverse to an input vector and add a constant multiple of the result
129    /// to an output vector
130    ///
131    /// # Arguments
132    ///  * `target` - The output vector
133    ///  * `coeff` - The constant multiple above
134    ///  * `input` - The input vector, expressed in the basis of the ambient space
135    pub fn apply(&self, mut target: FpSliceMut, coeff: u32, input: FpSlice) {
136        let p = self.prime();
137        let mut row = 0;
138        for (i, c) in input.iter().enumerate() {
139            if let Some(pivots) = self.pivots()
140                && (i >= pivots.len() || pivots[i] < 0)
141            {
142                continue;
143            }
144            if c != 0 {
145                target.add(self.preimage.row(row), (coeff * c) % p);
146            }
147            row += 1;
148        }
149    }
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155
156    #[test]
157    fn test_stream_qi() {
158        let p = ValidPrime::new(2);
159        let qi = QuasiInverse {
160            image: Some(vec![0, -1, 1, -1, 2, 3]),
161            preimage: Matrix::from_vec(
162                p,
163                &[
164                    vec![1, 0, 1, 1],
165                    vec![1, 1, 0, 0],
166                    vec![0, 1, 0, 1],
167                    vec![1, 1, 1, 0],
168                ],
169            ),
170        };
171        let v0 = FpVector::from_slice(p, &[1, 1, 0, 0, 1, 0]);
172        let v1 = FpVector::from_slice(p, &[0, 0, 1, 0, 1, 1]);
173
174        let mut out0 = FpVector::new(p, 4);
175        let mut out1 = FpVector::new(p, 4);
176
177        let mut cursor = io::Cursor::new(Vec::<u8>::new());
178        qi.to_bytes(&mut cursor).unwrap();
179        cursor.set_position(0);
180
181        QuasiInverse::stream_quasi_inverse(
182            p,
183            &mut cursor,
184            &mut [out0.as_slice_mut(), out1.as_slice_mut()],
185            &[v0.as_slice(), v1.as_slice()],
186        )
187        .unwrap();
188
189        let mut bench0 = FpVector::new(p, 4);
190        let mut bench1 = FpVector::new(p, 4);
191
192        qi.apply(bench0.as_slice_mut(), 1, v0.as_slice());
193        qi.apply(bench1.as_slice_mut(), 1, v1.as_slice());
194
195        assert_eq!(out0, bench0, "{out0} != {bench0}");
196        assert_eq!(out1, bench1, "{out1} != {bench1}");
197
198        assert_eq!(cursor.position() as usize, cursor.get_ref().len());
199    }
200}
fp/matrix/quasi_inverse.rs

fp/matrix/
quasi_inverse.rs
