Second-Order Adjoints by Source Code Manipulation of Numerical Programs
Uwe Naumann, Michael Maier, Jan Riehme, and Bruce Christianson
The analysis and modification of numerical programs in the context
of generating and optimizing adjoint code automatically probably
ranges among the technically and theoretically most challenging
source transformation algorithms known today. A complete compiler
for the target language (Fortran in our case) is needed to cover the
technical side. This amounts to a mathematically motivated semantic
transformation of the source code that involves the reversal of the
flow of data through the program. Both the arithmetic complexity and
the memory requirement can be substantial for large-scale numerical
simulations. Finding the optimal data-flow reveral schedule turns out to
be an NP-complete problem. The same complexity result applies to other
domain-specific peephole optimizations. In this paper we present a first
research prototype of the NAGWare Fortran compiler with the ability to
generate adjoint code automatically. Moreover, we discuss an approach
to generating second-order adjoint code for use in Newtontype algorithms
for unconstrained nonlinear optimization. While the focus of this paper
is mostly on the compiler issues some information on the mathematical
background will be found helpful for motivational purposes.