

Jacobian Code Generated by Source Transformation and Vertex Elimination can be as Efficient as HandCoding
Article in a journal
  

Author(s)
Shaun A. Forth
, Mohamed Tadjouddine
, John D. Pryce
, John K. Reid

Published in
ACM Transactions on Mathematical Software 
Year 2004 
Abstract This paper presents the first extended set of results from EliAD, a sourcetransformation implementation of the vertexelimination 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. 126135). We introduce the necessary theory in terms of well known algorithms of numerical linear algebra applied to the linear, extended Jacobian system that prescribes their relationship between the derivatives of all variables in the function code. Using an example, we highlight the potential for numerical instability in vertexelimination. We describe the source transformation implementation of our tool EliAD and present results from 5 test cases, 4 of which are taken from the MINPACK2 collection (Averick et al, Report ANL/MCSTM150, 1992) and for which handcoded Jacobian codes are available. On 5 computer/compiler platforms, we show that the Jacobian code obtained by EliAD is as efficient as handcoded 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 reverseordered preelimination 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 reordering 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. 
AD Theory and Techniques Code Optimization, Data Flow Analysis, XCountry 
BibTeX
@ARTICLE{
Forth2004JCG,
ad_theotech = "Code Optimization, Data Flow Analysis, XCountry",
author = "Shaun A. Forth and Mohamed Tadjouddine and John D. Pryce and John K. Reid",
title = "Jacobian Code Generated by Source Transformation and Vertex Elimination can be as
Efficient as HandCoding",
abstract = "This paper presents the first extended set of results from EliAD, a
sourcetransformation implementation of the vertexelimination 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. 126135). We
introduce the necessary theory in terms of well known algorithms of numerical linear algebra applied
to the linear, extended Jacobian system that prescribes their relationship between the derivatives
of all variables in the function code. Using an example, we highlight the potential for numerical
instability in vertexelimination. We describe the source transformation implementation of our tool
EliAD and present results from 5 test cases, 4 of which are taken from the MINPACK2 collection
(Averick et al, Report ANL/MCSTM150, 1992) and for which handcoded Jacobian codes are available.
On 5 computer/compiler platforms, we show that the Jacobian code obtained by EliAD is as efficient
as handcoded 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
reverseordered preelimination 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 reordering 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.",
journal = "{ACM} Transactions on Mathematical Software",
volume = "30",
year = "2004",
pages = "266299",
number = "3",
url = "http://doi.acm.org/10.1145/1024074.1024076"
}
 
back

