15
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – J. M.
    Nov 30, 2011 at 14:55
  • $\begingroup$ Are you asking about reverse-mode or forward-mode? $\endgroup$
    – Jed Brown
    Dec 1, 2011 at 1:05
  • $\begingroup$ My (limited) understanding is that both forward and reverse modes have roughly similar costs. $\endgroup$
    – MRocklin
    Dec 1, 2011 at 14:30

2 Answers 2

Reset to default
8
$\begingroup$

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.

The standard reference in the field is Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Second Edition by Andreas Griewank and Andrea Walther, and should provide more detailed information on how to reduce the number of computations needed to evaluate the derivative of a program.

  1. Griewank, A., Naumann, U. Accumulating Jacobians as chained sparse matrix products. Math. Program., Ser. A 95, 555–571 (2003). https://doi.org/10.1007/s10107-002-0329-7
Improve this answer
$\endgroup$
3
$\begingroup$

Any AD still needs these intrinsics to be provided, so I can't see what that has to do with generic complexity of an expression. I am guessing you can classify complexity by the number of paths through the expression graph since you phrase AD this way. Andrew Lyons has good work on series-parallel graphs here.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.