haar_lib/linalg/mod_p/
gaussian_elim.rs

1//! ガウスの消去法 (mod p)
2use crate::num::ff::FFElem;
3
4/// mod p上で行列を掃き出し、ランクを求める。
5pub fn gaussian_elim<T>(mut a: Vec<Vec<T>>) -> (usize, Vec<Vec<T>>)
6where
7    T: FFElem + Copy,
8{
9    let n = a.len();
10    let Some(m) = a.first().map(|a| a.len()) else {
11        return (0, a);
12    };
13
14    assert!(a.iter().all(|r| r.len() == m));
15    let mut rank = 0;
16
17    for j in 0..m {
18        let mut pivot = None;
19
20        for (i, ai) in a.iter().enumerate().skip(rank) {
21            if ai[j].value() != 0 {
22                pivot = Some(i);
23                break;
24            }
25        }
26
27        if let Some(pivot) = pivot {
28            a.swap(pivot, rank);
29
30            let mut ar = a.swap_remove(rank);
31            let d = ar[j].inv();
32            for x in ar.iter_mut() {
33                *x *= d;
34            }
35
36            for ai in a.iter_mut() {
37                let d = ai[j];
38                if d.value() != 0 {
39                    for (aij, arj) in ai.iter_mut().zip(ar.iter()) {
40                        *aij -= *arj * d;
41                    }
42                }
43            }
44
45            a.push(ar);
46            a.swap(rank, n - 1);
47
48            rank += 1;
49        } else {
50            continue;
51        }
52    }
53
54    (rank, a)
55}
haar_lib/linalg/mod_p/gaussian_elim.rs

haar_lib/linalg/mod_p/
gaussian_elim.rs
