FADBAD.
A flexible C++ package for automatic differentiation.

IMM Technical Report 17/96

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.

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.

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.

The FADBAD Homepage


Last modified August 16, 1996
Finn Kuno Christensen

Back to IMM Homepage