zkhash/
utils.rs

Help
1// use std::cmp::min;
2
3use ark_ff::PrimeField;
4
5// pub fn from_u64<F: PrimeField>(val: u64) -> F {
6//     F::from_repr(F::Repr::from(val)).unwrap()
7// }
8
9// guassian elimination
10pub fn mat_inverse<F: PrimeField>(mat: &[Vec<F>]) -> Vec<Vec<F>> {
11    let n = mat.len();
12    assert!(mat[0].len() == n);
13
14    let mut m = mat.to_owned();
15    let mut inv = vec![vec![F::zero(); n]; n];
16    for (i, invi) in inv.iter_mut().enumerate() {
17        invi[i] = F::one();
18    }
19
20    // upper triangle
21    for row in 0..n {
22        for j in 0..row {
23            // subtract from these rows
24            let el = m[row][j];
25            for col in 0..n {
26                // do subtraction for each col
27                if col < j {
28                    m[row][col] = F::zero();
29                } else {
30                    let mut tmp = m[j][col];
31                    tmp.mul_assign(&el);
32                    m[row][col].sub_assign(&tmp);
33                }
34                if col > row {
35                    inv[row][col] = F::zero();
36                } else {
37                    let mut tmp = inv[j][col];
38                    tmp.mul_assign(&el);
39                    inv[row][col].sub_assign(&tmp);
40                }
41            }
42        }
43        // make 1 in diag
44        let el_inv = m[row][row].inverse().unwrap();
45        for col in 0..n {
46            match col.cmp(&row) {
47                std::cmp::Ordering::Less => inv[row][col].mul_assign(&el_inv),
48                std::cmp::Ordering::Equal => {
49                    m[row][col] = F::one();
50                    inv[row][col].mul_assign(&el_inv)
51                }
52                std::cmp::Ordering::Greater => m[row][col].mul_assign(&el_inv),
53            }
54        }
55    }
56
57    // upper triangle
58    for row in (0..n).rev() {
59        for j in (row + 1..n).rev() {
60            // subtract from these rows
61            let el = m[row][j];
62            for col in 0..n {
63                // do subtraction for each col
64
65                #[cfg(debug_assertions)]
66                {
67                    if col >= j {
68                        m[row][col] = F::zero();
69                    }
70                }
71                let mut tmp = inv[j][col];
72                tmp.mul_assign(&el);
73                inv[row][col].sub_assign(&tmp);
74            }
75        }
76    }
77
78    #[cfg(debug_assertions)]
79    {
80        for (row, mrow) in m.iter().enumerate() {
81            for (col, v) in mrow.iter().enumerate() {
82                if row == col {
83                    debug_assert!(*v == F::one());
84                } else {
85                    debug_assert!(*v == F::zero());
86                }
87            }
88        }
89    }
90
91    inv
92}
93
94pub fn mat_transpose<F: PrimeField>(mat: &[Vec<F>]) -> Vec<Vec<F>> {
95    let rows = mat.len();
96    let cols = mat[0].len();
97    let mut transpose = vec![vec![F::zero(); rows]; cols];
98
99    for (row, matrow) in mat.iter().enumerate() {
100        for col in 0..cols {
101            transpose[col][row] = matrow[col];
102        }
103    }
104    transpose
105}
zkhash/utils.rs

zkhash/
utils.rs
