Search Results

Documents authored by Riehme, Jan


Document
Algorithmic Differentiation Through Automatic Graph Elimination Ordering (ADTAGEO)

Authors: Jan Riehme and Andreas Griewank

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


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

Cite as

Jan Riehme and Andreas Griewank. Algorithmic Differentiation Through Automatic Graph Elimination Ordering (ADTAGEO). In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{riehme_et_al:DagSemProc.09061.4,
  author =	{Riehme, Jan and Griewank, Andreas},
  title =	{{Algorithmic Differentiation Through Automatic Graph  Elimination Ordering (ADTAGEO)}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.4},
  URN =		{urn:nbn:de:0030-drops-20852},
  doi =		{10.4230/DagSemProc.09061.4},
  annote =	{Keywords: Automatic Differentiation, Instant Elimination, Live-DAG, symmetric Hessian-DAG, forward mode, reverse mode, checkpointing, ADTAGEO}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail