When is automatic differentiation cheap?

Automatic differentiation allows us to numerically evaluate the derivative of a program on a particular input. There is a theorem that this computation can done at a cost less than five times the cost to run the original program. This factor of five is an upper bound.

In what situations can this cost be further reduced? Many in-the-field derivative codes run at near the speed of the original program. What is done to obtain this speed-up?

What are traits of the original program that can be exploited to speed up computation?

What software engineering tricks can be employed to speed up computation?

• Certainly, one would want to exploit the special properties of derivatives of functions like the exponential function and trigonometric functions. Lots of potential common subexpressions there. Nov 30, 2011 at 14:55
• Are you asking about reverse-mode or forward-mode? Dec 1, 2011 at 1:05
• My (limited) understanding is that both forward and reverse modes have roughly similar costs. Dec 1, 2011 at 14:30

My limited understanding of AD parallels what Matt has said. To speed up the computation of derivatives, the structure of the expression graph must exploit sparsity and scarcity in the set of Jacobian matrices. (See this paper$$^1$$ by Griewank for more insight.) The software engineering tricks would likely be in the AD code itself to restructure the expression graph to take advantage of these properties in the set of Jacobian matrices. Knowing how the AD code generates an expression graph from the code you are writing would in turn help you better understand how to write code that requires fewer computations. Any good AD code should already take advantage of intrinsics with common subexpressions, but good AD codes are hard to write.