The D* Symbolic Differentiation Algorithm

Functions with densely interconnected expression graphs, which arise in applications such as dynamics, space-time optimization, and PRT, can be difficult to efficiently differentiate using existing symbolic or automatic differentiation techniques. The new algorithm, D*, computes efficient symbolic derivatives for these functions by symbolically executing the expression graph at compile time to eliminate common subexpressions and by exploiting the special nature of the graph that represents the derivative of a function. This graph has a sum of products form; the new algorithm computes a factorization of this derivative graph along with an efficient grouping of product terms into subexpressions.

This paper is a revised and expanded version of the paper presented at SIGGRAPH 2007, most recently updated 11/1/2007.