Symbolic Differentiation

D* generates symbolic derivatives which can be thousands of times faster than those generated by Mathematica or automatic differentiation. Functions with densely interconnected expression graphs, which arise in applications such as dynamics, spacetime optimization (also known as the optimal control problem), and PRT, can be difficult to efficiently differentiate using existing symbolic or automatic differentiation techniques. The D* algorithm 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. For the test suite problems D* generates symbolic derivatives which are up to 4.6×10^3 times faster than those computed by the symbolic math program Mathematica and up to 2.2×10^5 times faster than the non-symbolic automatic differentiation program CppAD. In some cases, the D* derivatives rival the best manually derived solutions.