John Reid (Rutherford Appleton Laboratory)

On the utility of automatic differentiationWednesday 26 January 2000 at 15.30, JCMB 6324

Abstract

Automatic differentiation is a means of computing the derivatives of a variable for a given set ofvalues of the independent variables. It does not seek to construct an analytic formula (symbolic algebra), but works more directly from the computer code that expresses the value of the variable. There are two basic methods.

In the forward method, for each independent variable and each dependent variable, thecomputer holds a value and a representation of all the desired derivatives. For each elementary operation, the desired derivatives of the result are calculated from those of the primaries by the chain rule.

In the backward method, a graph is constructed to represent the whole computation, with a nodei for each independent variable, i = 1, 2, ..., n, and a node i for the result of each elementary operation, i = n+1, n+2, ..., with links to nodes for the primaries of the operation. Only the values are constructed initially in the forward pass that constructs the graph.

The aim of this talk is to review work in this area and explain how the algorithm is implementedin the Fortran 90 code HSL_AD01 of the Harwell Subroutine Library. The forward method is very effective if the number of independent variables is small, since then the extra work and storage to compute and hold all the derivatives as the computation proceeds is modest. For a large number of independent variables, the forward method becomes impractical unless the Jacobian is sparse, butthe work of the backward method in computing first derivatives is bounded by a small fixed multiple of the work needed for the values themselves. The disadvantage of the backward method is that the whole computational graph has to be stored, which is not practical for very long computations.