Publication: Using Directed Edge Separators to Increase Efficiency in the Determination of Jacobian Matrices via Automatic Differentiation
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Using Directed Edge Separators to Increase Efficiency in the Determination of Jacobian Matrices via Automatic Differentiation

- incollection -
 

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

BibTeX
@INCOLLECTION{
         Coleman2012UDE,
       title = "Using Directed Edge Separators to Increase Efficiency in the Determination of
         {J}acobian Matrices via Automatic Differentiation",
       doi = "10.1007/978-3-642-30023-3_19",
       author = "Thomas F. Coleman and Xin Xiong and Wei Xu",
       abstract = "",
       pages = "209--219",
       crossref = "Forth2012RAi",
       booktitle = "Recent Advances in Algorithmic Differentiation",
       series = "Lecture Notes in Computational Science and Engineering",
       publisher = "Springer",
       address = "Berlin",
       volume = "87",
       editor = "Shaun Forth and Paul Hovland and Eric Phipps and Jean Utke and Andrea Walther",
       isbn = "978-3-540-68935-5",
       issn = "1439-7358",
       year = "2012"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)