U. Naumann, "On Optimal Jacobian Accumulation for Single Expression use Programs," Preprint ANL/MCS-P944-0402, April 2002. [pdf]
ADIFOR and ADIC, the widely used software tools for Automatic Differentiation, use assignment-level reverse mode to compute local gradients of scalar assignment. This pre-accumulation often results in very efficient forward-mode derivative code. Scalar assignments belong to the class of Single Expression Use (SEU) programs. There, the values of all intermediate variables are read exactly once. Based on several theoretical results, we derive an algorithm for generating optimal Jacobian code for SEU programs. The number of floating-point operations performed during the accumulation of the Jacobian is minimized.