Jacobian code generated by source transformation and vertex elimination can be as efficient as hand-coding

ABSTRACT

This article 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 five test cases, four 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 five 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.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Averick, B. M., Carter, R. G., Moré, J. J., and Xue, G.-L. 1992. The MINPACK-2 test problem collection. Preprint MCS--P153--0692, ANL/MCS--TM--150, Rev. 1, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill. See ftp://info.mcs. anl.gov/pub/MINPACK-2/tprobs/P153.ps.Z.
• 3: Bendtsen, C. and Stauning, O. 1996. FADBAD, A flexible C++ package for automatic differentiation. Tech. Rep. IMM-REP-1996-17, Technical University of Denmark, IMM, Departement of Mathematical Modeling, Lyngby.
• 4: Berz, M., Bischof, C., Corliss, G., and Griewank, A., Eds. 1996. Computational Differentiation: Techniques, Applications, and Tools. SIAM, Philadelphia, Pa.
• 5: C. H. Bischof , H. M. Bücker , B. Lang , A. Rasch , A. Vehreschild, Combining Source Transformation and Operator Overloading Techniques to Compute Derivatives for MATLAB Programs, Proceedings of the Second IEEE International Workshop on Source Code Analysis and Manipulation (SCAM'02), p.65, October 01-01, 2002
• 6: Bischof, C. H. 1991. Issues in parallel automatic differentiation. In Automatic Differentiation of Algorithms: Theory, Implementation, and Application, A. Griewank and G. F. Corliss, Eds. SIAM, Philadelphia, Pa., 100--113.
• 7: Bischof, C. H., Carle, A., Hovland, P. D., Khademi, P., and Mauer, A. 1998. ADIFOR 2.0 user's guide (Revision D). Tech. Rep., Mathematics and Computer Science Division Technical Memorandum no. 192 and Center for Research on Parallel Computation Technical Report CRPC-95516-S. See www.mcs.anl.gov/adifor.
• 8: Christian Bischof , Peyvand Khademi , Andrew Mauer , Alan Carle, Adifor 2.0: Automatic Differentiation of Fortran 77 Programs, IEEE Computational Science & Engineering, v.3 n.3, p.18-32, September 1996 [doi>10.1109/99.537089]
• 9: Bischof, C. H. and Haghighat, M. R. 1996. Hierarchical approaches to automatic differentiation. In Computational Differentiation: Techniques, Applications, and Tools, M. Berz, C. Bischof, G. Corliss, and A. Griewank, Eds. SIAM, Philadelphia, Pa., 83--94.
• 10: Bischof, C. H., Khademi, P. M., Bouaricha, A., and Carle, A. 1996b. Efficient computations of gradients and Jacobians by dynamic exploitation of sparsity in automatic differentiation. Optimiza. Meth. Softw. 7, 1--39.
• 11: C. H. Bischof , L. Roh , A. J. Mauer-Oats, ADIC: an extensible automatic differentiation tool for ANSI-C, Software—Practice & Experience, v.27 n.12, p.1427-1456, Dec. 1997 [doi>10.1002/(SICI)1097-024X(199712)27:12<1427::AID-SPE138>3.3.CO;2-H]
• 12: Thomas F. Coleman , Burton S. Garbow , Jorge J. More, Software for estimating sparse Jacobian matrices, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.329-345, Sept. 1984 [doi>10.1145/1271.1610]
• 13: Thomas F. Coleman , Arun Verma, ADMIT-1 : Automatic Differentiation and MATLAB Interface Toolbox, Cornell University, Ithaca, NY, 1998
• 14: George Corliss , Christèle Faure , Andreas Griewank , Lauren Hascoët , Uwe Naumann, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 15: I. S. Duff , A. M. Erisman , J. K. Reid, Direct methods for sparse matrices, Clarendon Press, New York, NY, 1987
• 16: Faure, C. and Papegay, Y. 1998. Odyssée User's Guide. Version 1.7. Rapport technique RT--0224, INRIA, Sophia-Antipolis, France. Sept. See www.inria.fr/RRRT/RT-0224.html, and www.inria.fr/safir/SAM/Odyssee/odyssee.html.
• 17: Forth, S. A. 2001. User guide for MAD---A Matlab automatic differentiation toolbox. Applied Mathematics and Operational Research Report AMOR 2001/5, Cranfield University (RMCS Shrivenham), Swindon, SN6 8LA, UK. June.
• 18: Forth, S. A. and Tadjouddine, M. 2003. CFD Newton solvers with EliAD, an elimination automatic differentiation tool. In Computational Fluid Dynamics 2002: Proceedings of the 2nd International Conference on Computational Fluid Dynamics, ICCFD (Sydney, Australia). S. Armfield, P. Morgan, and K. Srinivas, Eds., Springer-Verlag, New York, 134--139.
• 19: Ralf Giering , Thomas Kaminski, Recipes for adjoint code construction, ACM Transactions on Mathematical Software (TOMS), v.24 n.4, p.437-474, Dec. 1998 [doi>10.1145/293686.293695]
• 20: Goedecker, S. and Hoisie, A. 2001. Performance Optimisation of Numerically Intensive Codes. Software, Environments, Tools. SIAM, Philadelphia, Pa., ISBN 0-89871-482-3.
• 21: Andreas Griewank, Evaluating derivatives: principles and techniques of algorithmic differentiation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 22: Griewank, A. and Corliss, G. F., Eds. 1991. Automatic Differentiation of Algorithms: Theory, Implementation, and Application. SIAM, Philadelphia, Pa.
• 23: Andreas Griewank , David Juedes , Jean Utke, Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.131-167, June 1996 [doi>10.1145/229473.229474]
• 24: Griewank, A. and Reese, S. 1991. On the calculation of Jacobian matrices by the Markowitz rule. In Automatic Differentiation of Algorithms: Theory, Implementation, and Application, A. Griewank and G. F. Corliss, Eds. SIAM, Philadelphia, Pa., 126--135.
• 25: Hascoet, L., Naumann, U., and Pascual, V. 2003. TBR analysis in reverse mode automatic differentiation. In Future Generation Computer Systems. Elsevier, Amsterdam, The Netherlands.
• 26: Paul D. Hovland , Lois C. McInnes, Parallel simulation of compressible flow using automatic differentiation and PETSc, Parallel Computing, v.27 n.4, p.503-519, March 1, 2001 [doi>10.1016/S0167-8191(00)00074-0]
• 27: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 28: Markowitz, H. 1957. The elimination form of the inverse and its application. Manage. Sci. 3, 257--269.
• 29: Naumann, U. 1999. Efficient calculation of Jacobian matrices by optimized application of the chain rule to computational graphs. Ph.D. thesis, Technical University of Dresden.
• 30: Uwe Naumann, Elimination techniques for cheap Jacobians, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 31: Naumann, U. 2003. Statement-level optimality of tangent-linear and adjoint models. Argonne National Laboratory, preprint, ANL/MCS-P-1066, June.
• 32: Uwe Naumann, Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph, Mathematical Programming: Series A and B, v.99 n.3, p.399-421, April 2004 [doi>10.1007/s10107-003-0456-9]
• 33: Parr, T., Lilly, J., Wells, P., Klaren, R., Illouz, M., Mitchell, J., Stanchfield, S., Coker, J., Zukowski, M., and Flack, C. 2000. ANTLR Reference Manual. Tech. Rep., MageLang Institute's jGuru.com. January. See www.antlr.org/doc/index.html.
• 34: Pryce, J. D. and Reid, J. K. 1998. ADO1, A Fortran 90 code for automatic differentiation. Tech. Rep. RAL-TR-1998-057, Rutherford Appleton Laboratory, Chilton, Didcot, Oxfordshire, OX11 OQX, England. See ftp://matisa.cc.rl.ac.uk/pub/reports/prRAL98057.ps.gz.
• 35: Reid, J. 2003. On the stability of automatic differentiation. In preparation.
• 36: Roe, P. L. 1981. Approximate Riemann solvers, parameter vectors, and difference schemes. J. Computat. Phys. 43, 357--372.
• 37: Tadjouddine, M. 1999. La différentiation automatique. Ph.D. dissertation, Université de Nice, Sophia Antipolis, France.
• 38: M. Tadjouddine , F. Eyssette , C. Faure, Sparse Jacobian Computation in Automatic Differentiation by Static Program Analysis, Proceedings of the 5th International Symposium on Static Analysis, p.311-326, September 14-16, 1998
• 39: Mohamed Tadjouddine , Shaun A. Forth , John D. Pryce, AD tools and prospects for optimal AD in CFD flux Jacobian calculations, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 40: Tadjouddine, M., Forth, S. A., and Pryce, J. D. 2003. Hierarchical automatic differentiation by vertex elimination and source transformation. In Proceedings of Computational Science and Its Applications---ICCSA 2003. Lecture Notes in Computer Science, vol. 2. Springer-Verlag, New York, 115--124.
• 41: Mohamed Tadjouddine , Shaun A. Forth , J. D. Pryce , J. K. Reid, Performance Issues for Vertex Elimination Methods in Computing Jacobians Using Automatic Differentiation, Proceedings of the International Conference on Computational Science-Part II, p.1077-1086, April 21-24, 2002
• 42: Verma, A. 1998. ADMAT: Automatic differentiation in MATLAB using object oriented methods. In SIAM Interdisciplinary Workshop on Object Oriented Methods for Interoperability. SIAM, National Science Foundation, Yorktown Heights, N.Y., 174--183.
• 43: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Stability (and instability)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Automatic differentiation
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations
      G.1.6 Optimization
          Subjects: Least squares methods
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Algorithms, Performance

Keywords:
Jacobian, source transformation, vertex elimination