Volume 21, pp. 134-150, 2005.

Optimality-preserving elimination of linearities in Jacobian accumulation

Uwe Naumann and Jean Utke


We consider a mathematical function that is implemented in a high-level programming language 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 by 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 input 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 $({\bf 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.

Full Text (PDF) [438 KB], BibTeX

Key words

Jacobian accumulation, linearities, constant folding

AMS subject classifications

90C27, 26B10, 68N99.

< Back