Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++

ABSTRACT

The C++ package ADOL-C described here facilitates the evaluation of first and higher derivatives of vector functions that are defined by computer programs written in C or C++. The resulting derivative evaluation routines may be called from C/C++, Fortran, or any other language that can be linked with C. The numerical values of derivative vectors are obtained free of truncation errors at a small multiple of the run-time and randomly accessed memory of the given function evaluation program. Derivative matrices are obtained by columns or rows. For solution curves defined by ordinary differential equations, special routines are provided that evaluate the Taylor coefficient vectors and their Jacobians with respect to the current state vector. The derivative calculations involve a possibly substantial (but always predictable) amount of data that are accessed strictly sequentially and are therefore automatically paged out to external files.

REFERENCES

• 1: AVERICK, B., MORE, J., BISCHOF, C., CARLE, A., AND GRIEWANK, A. 1993. Computing large sparse Jacobian matrices using automatic differentiation. Preprint MCS-P348-0193, Argonne National Laboratory, Argonne, Ill.
• 2: BISCHOF, C. H., CARLE, A., CORLISS, G. F. GRIEWANK, A., AND HOVLAND P. 1992. ADIFOR: Generating derivative codes from Fortran programs. Sci. Program. 1, 1, 1-29.
• 3: BRENAN, K. E., CAMPBELL, S. L., AND PETZOLD, L. R. 1989. Numerical Solution of Initial Value Problems in Differential-Algebraic Equations. Elsevier (North-Holland), Amsterdam.
• 4: CACUCI, D. G. 1981a. Sensitivity theory for nonlinear systems. I. Nonlinear functional analysis approach. J. Math. Phys. 22, 12, 2794-2802.
• 5: CACUCI, D.G. 1981b. Sensitivity theory for nonlinear systems. II. Extension to additional classes of responses. J. Math. Phys. 22, 12, 2803-2812.
• 6: CHRISTIANSON, B. 1992. Reverse accumulation and accurate rounding error estimates for Taylor series. Opt. Methods Softw. 1, 81-94.
• 7: GRIEWANK, A. 1990. Direct calculation of Newton steps without accumulating Jacobians. In Large-Scale Numerical Optimization, T. F. Coleman and Yuying Li, Eds. SIAM, Philadelphia, Pa., 115-137.
• 8: GRIEWANK, A. 1992. Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation. Opt. Methods Softw. 1, 35-54.
• 9: 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.
• 10: E. Hairer , S. P. Nørsett , G. Wanner, Solving ordinary differential equations I (2nd revised. ed.): nonstiff problems, Springer-Verlag New York, Inc., New York, NY, 1993
• 11: HORWEDEL, J. E., WORLE~, B. A., OBLOW, E. M., AND PIN, F. G. 1988. GRESS version 1.0 users manual. Tech. Memo. ORNL/TM 10835, Oak Ridge National Laboratory, Oak Ridge, Tenn.
• 12: Gershon Kedem, Automatic Differentiation of Computer Programs, ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.150-165, June 1980 [doi>10.1145/355887.355890]
• 13: KUBOTA, K. 1991. PADRE2, a FORTRAN precompiler yielding error estimates and second derivatives. In Automatic Differentiation of Algorithms: Theory, Implementation, and Application, A. Griewank and G. F. Corliss, Eds. SIAM, Philadelphia, Pa, 251-262.
• 14: LINNAINMAA, S. 1976. Taylor expansion of the accumulated rounding error. BIT (Nordisk Tidskrift for Informationsbehandling) 16, 1, 146-160.
• 15: OSTROVSKII, G. M., VOLIN, V. M., AND BORISOV, W. W. 1971. Ober die Berechnung von Ableitungen. Wissenschaftliche Zeitschrift der Technischen Hochschule far Chemie, Leuna- Merseburg 13, 4, 382-384.
• 16: RALL, L.B. 1981. Automatic Differentiation: Techniques and Applications. Lecture Notes in Computer Science, vol. 120. Springer-Verlag, Berlin.
• 17: L B. Rall, Differentiation and generation of taylor coefficients in PASCAL-SC, Proc. of the symposium on A new approach to scientific computation, p.291-309, December 1983, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, United States
• 18: Bert Speelpenning, Compiling fast partial derivatives of functions given by algorithms, 1980
• 19: TALAGRAND, O. AND COURTIER, P. 1987. Variational assimilation of meteorological observations with the adjoint vorticity equation--Part I. Theory. Q. J. R. Meteorol. Soc. 113, 1311-1328.
• 20: R. E. Wengert, A simple automatic derivative evaluation program, Communications of the ACM, v.7 n.8, p.463-464, Aug. 1964 [doi>10.1145/355586.364791]
• 21: WERBOS, P. 1974. Beyond regression: New tools for prediction and analysis in the behavioral sciences. Ph.D thesis, Committee on Applied Mathematics, Harvard Univ., Cambridge, Mass. Nov.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Performance

Keywords:
Hessians, Taylor coefficients, automatic differentiation, chain rule, forward mode, gradients, overloading, reverse mode