BibTeX
@ARTICLE{
         Forth2004JCG,
       ad_theotech = "Code Optimization, Data Flow Analysis, X-Country",
       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 Hand-Coding",
       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 their 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.",
       journal = "{ACM} Transactions on Mathematical Software",
       volume = "30",
       year = "2004",
       pages = "266--299",
       number = "3",
       url = "http://doi.acm.org/10.1145/1024074.1024076"
}