ABSTRACT
Computing derivatives of numerical models F (x) 7→ y : Rn 7→ Rm given as a computer program P is an important but also compute-intensive task. Automatic or algorithmic1differentiation (AD) [1] provides the means to obtain such derivatives. OpenAD [2] implements AD as a source transformation applied to Fortran programs for both the forward and reverse modes. In this paper we describe the solutions to three combinatorial aspects of AD as implemented in OpenAD. For information regarding the general use of OpenAD please see [3]. Because OpenAD is a source transformation tool, the combinatorial problems are solved at compile time; hence, our approach can afford costly heuristics to approximate a good solution. Using such heuristics even with small improvements is justified when, for instance, these improvements benefit the numerical kernel of a loop and therefore the improvement accumulates over the runtime, realizing considerable savings. Our intention is
c=c*c324342
c*c31=51c
c = c
(a) (b) (c) (d) (e)
FIGURE 6.1: Sequence of statements (a), corresponding sequence of elemental operations enumerating the computed values (b), the corresponding G using the value enumeration (c), elimination of vertex 3 from G (d), and front elimination of edge (1, 3) from G (e).
