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 = "8394",
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 onedimensional 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 MINPACK2
optimization test set collection.",
keywords = "Differentiation partition, hybrid modes, optimal elimination ordering, higherlevel
operands, computational graph, program graph, hierarchical differentiation.",
referred = "[Mancini2002APH], [Naumann2002ETf], [Tadjouddine2001ATa].",
ad_theotech = "Hierarchical Approach",
year = "1996"
}
