Algorithm 746: PCOMP—a Fortran code for automatic differentiation

ABSTRACT

Automatic differentiation is an interesting and important tool for all numerical algorithms that require derivatives, e.g., in nonlinear programming, optimal control, parameter estimation, and differential equations. The basic idea is to avoid not only numerical approximations, which are expensive with respect to CPU time and contain round-off errors, but also hand-coded differentiation. This article introduces the forward and backward accumulation methods and describes the numerical implementation of a computer code with the name PCOMP. The main intention of the approach used is to provide a flexible and portable Fortran code for practical applications. The underlying language is described in terms of a formal grammar and is a subset of Fortran with a few extensions. Besides a parser that generates an intermediate code and that can be executed independently from the evaluation routines, there are other subroutines for the direct computation of function and gradient values, which can be called directly from a user program. On the other hand, it is possible to generate a Fortran code for function and gradient evaluation that can be compiled and linked separately.

REFERENCES

• 1: CHAR, B. W., GEDDES, K. O., GONNET, G. H., MONEGAN, M. B., AND WATT, S.M. 1988. MAPLE Reference Manual, 5th ed. Symbolic Computing Group, Univ. of Waterloo, Waterloo, Canada.
• 2: DOBMANN, M. 1993. Erweiterungen zum Automatischen Dlfferenzieren, Diplomarbeit, Mathematisehes Institut, Univ. Bayreuth, Bayreuth, Germany.
• 3: FISCHER, H. 1991. Special problems in automatic differentiation. In Automatic Differentiation of Algorithms: Theory, Implementation and Application, Proceedings of a Workshop, A. Griewank and G. Corliss, Eds. SIAM, Philadelphia, Pa.
• 4: GRIEWANK, A. 1989. On automatic differentiation. In Mathematical Programming: Recent Developments and Applications, M. Iri and K. Tanabe, Eds. Kluwer Academic, Boston, Mass., 83-107.
• 5: GRIEWANK. A. AND CORLISS. G.. Eds. 1991. Automatic D~fferentiation of Algomthms: Theory, Implementatwn and Application, Procee&ngs of a Workshop (Breckenridge, Colo.). SIAM, Philadelphia, Pa.
• 6: GRmWANK, A., JUEDES, D., AND SRINIVASAN, J. 1991. ADOL-C: A package for the automatic differentiation of algorithms written in C/C ++. Preprint MCS-P180-1190, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill.
• 7: HILLSTROM, K.E. 1985. Users guide for JAKEF. Tech. Mem. ANL/MCS-TM-16, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill.
• 8: Willi Hock , K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag New York, Inc., Secaucus, NJ, 1981
• 9: IDNANZ, A. 1987. NLPSOLVER: User Guide 3i Corp, Park Ridge, N.Y.
• 10: JUEDES, D. W 1991. A taxonomy of automatic differentiation tools. In Automatzc D~fferent~ation of Algorithms: Theory, Implementation and Apphcat~on, A. Griewank and G. Corhss, Eds. SIAM, Philadelphia, Pa.
• 11: H Kagiwada, Numerical derivatives and nonlinear analysis, Plenum Press, New York, NY, 1986
• 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: KELEVEDZHIEV, E. AND KIROV, N. 1989. Interactive optimization systems. Working Paper, IIASA, Laxenburg, Austria.
• 14: I~M, K. V., NESTEROV, I. E., SKOKOV, V. A., AND C~ER~SSKn, B. V. 1984. An efficient algorithm for computing derivatives and extremal problems. Ekonom~ka z matematzcheskze metody 20, 2, 309-318. In English.
• 15: KNEPPE, G. 1990. MBB-LAGRANGE: Structural optimization system for space and aircraft structures. Rep. S-PUB-0406, MBB, Munich, Germany
• 16: KREDLER, C., GREINER, M., KOLBL, A., AND PURSCHE, T. 1990. User's guide for PADMOS. Inst. fur Angewandte Mathematik und Statistik, Univ. Munchen, Mumch, Germany.
• 17: LIEPELT, M. 1990. AutomattschesDlfferenzieren. Dlplomarbeit, Mathematlsches Institut, Univ. Bayreuth, Bayreuth, Germany.
• 18: RALL, L.B. 1981. Automatic Differentiatzon--Techn~ques and Applications. Lecture Notes m Computer Science, vol. 120. Springer, New York.
• 19: ROSENBROCK, H.H. 1969. An automatic method for finding the greatest and least value of a function. Comput. J. 3, 175 183.
• 20: SCHITTKOWSKI, K. 1987a. EMP: An expert system for mathematical programming. Rep. Mathematisches Institut, Univ. Bayreuth, Bayreuth, Germany.
• 21: Klaus Schittkowski, More test examples for nonlinear programming codes, Springer-Verlag New York, Inc., New York, NY, 1987

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.2 Automatic Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Languages

Keywords:
automatic differentiation, forward accumulation, reverse accumulation