Computing the Determinant in Rust: Part 1.

Join Medium with my referral link - applied.math.coding

In these stories (here and here), we have looked at some basic properties of determinants. Our goal in this story is to compute a determinant numerically. To do this there exists several ways and most of these are not efficient at all. The first implementation we are going to look at, is a straightforward method. Although it provides us with some training in programming, it is horrible inefficient. The second implementation which we will look at in a follow-up story, is far more efficient and even easier to realize.

The implementations will be done in Rust. In case you need some wrap-up, feel invited to this small introduction.

Direct computation:

Give a square matrix A we can compute its determinate det A by the following formula:

The sum is taken over all permutations and sgn refers to the parity of a given permutation. You can find more on this formula in the above referenced stories and about permutations here.

In order to sum over all permutations, we are going to implement an iterator that lets us enumerate all permutations together with their parities:

pub struct Permutations(usize);

impl Permutations {
    pub fn iter(&self) -> PermutationIterator {
        PermutationIterator::create((0..self.0).collect())
    }
}

pub struct PermutationIterator {
    n: usize,                                       // produced perm. size
    e: usize,                                       // the element to shift
    e_idx: usize,                                   // the next shift position
    reduced_perm: (Vec<usize>, i8),       // the next perm. of reduced_iter
    reduced_iter: Option<Box<PermutationIterator>>, // iter. through red. perms
}

For instance, given v = [0, 1, 2], we cut-off the first element to get 0 and [1 , 2] and then enumerate all permutations of [1, 2]. Given such a permutation, say p = [1, 2], we produce permutations for v by shifting 0 through p:

[0, 1, 2]

[1, 0, 2]

[1, 2, 0]