OPTIMALITY-PRESERVING ELIMINATION OF LINEARITIES IN JACOBIAN ACCUMULATION

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