"Optimality-Preserving Elimination of Linearities in Jacobian Accumulation"
U. Naumann and J. Utke
Preprint Version: [pdf]
We consider a mathematical function that is implemented in high-level programming languages such as C or Fortran. This function is assumed to be differentiable in some neighborhood of a set of input arguments. For available local partial derivatives of the arithmetic operators and intrinsic functions provided by the programming language, the Jacobian of the function at the given arguments can be accumulated using the chain rule. This technique is known as automatic differentiation of numerical programs.
Under the above assumptions, the values of the local partial derivatives are well defined for given values of the inputs. A code for accumulating the Jacobian matrix that is based on the chain rule takes these partial derivatives as inputs and computes the nonzero entries of the Jacobian using only scalar multiplications and additions. The exploitation of the associativity of the chain rule or, equivalently, the algebraic properties of the corresponding field (R,*,+) - in particular associativity of the multiplication and distributivity - to minimize the number of multiplications leads to a combinatorial optimization problem that is widely conjectured to be np-hard. Several heuristics have been developed for its approximate solution. Their efficiency always depends on the total number of partial derivatives.
Linearities in the function lead to constant partial derivatives that do not depend on the input values. We present a specialized constant folding algorithm to decrease the size of the combinatorial problem in order to increase the efficiency of heuristics for its solution. Moreover, we show that this algorithm preserves optimality in the sense that an optimal solution for the reduced problem yields an objective value no worse than that of an optimal solution for the original problem.