The Combinatorics of Adjoint Code Generation

Professor Uwe Naumann
RWTH Aachen University
Aachen Germany

Abstract:

Automatic differentiation (AD) is a compiling technique for transforming
numerical simulation programs into code for computing derivatives.
We begin this talk with a brief introduction to AD.

In large-scale nonlinear optimization problems, the ``adjoint'' mode of AD is
of particular interest, since they enable derivatives to be computed at a
computational cost that is a small constant multiple of the cost of running the
original program. The robust generation of efficient adjoint code is one of the
big challenges in computational science and engineering. The main issue to be
addressed is the reversal of the program flow (control and data). All
intermediate values need to be recovered in reverse order.

Storing them on a stack is not an option for large-scale simulation. Repeated
recomputation as a function of the program's inputs yields quadratic growth of
the computational complexity. Checkpointing schemes have been developed as
trade-offs between storage and recomputation. The combinatorial problem is to
place checkpoints such that the overall computational cost of an evaluation of
the adjoint code is minimized. We propose a proof for this problem being
intractable (NP-complete) and comment on approaches to its approximate
solution.

Short Bio:

Professor Uwe Naumann is an associate professor of computer science at the
RWTH Aachen University, Germany. He received his PhD. in Discrete
Mathematics from Technical University Dresden, Germany in 1999. He has held
earlier appointments at INRIA, Sophia-Antipolis, France, the University of
Hertfordshire, U.K., and Argonne National Laboratory. He is one of the
chief architects of the OpenAD software for automatic differentiation. His
research interests are in combinatorial scientific computing, programming
languages, compilers and software engineering.