Performance of division/reciprocal/sqrt in multivariate, high-order auto diff

[Serrof]

DerivativeStructure implements intrinsic functions like division itself by composing from the left with univariate Taylor expansions, similarly to what is described here basically. This means in general that the "complexity" is at best N times the one of multiplication, where N is the order. However, exploiting recursive formulas between the derivatives allows to alleviate this dependency on N (see Neidinger), getting a "multiplication-like" algorithm. Although they are for the so-called normalized derivatives (with the factorials, as opposed to the standard ones used in Hipparchus), they could be adapted. A particular case, easily adaptable, is when the multiplication operator itself can be leveraged upon for the inversion: division (plus reciprocal) and square root.

Here is it for the division, reusing the syntax from DSCompiler:

    public void divide(final double[] lhs, final int lhsOffset,
                       final double[] rhs, final int rhsOffset,
                       final double[] result, final int resultOffset) {
        for (int i = 0; i < multIndirection.length; ++i) {
            result[resultOffset + i] = lhs[lhsOffset + i];
            for (int j = 0; j < multIndirection[i].length - 1; j++) {
                final MultiplicationMapper mapping = multIndirection[i][j];
                result[resultOffset + i] -= mapping.getCoeff() *
                        (result[resultOffset + mapping.lhsIndex] *
                        rhs[rhsOffset + mapping.rhsIndex]);
            }
            result[resultOffset + i] /= rhs[lhsOffset] * multIndirection[i][0].getCoeff();
        }
    }

Remark: using normalized derivatives to represent the expansion could also speed up computations as hinted in the same paper by Neidinger.

[Serrof]

For the previous code to work for sure, the prerequisite is that the multiplication mapping has monomials sorted in increasing total order. However from reading the docstring of DSCompiler, I'm not 100% sure about it. Could you confirm it's the case @maisonobe?