Function to invert Eigen matrix without branching statements for auto differentiation

Question

I need to invert an Eigen matrix (9x9 in my particular case) as a part of code that I want to automatically differentiate using CppAD. For this to succeed the code executing the inversion can not contain any branching like for example if or switch statements. Unfortunately, the inverse function of Eigen contains branching with makes the algorithmic differentiation of CppAD fail.

Mathematically it should be possible to come up with a formulation that does not need branching for a fixed matrix size that is guaranteed to be invertible. Is that correct?

Do you know of any library that implements such an inverse without branching?

Answer 1

There is a mechanical conversion from branch to no-branch for arithmetic functions.

Duplicate all the variables you use in each branch, and calculate both halves. At the end of the block, multiply the if branch by condition, and the else branch by !condition, then sum them.

Similarly for a switch, calculate all the cases, and multiply by value == case.

E.g.

Mat frob_branch(Mat a, Mat b) {
    if (a.baz()) {
        return a * b;
    } else {
        return b * a;
    }
}

becomes

Mat frob_no_branch(Mat a, Mat b) {
    auto if_true = a * b;
    auto if_false = b * a;
    bool condition = a.baz();
    return (if_true * condition) + (if_false * !condition);
}