Publication: Hierarchical Approaches to Automatic Differentiation
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Hierarchical Approaches to Automatic Differentiation

- incollection -
 

Author(s)
Christian H. Bischof , Mohammad R. Haghighat

Published in
Computational Differentiation: Techniques, Applications, and Tools

Editor(s)
Martin Berz, Christian Bischof, George Corliss, Andreas Griewank

Year
1996

Publisher
SIAM

Abstract
A mathematical function, specified by a computer program, can be differentiated efficiently through the exploitation of its program structure. The important properties of a program for the efficient generation of derivative code are the asymmetries between the number of inputs and outputs of program components at various levels of abstraction and the mathematical complexity of the involved operators. Automatic generation of efficient derivative codes thus requires analysis of programs for detection of such properties and systematic methods for their exploitation in composing the derivative codes. We suggest a hierarchical approach based on a partitioning of the computational or program graph as a means to deduce workable solutions to this hard problem. Each partition corresponds to a localized scope for derivative computation, and hierarchical partitions provide a mechanism for exploiting program structure at various levels. As a particular example, we discuss dynamic programming approaches for finding good one-dimensional partitions and generalizations to arbitrary directed acyclic graphs that, by recycling substructure information, allow one to determine the optimal elimination ordering for a graph with n nodes with complexity O(2n), as compared with the O(n!) complexity of a naive search. Lastly, we give a concrete example illustrating the hierarchical approach on the driven cavity problem from the MINPACK-2 optimization test set collection.

Cross-References
Berz1996CDT

AD Theory and Techniques
Hierarchical Approach

BibTeX
@INCOLLECTION{
         Bischof1996HAt,
       author = "Christian H. Bischof and Mohammad R. Haghighat",
       editor = "Martin Berz and Christian Bischof and George Corliss and Andreas Griewank",
       title = "Hierarchical Approaches to Automatic Differentiation",
       booktitle = "Computational Differentiation: Techniques, Applications, and Tools",
       pages = "83--94",
       publisher = "SIAM",
       address = "Philadelphia, PA",
       key = "Bischof1996HAt",
       crossref = "Berz1996CDT",
       abstract = "A mathematical function, specified by a computer program, can be differentiated
         efficiently through the exploitation of its program structure. The important properties of a program
         for the efficient generation of derivative code are the asymmetries between the number of inputs and
         outputs of program components at various levels of abstraction and the mathematical complexity of
         the involved operators. Automatic generation of efficient derivative codes thus requires analysis of
         programs for detection of such properties and systematic methods for their exploitation in composing
         the derivative codes. We suggest a hierarchical approach based on a partitioning of the
         computational or program graph as a means to deduce workable solutions to this hard problem. Each
         partition corresponds to a localized scope for derivative computation, and hierarchical partitions
         provide a mechanism for exploiting program structure at various levels. As a particular example, we
         discuss dynamic programming approaches for finding good one-dimensional partitions and
         generalizations to arbitrary directed acyclic graphs that, by recycling substructure information,
         allow one to determine the optimal elimination ordering for a graph with $n$ nodes with complexity
         $O(2^n)$, as compared with the $O(n!)$ complexity of a naive search. Lastly, we give a concrete
         example illustrating the hierarchical approach on the driven cavity problem from the MINPACK-2
         optimization test set collection.",
       keywords = "Differentiation partition, hybrid modes, optimal elimination ordering, higher-level
         operands, computational graph, program graph, hierarchical differentiation.",
       referred = "[Mancini2002APH], [Naumann2002ETf], [Tadjouddine2001ATa].",
       ad_theotech = "Hierarchical Approach",
       year = "1996"
}


back
  

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