#
The Data-Dependence Graph of Adjoint Programs

*Laurent Hascoët*
*(INRIA, BP93, 06902 Sophia-Antipolis, France)*

INRIA Research Report #4167, april 2001 (17 pages)

**Abstract:**
Automatic Differentiation is a technique that permits generation of
adjoint programs, which compute gradients. In scientific computation,
these gradients are a fundamental tool for optimization or data assimilation.
Computation of a gradient is relatively expensive, and should therefore
be optimized whenever possible. The study of these program optimizations
is most often based on the data-dependence graph. Under precise assumptions,
we prove that the adjoint program's data-dependence graph is isomorphic to
a sub-graph of the original data-dependence graph. The proof relies on a
refined definition of the notion of data-dependence, and on a formal
definition of adjoint programs in terms of products of local Jacobian
matrices. This theorem can be used to transpose optimizations of the
original program, to the adjoint program. It can also justify specific
transformations on the adjoint. We give some examples of such applications

**Keywords:**
Automatic Differentiation, reverse mode, adjoints, gradients,
data-dependences, parallelization, Memory optimization

Full text (pdf)
`
@techreport{Hascoet2001TDG,
author = {Hasco\"et, L.},
title = {The Data-Dependence Graph of Adjoint Programs},
institution = {INRIA},
type = {Research Report},
number=4167,
url = "http://www.inria.fr/rrrt/rr-4167.html",
year=2001
}
`