qfall_math/integer/mat_z/
forms.rs

1// Copyright 2025 Jan Niklas Siemer
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! This file contains implementations of special forms and transforms of
10//! matrices, e.g. (Hermite and Smith) normal forms, echelon form, ...
11
12use super::MatZ;
13use crate::traits::MatrixDimensions;
14use flint3_sys::{fmpz_mat_hnf_transform, fmpz_mat_is_in_hnf, fmpz_mat_is_in_snf, fmpz_mat_snf};
15
16impl MatZ {
17    /// Computes the Hermite normal form of `self` along with
18    /// the transformation matrix `U` s.t. `U * A = H`.
19    ///
20    /// # Examples
21    /// ```
22    /// use qfall_math::integer::MatZ;
23    /// use std::str::FromStr;
24    /// let matrix = MatZ::from_str("[[1, 2, 12],[2, 4, 5]]").unwrap();
25    /// let h_cmp = MatZ::from_str("[[1, 2, 12],[0, 0, 19]]").unwrap();
26    /// let u_cmp = MatZ::from_str("[[1, 0],[2, -1]]").unwrap();
27    ///
28    /// let (h, u) = matrix.hermite_nf();
29    ///
30    /// assert_eq!(h_cmp, h);
31    /// assert_eq!(u_cmp, u);
32    /// ```
33    pub fn hermite_nf(&self) -> (MatZ, MatZ) {
34        let nr_rows = self.get_num_rows();
35        let nr_cols = self.get_num_columns();
36
37        let mut hnf = MatZ::new(nr_rows, nr_cols);
38        let mut transform = MatZ::new(nr_rows, nr_rows);
39
40        // FLINT doc-comment
41        // Computes an integer matrix H such that H is the unique (row) Hermite normal form of A
42        // along with the transformation matrix U such that UA = H.
43        // The algorithm used is selected from the implementations in FLINT as per fmpz_mat_hnf.
44        unsafe { fmpz_mat_hnf_transform(&mut hnf.matrix, &mut transform.matrix, &self.matrix) };
45
46        (hnf, transform)
47    }
48
49    /// Checks if `self` is a matrix in Hermite normal form.
50    ///
51    /// # Examples
52    /// ```
53    /// use qfall_math::integer::MatZ;
54    /// use std::str::FromStr;
55    /// let non_hnf = MatZ::from_str("[[1, 2, 12],[2, 4, 5]]").unwrap();
56    /// let hnf = MatZ::from_str("[[1, 2, 12],[0, 0, 19]]").unwrap();
57    ///
58    /// assert!(!non_hnf.is_in_hermite_nf());
59    /// assert!(hnf.is_in_hermite_nf());
60    /// ```
61    pub fn is_in_hermite_nf(&self) -> bool {
62        1 == unsafe { fmpz_mat_is_in_hnf(&self.matrix) }
63    }
64
65    /// Computes the unique Smith normal form of the matrix `self`.
66    ///
67    /// # Examples
68    /// ```
69    /// use qfall_math::integer::MatZ;
70    /// use std::str::FromStr;
71    /// let matrix = MatZ::from_str("[[1, 2, 12],[2, 4, 5]]").unwrap();
72    /// let snf_cmp = MatZ::from_str("[[1, 0, 0],[0, 19, 0]]").unwrap();
73    ///
74    /// let snf = matrix.smith_nf();
75    ///
76    /// assert_eq!(snf_cmp, snf);
77    /// ```
78    pub fn smith_nf(&self) -> Self {
79        let mut snf: MatZ = MatZ::new(self.get_num_rows(), self.get_num_columns());
80
81        unsafe { fmpz_mat_snf(&mut snf.matrix, &self.matrix) };
82
83        snf
84    }
85
86    /// Checks if `self` is a matrix in Smith normal form.
87    ///
88    /// # Examples
89    /// ```
90    /// use qfall_math::integer::MatZ;
91    /// use std::str::FromStr;
92    /// let non_snf = MatZ::from_str("[[1, 2, 12],[2, 4, 5]]").unwrap();
93    /// let snf = MatZ::from_str("[[1, 0, 0],[0, 19, 0]]").unwrap();
94    ///
95    /// assert!(!non_snf.is_in_smith_nf());
96    /// assert!(snf.is_in_smith_nf());
97    /// ```
98    pub fn is_in_smith_nf(&self) -> bool {
99        1 == unsafe { fmpz_mat_is_in_snf(&self.matrix) }
100    }
101}
102
103#[cfg(test)]
104mod test_hermite_nf {
105    use super::MatZ;
106    use std::str::FromStr;
107
108    /// Ensures that [`MatZ::hermite_nf`] and [`MatZ::is_in_hermite_nf`] works for small entries.
109    #[test]
110    fn small_entries() {
111        let matrix = MatZ::from_str("[[2,3,6,2],[5,6,1,6],[8,3,1,1]]").unwrap();
112        let h_cmp = MatZ::from_str("[[1, 0, 50, -11],[0, 3, 28, -2],[0, 0, 61, -13]]").unwrap();
113        let u_cmp = MatZ::from_str("[[9, -5, 1],[5, -2, 0],[11, -6, 1]]").unwrap();
114
115        let (h, u) = matrix.hermite_nf();
116
117        assert_eq!(h_cmp, h);
118        assert_eq!(u_cmp, u);
119        assert_eq!(h, &u * &matrix);
120
121        assert!(!matrix.is_in_hermite_nf());
122        assert!(h.is_in_hermite_nf());
123        assert!(!u.is_in_hermite_nf());
124    }
125
126    /// Ensures that [`MatZ::hermite_nf`] and [`MatZ::is_in_hermite_nf`] works for large entries.
127    #[test]
128    fn large_entries() {
129        let matrix = MatZ::from_str(&format!(
130            "[[{}, 0],[{}, {}]]",
131            i64::MAX,
132            2 * (i64::MAX as u64),
133            u64::MAX
134        ))
135        .unwrap();
136        let h_cmp = MatZ::from_str(&format!("[[{}, 0],[0, {}]]", i64::MAX, u64::MAX)).unwrap();
137        let u_cmp = MatZ::from_str("[[1, 0],[-2, 1]]").unwrap();
138
139        let (h, u) = matrix.hermite_nf();
140
141        assert_eq!(h_cmp, h);
142        assert_eq!(u_cmp, u);
143        assert_eq!(h, &u * &matrix);
144
145        assert!(!matrix.is_in_hermite_nf());
146        assert!(h.is_in_hermite_nf());
147        assert!(!u.is_in_hermite_nf());
148    }
149
150    /// Ensures that [`MatZ::hermite_nf`] and [`MatZ::is_in_hermite_nf`] work
151    /// for any matrix dimensions.
152    #[test]
153    fn dimensions() {
154        let mat_0 = MatZ::sample_uniform(4, 1, 0, 16).unwrap();
155        let mat_1 = MatZ::sample_uniform(5, 5, 0, 16).unwrap();
156        let mat_2 = MatZ::sample_uniform(2, 4, 0, 16).unwrap();
157
158        let (hnf_0, u_0) = mat_0.hermite_nf();
159        let (hnf_1, u_1) = mat_1.hermite_nf();
160        let (hnf_2, u_2) = mat_2.hermite_nf();
161
162        assert!(hnf_0.is_in_hermite_nf());
163        assert!(hnf_1.is_in_hermite_nf());
164        assert!(hnf_2.is_in_hermite_nf());
165
166        assert_eq!(hnf_0, u_0 * mat_0);
167        assert_eq!(hnf_1, u_1 * mat_1);
168        assert_eq!(hnf_2, u_2 * mat_2);
169    }
170}
171
172#[cfg(test)]
173mod test_smith_nf {
174    use super::MatZ;
175    use std::str::FromStr;
176
177    /// Ensures that [`MatZ::smith_nf`] and [`MatZ::is_in_smith_nf`] works for small entries.
178    #[test]
179    fn small_entries() {
180        let matrix = MatZ::from_str("[[2,3,6,2],[5,6,1,6],[8,3,1,1]]").unwrap();
181        let s_cmp = MatZ::from_str("[[1, 0, 0, 0],[0, 1, 0, 0],[0, 0, 1, 0]]").unwrap();
182
183        let s = matrix.smith_nf();
184
185        assert_eq!(s_cmp, s);
186
187        assert!(!matrix.is_in_smith_nf());
188        assert!(s.is_in_smith_nf());
189    }
190
191    /// Ensures that [`MatZ::smith_nf`] and [`MatZ::is_in_smith_nf`] works for large entries.
192    #[test]
193    fn large_entries() {
194        let matrix = MatZ::from_str(&format!(
195            "[[{}, 0],[{}, {}]]",
196            i64::MAX,
197            2 * (i64::MAX as u64),
198            u64::MAX
199        ))
200        .unwrap();
201        let s_cmp =
202            MatZ::from_str("[[1, 0],[0, 170141183460469231704017187605319778305]]").unwrap();
203
204        let s = matrix.smith_nf();
205
206        assert_eq!(s_cmp, s);
207
208        assert!(!matrix.is_in_smith_nf());
209        assert!(s.is_in_smith_nf());
210    }
211
212    /// Ensures that [`MatZ::smith_nf`] and [`MatZ::is_in_smith_nf`] work
213    /// for any matrix dimensions.
214    #[test]
215    fn dimensions() {
216        let mat_0 = MatZ::sample_uniform(4, 1, 0, 16).unwrap();
217        let mat_1 = MatZ::sample_uniform(5, 5, 0, 16).unwrap();
218        let mat_2 = MatZ::sample_uniform(2, 4, 0, 16).unwrap();
219
220        let snf_0 = mat_0.smith_nf();
221        let snf_1 = mat_1.smith_nf();
222        let snf_2 = mat_2.smith_nf();
223
224        assert!(snf_0.is_in_smith_nf());
225        assert!(snf_1.is_in_smith_nf());
226        assert!(snf_2.is_in_smith_nf());
227    }
228}
qfall_math/integer/mat_z/forms.rs

qfall_math/integer/mat_z/
forms.rs
