Algorithmic Differentiation Through Automatic Graph Elimination Ordering (ADTAGEO)

Abstract

Algorithmic Differentiation Through Automatic Graph Elimination
Ordering (ADTAGEO) is based on the principle of Instant
Elimination: At runtime we dynamically maintain a DAG representing
only active variables that are alive at any time. Whenever an
active variable is deallocated or its value is overwritten the
corresponding vertex in the Live-DAG will be eliminated
immediately by the well known vertex elimination rule [1].

Consequently, the total memory requirement is equal to that of the
sparse forward mode. Assuming that local variables are destructed
in the opposite order of their construction (as in C++), a single
assignment code is in effect differentiated in reverse mode. If
compiler-generated temporaries are destroyed in reverse order too,
then Instant Elimination yields the statement level reverse mode of
ADIFOR [2] naturally.

The user determines the elimination order intentionally (or
unintentionally) by the order in which he declares variables,
which makes hybrid modes of AD possible by combining forward and
reverse differentiated parts.

By annotating the Live-DAG with local Hessians and applying second
order elimination rules, Hessian-vector products can be computed
efficiently since the annotated Live-DAG stores one half of the
symmetric Hessian graph only (as suggested in [1]).

Nested automatic differentiation is done easily by subsequent
propagations, since sensitivities between variables alive can be
obtained at any point in time within the Live-DAG.

The concept of maintaining a Live-DAG fits optimally into the
strategy of overloaded operators for classes, it is a very natural
example of Object Oriented Programming. A proof-of-concept
implementation in C++ is available (contact the first author).


References

1. Griewank, A.: Evaluating Derivatives. Principles and
   Techniques of Algorithmic Differentiation. 
   SIAM (2000)

2.Bischof, C.H., Carle, A., Khademi, P., Mauer, A.: ADIFOR 2.0:
   Automatic differentiation of Fortran 77 programs. 
   IEEE Computational Science & Engineering 3 (1996) 18-32