License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-20852
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2085/

Riehme, Jan ; Griewank, Andreas

Algorithmic Differentiation Through Automatic Graph Elimination Ordering (ADTAGEO)

pdf-format:
Dokument 1.pdf (99 KB)


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

BibTeX - Entry

@InProceedings{riehme_et_al:DSP:2009:2085,
  author =	{Jan Riehme and Andreas Griewank},
  title =	{Algorithmic Differentiation Through Automatic Graph  Elimination Ordering (ADTAGEO)},
  booktitle =	{Combinatorial Scientific Computing},
  year =	{2009},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  number =	{09061},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2085},
  annote =	{Keywords: Automatic Differentiation, Instant Elimination, Live-DAG, symmetric Hessian-DAG,  forward mode, reverse mode, checkpointing, ADTAGEO}
}

Keywords: Automatic Differentiation, Instant Elimination, Live-DAG, symmetric Hessian-DAG, forward mode, reverse mode, checkpointing, ADTAGEO
Seminar: 09061 - Combinatorial Scientific Computing
Issue date: 2009
Date of publication: 24.07.2009


DROPS-Home | Fulltext Search | Imprint Published by LZI