×

On the implementation of automatic differentiation tools. (English) Zbl 1168.65324

Summary: Automatic differentiation is a semantic transformation that applies the rules of differential calculus to source code. It thus transforms a computer program that computes a mathematical function into a program that computes the function and its derivatives. Derivatives play an important role in a wide variety of scientific computing applications, including numerical optimization, solution of nonlinear equations, sensitivity analysis, and nonlinear inverse problems. We describe the forward and reverse modes of automatic differentiation and provide a survey of implementation strategies. We describe some of the challenges in the implementation of automatic differentiation tools, with a focus on tools based on source transformation. We conclude with an overview of current research and future opportunities.

MSC:

65D25 Numerical differentiation
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Abate, J., Bischof, C., Carle, A., Roh, L.: Algorithms and design for a second-order automatic differentiation module. In: Proc. Int. Symposium on Symbolic and Algebraic Computing (ISSAC) ’97, New York, pp. 149–155. Association of Computing Machinery (1997) · Zbl 0923.68068
[2] Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques and Tools. Addison–Wesley, Reading (1986) · Zbl 1155.68020
[3] Allen, R., Kennedy, K.: Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann, San Mateo (2002)
[4] Amarasinghe, S.P., Anderson, J.M., Lam, M.S., Tseng, C.W.: The SUIF compiler for scalable parallel machine. In: Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing (1995) · Zbl 0960.68544
[5] Aubert, P., Di Césaré, N.: Expression templates and forward mode automatic differentiation. In [26], Chap. 37, pp. 311–315 (2001)
[6] Bagge, O.S., Kalleberg, K.T., Haveraaen, M., Visser, E.: Design of the CodeBoost transformation system for domain-specific optimisation of C++ programs. In: Binkley, D., Tonella, P. (eds.): Third International Workshop on Source Code Analysis and Manipulation (SCAM 2003). IEEE Computer Society Press, Amsterdam (2003, to appear)
[7] Bartholomew-Biggs, M.: OPFAD–A users guide to the OPtima forward automatic differentiation tool. Technical report, Numerical Optimization Centre, University of Hertfordsshire (1995)
[8] Bartholomew-Biggs, M.C., Brown, S., Christianson, B., Dixon, L.C.W.: The efficient calculation of gradients, Jacobians and Hessians. Technical Report NOC TR301, The Numerical Optimisation Center, University of Hertfordshire, Hatfield, U.K. (1995)
[9] Barton, J.J., Nackman, L.R.: Automatic differentiation. C++ Rep. 8(2), 61–63 (1996)
[10] Beda, L.M., Korolev, L.N., Sukkikh, N.V., Frolova, T.S.: Programs for automatic differentiation for the machine BESM. Technical Report, Institute for Precise Mechanics and Computation Techniques, Academy of Science, Moscow, USSR (1959) (In Russian)
[11] Bell, B.M.: CppAD User Manual. Available at http://www.seanet.com/\(\sim\)bradbell/CppAD/ (2003)
[12] Bendtsen, C., Stauning, O.: FADBAD, a flexible C++ package for automatic differentiation. Technical Report IMM-REP-1996-17, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark (1996)
[13] Berz, M., Bischof, C., Corliss, G., Griewank, A. (eds.): Computational Differentiation: Techniques, Applications, and Tools. SIAM, Philadelphia (1996) · Zbl 0857.00033
[14] Binkley, D.W., Gallagher, K.B.: Program slicing. Adv. Comput. 43, 1–50 (1996)
[15] Bischof, C., Roh, L.: The automatic differentiation intermediate form (AIF). Unpublished Information (1996)
[16] Bischof, C., Carle, A., Corliss, G., Griewank, A., Hovland, P.: ADIFOR: Generating derivative codes from Fortran programs. Sci. Program. 1(1), 11–29 (1992)
[17] Bischof, C., Carle, A., Khademi, P., Mauer, A.: ADIFOR 2.0: Automatic differentiation of Fortran 77 programs. IEEE Comput. Sci. Eng. 3(3), 18–32 (1996) · Zbl 05092146
[18] Bischof, C., Roh, L., Mauer, A.: ADIC–An extensible automatic differentiation tool for ANSI-C. Softw. Pract. Exp. 27(12), 1427–1456 (1997) · Zbl 05471765
[19] Bischof, C.H., Bücker, H.M., Lang, B., Rasch, A.: An interactive environment for supporting the paradigm shift from simulation to optimization. In: 4th Workshop on Parallel/High-Performance OO Scientific Computing (POOSC’01) 14 October 2001, at the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA’01) 14–18 October, Tampa Bay, FL (2001, to appear)
[20] Bischof, C.H., Bücker, H.M., Lang, B., Rasch, A., Vehreschild, A.: Combining source transformation and operator overloading techniques to compute derivatives for MATLAB programs. Preprint RWTH-CS-SC-02-04, Institute for Scientific Computing, Aachen University of Technology (2002)
[21] Brooke, A., Kendrick, D., Meeraus, A.: GAMS: A User’s Guide. The Scientific Press, South San Francisco (1988)
[22] Brown, S.: OPRAD–A users guide to the OPtima reverse automatic differentiation tool. Technical report, Numerical Optimization Centre, University of Hertfordsshire (1995)
[23] Christianson, B., Dixon, L.C.W., Brown, S.: Sharing storage using dirty vectors. In [13], pp. 107–115 · Zbl 1076.65545
[24] Christianson, D.B.: Automatic Hessians by reverse accumulation in ada. IMA J. Numer. Anal. (1991) Presented at SIAM Workshop on Automatic Differentiation of Algorithms, Breckenridge, CO, January 1991
[25] Coleman, T.F., Verma, A.: ADMIT-1: Automatic differentiation and MATLAB interface toolbox. ACM Trans. Math. Softw. 26(1), 150–175 (2000) · Zbl 1137.65329
[26] Corliss, G., Faure, C., Griewank, A., Hascoët, L., Naumann, U. (eds.): Automatic Differentiation: From Simulation to Optimization. Computer and Information Science Springer, New York (2001)
[27] Edison Design Group: EDG C++ Front End (2003). http://www.edg.com/cpp.html
[28] Faure, C.: Adjoining strategies for multi-layered programs. Optim. Methods Softw. (2001, to appear). Also appeared as INRIA Rapport de recherche no. 3781, BP 105-78153 Le Chesnay Cedex, France (1999)
[29] Faure, C., Naumann, U.: Minimizing the tape size. In [26], Chap. 34, pp. 293–298 (2001)
[30] Forth, S.: An efficient implementation of AD in MATLAB. Presentation at Joint University of Hertfordshire/Cranfield University (RMCS Shrivenham) Automatic Differentiation Symposium (2001). Available at http://www.rmcs.cranfield.ac.uk/esd/amor/workshop/alldatastore/ADDAYmay01forth.pdf
[31] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. The Scientific Press, South San Francisco (1993) · Zbl 0701.90062
[32] Frazier, Z.: PyAD User manual. Available at http://students.washington.edu/zfrazier/projects/pyad/pyad-doc/ (2003)
[33] Giering, R., Kaminski, T.: Recipes for adjoint code construction. ACM TOMS 24(4), 437–474 (1998) · Zbl 0934.65027
[34] Giering, R., Kaminski, T.: Applying TAF to generate efficient derivative code of Fortran 77-95 programs. In: Proceedings of GAMM 2002, Augsburg, Germany (2002)
[35] Griewank, A.: On automatic differentiation. In: Mathematical Programming: Recent Developments and Applications, pp. 83–108. Kluwer Academic, Amsterdam (1989) · Zbl 0696.65015
[36] Griewank, A.: Personal communication (1998)
[37] Griewank, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Philadelphia (2000) · Zbl 0958.65028
[38] Griewank, A.: Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation. Optim. Methods Softw. 1, 35–54 (1992)
[39] Griewank, A., Corliss, G.F.: Automatic Differentiation of Algorithms: Theory, Implementation, and Application. SIAM, Philadelphia (1991) · Zbl 0747.00030
[40] Griewank, A., Reese, S.: On the calculation of Jacobian matrices by the Markowitz rule. In [39], pp. 126–135 (1991) · Zbl 0782.65027
[41] Griewank, A., Juedes, D., Utke, J.: ADOL-C, a package for the automatic differentiation of algorithms written in C/C++. ACM Trans. Math. Softw. 22(2), 131–167 (1996) · Zbl 0884.65015
[42] Grimm, J., Pottier, L., Rostaing-Schmidt, N.: Optimal time and minimum space-time product for reversing a certain class of programs. In [13], pp. 95–106 (1996) · Zbl 0866.65016
[43] Guyer, S.Z., Lin, C.: Optimizing the use of high performance software libraries. Lecture Notes in Computer Science, vol. 2017, pp. 227–243. Springer, Berlin (2001) · Zbl 1014.68775
[44] Hill, D.R., Rich, L.C.: Automatic differentiation in MATLAB. Appl. Numer. Math. 9, 33–43 (1992) · Zbl 0753.65017
[45] Hinkins, R.L.: Parallel computation of automatic differentiation applied to magnetic field calculations. Master’s thesis, University of California, Berkeley (1994)
[46] Hinsen, K.: Scientific python collection. Module Scientific. Functions. Derivatives (2003). Available at http://starship.python.net/\(\sim\)hinsen/ScientificPython/ · Zbl 1054.68030
[47] Hovland, P.D., Naumann, U., Norris, B.: An XML-based platform for semantic transformation of numerical programs. Preprint ANL/MCS-P950-0402, Mathematics and Computer Science Division, Argonne National Laboratory. Proceedings of Software Engineering and Applications (SEA 2002) (2002, to appear)
[48] Huss, R.E.: An ADA library for automatic evaluation of derivatives. Appl. Math. Comput. 35(2), 103–123 (1990) · Zbl 0714.65020
[49] Jerrell, M.: Automatic differentiation using almost any language. ACM SIGNUM Newsl. pp. 2–9 (1989)
[50] Juedes, D.W.: A taxonomy of automatic differentiation tools. In [39], pp. 315–329 (1991) · Zbl 0782.65029
[51] Kahrimanian, H.G.: Analytical differentiation by a digital computer. Master’s thesis, Temple University (1953)
[52] Kalman, D., Lindell, R.: Automatic differentiation in astrodynamical modeling. In [39], pp. 228–243 (1991)
[53] Karczmarczuk, J.: Functional differentiation of computer programs. J. HOSC 14, 35–57 (2001) · Zbl 0967.68174
[54] Kennedy, K., Broom, B., Cooper, K., Dongarra, J., Fowler, R., Gannon, D., Johnsson, L., Mellor-Crummey, J., Torczon, L.: Telescoping languages: A strategy for automatic generation of scientific problem-solving systems from annotated libraries. J. Parallel Distrib. Comput. 61(12), 1803–1826 (2001) · Zbl 1006.68025
[55] Korelc, J.: Hybrid system for multi-language and multi-environment generation of numerical codes. In: Proceedings of the 2001 International Symposium on Symbolic and algebraic computation, pp. 209–216. ACM Press (2001) · Zbl 1356.65277
[56] Lawson, C.L.: Computing derivatives using W-arithmetic and U-arithmetic. Internal computing memorandum CM–286, Jet Propulsion Laboratory, Pasadena (1971)
[57] Lesk, A.M.: Dynamic computation of derivatives. Commun. ACM 10(9), 571–572 (1967) · Zbl 0147.36103
[58] Maany, Z.: Ada automatic differentiation package for the optimization of functions of many variables. Technical Report NOC TR209, The Numerical Optimisation Center, Hatfield Polytechnic, Hatfield, UK (1989)
[59] Martins, J.R.R.A., Kroo, I.M., Alonso, J.J.: An automated method for sensitivity analysis using complex variables. In: Proceedings of the 38th Aerospace Sciences Meeting, Reno, NV (2000)
[60] Martins, J.R.R.A., Sturdza, P., Alonso, J.J.: The connection between the complex-step derivative approximation and algorithmic differentiation. In: Proceedings of the 39th Aerospace Sciences Meeting, Reno, NV (2001). Complexify.h and derivify.h available at http://mdolab.utias.utoronto.ca/c++.html
[61] Michelotti, L.: MXYZPTLK: A C++ Hacker’s implementation of automatic differentiation. In [39], pp. 218–227 (1991). Software available at http://www.netlib.org/c++/mxyzptlk/ · Zbl 0782.65032
[62] Monagan, M., Rodoni, R.R.: An implementation of the forward and reverse mode of automatic differentiation in maple. In: Berz, M., Bischof, C., Corliss, G., Griewank, A. (eds.) Computational Differentiation: Techniques, Applications, and Tools, pp. 353–362. SIAM, Philadelphia (1996) · Zbl 1076.65500
[63] Muchnick, S.S.: Advanced Compiler Design and Implementation. Morgan Kaufmann, San Mateo (1997)
[64] NAG-AD: Differentiation enabled Fortran compiler technology (2003). http://www.nag.co.uk/nagware/research/ad_overview.asp
[65] Naumann, U.: Reducing the memory requirement in reverse mode automatic differentiation by solving TBR flow equations. In: Sloot, P.M.A., Tan, C.J.K., Dongarra, J.J. (eds.) Proceedings of the International Conference on Computational Science, Part II, Amsterdam, The Netherlands, April 21–24, 2002. Lecture Notes in Computer Science, vol. 2330, pp. 1039–1048. Springer, Berlin (2002) · Zbl 1062.65024
[66] Naumann, U.: Statement level optimality of tangent-linear and adjoint models. Preprint ANL-MCS/P1066-0603, Argonne National Laboratory (2003)
[67] Naumann, U., Gottschling, P.: Simulated annealing for optimal pivot selection in Jacobian accumulation. In: Albrecht, A. (ed.): Stochastic Algorithms, Foundations and Applications–SAGA’03. Berlin, Springer (2003, to appear). See also http://angellib.sourceforge.net/ · Zbl 1161.90473
[68] Neidinger, R.D.: Automatic differentiation and APL. Coll. Math. J. 20(3), 238–251 (1989)
[69] Nilsson, H.: Functional automatic differentiation with Dirac impulses. ACM SIGPLAN Not. 38(9), 153–164 (2003) · Zbl 1315.68057
[70] Nolan, J.F.: Analytical differentiation on a digital computer. Master’s thesis, Massachusetts Institute of Technology (1953)
[71] Pryce, J.D., Reid, J.K.: ADO1, a Fortran 90 code for automatic differentiation. Technical Report RAL-TR-1998-057, Rutherford Appleton Laboratory, Chilton, Didcot, Oxfordshire, OX11 OQX, England (1998)
[72] Quinlan, D.: ROSE: Compiler support for object-oriented frameworks. Parallel Process. Lett. 10(2/3), 215 (2000)
[73] Reps, T., Rosay, G.: Precise interprocedural chopping. In: Kaiser, G.E. (ed.) SIGSOFT’95: Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, pp. 41–52. ACM Press (1995)
[74] Restrepo, J.M., Leaf, G.K., Griewank, A.: Circumventing storage limitations in variational data assimilation. SIAM J. Sci. Comput. 19, 1586–1605 (1998) · Zbl 0956.76078
[75] Rostaing, N., Dalmas, S., Galligo, A.: Automatic differentiation in Odyssee. Tellus 45a(5), 558–568 (1993)
[76] Rote, G.: Path problems in graphs. In: Tinhofer, G., Mayr, E., Noltemeier, H., M.M.S. in cooperation with Albrecht, R. (eds.) Computational Graphs Theory, Springer-Verlag Computing Supplementum 7. Springer (1990) · Zbl 0699.68088
[77] SGI: WHIRL intermediate language specification (1999). Available at http://open64.sourceforge.net/documentation.html
[78] Stamatiadis, S., Prosmiti, R., Farantos, S.C.: auto_deriv: Tool for automatic differentiation of a fortran code. Comput. Phys. Commun. 127(2&3), 343–355 (2000). Catalog number: ADLS · Zbl 0960.65026
[79] Tadjouddine, M., Forth, S.A., Pryce, J.D.: Hierarchicalal automatic differentiation by vertex elimination and source transformation. In: Kumar, V., Gavrilova, M.L., Tan, C.J.K. (eds.) Proceedings of the International Conference on Computational Science and its Applications, Part II, Montreal, Canada, May 18–21, 2003. Lecture Notes in Computer Science, vol. 2668, pp. 95–104. Springer, Berlin (2003)
[80] TAPENADE: TAPENADE tutorial (2002). http://www-sop.inria.fr/tropics/tapenade/tutorial.html
[81] Tsukanov, I.M.H.: Data structure and algorithms for fast automatic differentiation. Int. J. Numer. Methods Eng. 56(13), 1949–1972 (2003) · Zbl 1031.65035
[82] Veldhuizen, T.: Expression templates. C++ Rep. 7(5), 26–31 (1995)
[83] Wengert, R.E.: A simple automatic derivative evaluation program. Commun. ACM 7(8), 463–464 (1964) · Zbl 0131.34602
[84] Wilkins, R.D.: Investigation of a new analytic model for numerical derivative evaluation. Commun. ACM 7(8), 465–471 (1964) · Zbl 0131.34603
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.