Automatic differentiation (AD) is a technique for augmenting computer programs with derivative computations. It exploits the fact that every computer program, no matter how complicated, executes a sequence of elementary arithmetic operations such as additions or elementary functions such as exp(). By applying the chain rule of derivative calculus repeatedly to these operations, derivatives of arbitrary order can be computed automatically, and accurate to working precision.
Traditionally, two approaches to automatic differentiation have been developed: the so-called forward and reverse modes. These modes are distinguished by how the chain rule is used to propagate derivatives through the computation. The forward mode propagates derivatives of intermediate variables with respect to the independent variables. Given independent variables x, say, and dependent variables y, say, the linearity of differentiation allows the forward mode to compute arbitrary linear combinations J * S of columns of the Jacobian
For an n * p matrix S, the effort required is roughly
O(p) times the runtime and memory of the original program.
In particular, when S is a vector s, we compute
the directional derivative
. This type of
differentiation is also used to obtain a so-called tangent linear model.
In contrast, the reverse mode of automatic differentiation propagates derivatives of the final result with respect to an intermediate quantity, adjoint quantity. To propagate adjoints, one must be able to reverse the flow of the program and must remember or recompute any intermediate value that nonlinearly impacts the final result. For a q * m matrix W, the reverse mode allows us to compute the row linear combination W * J with O(q) times as many floating-point operations as required for the evaluation of f. The storage requirements are harder to predict and depend to a large extent on the nonlinearity of the program and the implementation approach chosen. The reverse mode also corresponds to a method for obtaining the discrete adjoint.
Recent research has centered on hybrid modes that try to combine the best features of the forward and reverse mode. Such techniques, as well as the forward and reverse mode, are described, for example, in the volumes
This
document was compiled
with contributions by Martin Berz, Mike Bartholomew-Biggs,
Stephen Brown,
Phil Brubaker,
Alan Carle, Bruce Christianson, David Cowey, Frederic
Eyssette, David M. Gay, Ralf Giering, Andreas Griewank, Christele Faure,
Jim Horwedel,
Peyvand Khademi, Koichi Kubota, Andrew Mauer, Michael B. Monagan, John
Pryce, John Reid, Andreas Rhodin, Nicole Rostaing-Schmidt, and Jean
Utke.