Jacobian Code Generated by Source Transformation and Vertex Elimination is as Efficient as Hand-Coding
Shaun A Forth, Mohamed Tadjouddine, John D Pryce & John K Reid
Published in
ACM Transactions on Mathematical Software (TOMS), Volume 30 , Issue 3
(September 2004) pp 266 - 299
Abstract
This paper presents the first extended set of results from EliAD, a
source-transformation implementation of the vertex-elimination automatic
differentiation approach to calculating the Jacobians of functions defined by
Fortran code (Griewank and Reese, Automatic Differentiation of Algorithms:
Theory, Implementation, and Application, 1991, pp. 126-135). We introduce the
necessary theory in terms of well known algorithms of numerical linear algebra
applied to the linear, extended Jacobian system that prescribes the
relationship between the derivatives of all variables in the function code.
Using an example, we highlight the potential for numerical instability in
vertex-elimination. We describe the source transformation implementation
of our tool EliAD and present results from 5 test cases, 4 of which are taken
from the MINPACK-2 collection (Averick et al, Report ANL/MCS-TM-150, 1992) and
for which hand-coded Jacobian codes are available. On 5 computer/compiler
platforms, we show that the Jacobian code obtained by EliAD is as efficient as
hand-coded Jacobian code. It is also between 2 to 20 times more efficient
than that produced by current, state of the art, Automatic Differentiation
tools even when such tools make use of sophisticated techniques such as sparse
Jacobian compression. We demonstrate the effectiveness of reverse-ordered
pre-elimination from the (successively updated) extended Jacobian system of all
intermediate variables used once. Thereafter, the monotonic
forward/reverse ordered eliminations of all other intermediates is shown to be
very efficient. On only one test case were orderings determined by the
Markowitz or related VLR heuristics found superior. A re-ordering of the
statements of the Jacobian code, with the aim of reducing reads and writes of
data from cache to registers, was found to have mixed effects but could be very
beneficial.
Download
Authors' PDF, copyright ACM. Posted here by permission of ACM for
your personal use. Not for redistribution. saf_toms04.pdf
ACM Portal Entry: http://doi.acm.org/10.1145/1024074.1024076