Generative Programming for Automatic Differentiation in C++0x

Marco Nehmeier

The computation of the first or higher derivatives of a function is a common problem in scientific computing.

The most obvious approach to compute the derivative values is the symbolic differentiation which applies the well known rules of differentiation onto the expression to compute a formal expression of the derivative function.

Another method called numerical differentiation is the approximation of the derivative with difference quotients.

Superior to these approaches is the automatic differentiation which is a technique to compute a value of the expression and the derivative together by applying the well known rules of differentiation. The difference to symbolic differentiation is that it propagates numerical values instead of formal expressions.

Commonly used implementations of automatic differentiation may be divided into two categories, the implementations using operator overloading to compute the values of the function and the derivative together in contrast to special tools applying the technique of source transformation to mix in the expressions to compute the derivatives. Both of these techniques are somehow inflexible in the manner that the operators are not overloaded for high order differentiation or additional tools are required for the source transformation.

In this paper we use expression templates and template meta programming to mix in the code for the partial differentiation. The main concept is to apply the symbolic differentiation at compile time only onto the single operations of the expression tree to create the run time code for the automatic differentiation. This has two advantages, we can, in theory, compute derivatives of any order and secondly the differentiation of the operations is done with types. This means that the symbolic differentiation of an operation with a specified order is performed only once by the compiler.

Our generic approach provides a domain specific language for partial automatic differentiation of an arbitrary order which is easily extendable by new types. Several C++ and especially C++0x template programming concepts and techniques like variadic templates, type lists or variadic tuples are used to realize the specification of the automatic differentiation at compile time. Common template meta programming techniques are refined.

We tested the functionality, correctness and performance of our implementation in different case studies for floating point as well as interval data types and compared it against other implementations.