IMM Technical Report 17/96
The use of a symbolic differentiation package such as Maple or
Mathematica can solve the problem of obtaining expressions for the
derivatives. This method obviously avoids truncation errors but
usually these packages have problems in handling large expressions
and the time/space usage for computing derivatives can be enormous. In
worst case it can even cause a program to crash. Furthermore, common
subexpressions are usually not identified in the expressions and this
leads to unnecessary computations during the evaluation of the
derivatives.
Automatic differentiation is an alternative to the above methods. Here
derivatives are computed by using the very well known ``chain rule''
for composite functions, in a clever way. In automatic
differentiation the evaluation of a function and its derivatives are
calculated simultaneously, using the same code and common temporary
values. If the code for the evaluation is optimized, then the
computation of the derivatives will automatically be optimized. The
resulting differentiation is free from truncation errors, and if we
calculate the derivatives using interval analysis we will obtain
enclosures of the true derivatives. Automatic differentiation is
``easy'' to implement in languages with operator overloading
such as C++, Ada and PASCAL-XSC.
The FADBAD Homepage
Claus Bendtsen and Ole Stauning
For a copy of this paper, either
Introduction:
The importance of differentiation as a mathematical tool is obvious.
One of the first things we learn in elementary school is how to
manually differentiate expressions using a few elementary formulas.
Unfortunately the use of derivatives in scientific computing has
been quite limited due to the misunderstanding that derivatives are hard
to obtain. Many people still think that the only alternative to the
symbolic way of obtaining derivatives is to use divided differences
in which the difficulties in finding an expression for the derivatives
are avoided. But by using divided differences, truncation
errors are introduced and this usually has a negative effect on
further computations -- in fact it can lead to very inaccurate results.
FADBAD:
FADBAD is a C++ program package which combines the two basic ways of
applying the chain rule, namely forward- and backward automatic
differentiation. Both the forward- and the backward differentiation
methods use operator overloading to redefine the arithmetic
operations, so that the program is capable of calculating first order
derivatives. The only thing a user has to provide is the C++ program
that performs the evaluation of the function. Since the computation
of the derivatives is itself a C++ program we can obtain higher order
derivatives by building the forward- and the backward automatic
differentiation classes on top of each other. Using this approach we
can obtain derivatives of order p in 2^p different ways -- hereby
giving the possibility to minimize time/space usage of the
computations by choosing the optimal combination of the
algorithms. Depending, of course, on the function which we want to
differentiate.
Finn Kuno Christensen