Author(s)
Thomas F. Coleman , Xin Xiong , Wei Xu

Published in
Recent Advances in Algorithmic Differentiation

Editor(s)
Shaun Forth, Paul Hovland, Eric Phipps, Jean Utke, Andrea Walther

Year
2012

Publisher
Springer

Abstract
Every numerical function evaluation can be represented as a directed acyclic graph (DAG), beginning at the initial input variable settings, and terminating at the output or corresponding function value(s). The “reverse mode” of automatic differentiation (ad) generates a “tape” which is a representation of this underlying DAG. In this work we illustrate that a directed edge separator in this underlying DAG can yield space and time efficiency gains in the application of ad. Use of directed edge separators to increase ad efficiency in different ways than proposed here has been suggested by other authors (Bischof and Haghighat, Hierarchical approaches to automatic differentiation. In: Berz M, Bischof C, Corliss G, Griewank A (eds) Computational differentiation: techniques, applications, and tools, SIAM, Philadelphia, PA, pp 83–94, 1996; Bücker and Rasch, ACM Trans Math Softw 29(4):440–457, 2003). In contrast to these previous works, our focus here is primarily on space. Furthermore, we explore two simple algorithms to find good directed edge separators, and show how these ideas can be applied recursively to great advantage. Initial numerical experiments are presented.

Cross-References
Forth2012RAi

AD Tools
ADMAT / ADMIT

AD Theory and Techniques
Combinatorics, Computational Graph