| 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
|
|