OTC Seminar Series ABSTRACTS
Title On the combinatorics behind Jacobian accumulation
Author(s) Uwe Naumann
Abstract

Jacobian matrices of vector functions given as computer programs can be computed with machine accuracy using Automatic Differentiation (AD). The two basic modes of AD - forward and reverse - possibly combined with techniques for exploiting sparsity, may result in varying computational costs. For control flow independent problems the number of arithmetic operations can be minimized by solving a computationally hard combinatorial optimization problem on the linearized computational graph. Following a brief introduction to the principles behind AD this talk will focus on the accumulation of Jacobians by elimination techniques applied to the linearized computational graph. We will present vertex, edge, and face elimination and discuss various approaches to approximating the solution of the Optimal Jacobian Accumulation problem, including heuristics, stochastic algorithms, and dynamic programming as well as a deterministic algorithm for an important special case. Finally, the abstract setup will be regarded in the context of differentiation enabled compiler technology. The pre-accumulation of local gradients and Jacobians at the statement or basic block level represents a fundamental optimization technique for derivative code. The implementation of the theoretical results is the subject of ongoing development work at Argonne National Laboratory, NAG Ltd. Oxford, UK, and Royal Military College of Science, Shrivenham, UK

  .close window