The complex-step derivative approximation

ABSTRACT

The complex-step derivative approximation and its application to numerical algorithms are presented. Improvements to the basic method are suggested that further increase its accuracy and robustness and unveil the connection to algorithmic differentiation theory. A general procedure for the implementation of the complex-step method is described in detail and a script is developed that automates its implementation. Automatic implementations of the complex-step method for Fortran and C/C++ are presented and compared to existing algorithmic differentiation tools. The complex-step method is tested in two large multidisciplinary solvers and the resulting sensitivities are compared to results given by finite differences. The resulting sensitivities are shown to be as accurate as the analyses. Accuracy, robustness, ease of implementation and maintainability make these complex-step derivative approximation tools very attractive options for sensitivity analysis.

REFERENCES

• 1: Anderson, W. K., Newman, J. C., Whitfield, D. L., and Nielsen, E. J. 1999. Sensitivity analysis for the Navier--Stokes equations on unstructured meshes using complex variables. AIAA Paper 99--3294.
• 2: Bartholomew-Biggs, M. 1995. OPFAD---A Users Guide to the OPtima Forward Automatic Differentiation Tool. Numerical Optimization Centre, University of Hertfordsshire.
• 3: Thomas Beck, Automatic differentiation of iterative processes, Journal of Computational and Applied Mathematics, v.50 n.1-3, p.109-118, May 20, 1994
• 4: Thomas Beck , Herbert Fischer, The if-problem in automatic differentiation, Journal of Computational and Applied Mathematics, v.50 n.1-3, p.119-131, May 20, 1994
• 5: Bendtsen, C. and Stauning, O. 1996. FADBAD, A flexible C++ package for automatic differentiation---using the forward and backward methods. Tech. Rep. IMM-REP-1996-17, Technical University of Denmark, DK-2800 Lyngby, Denmark.
• 6: Berz, M. 1987. The differential algebra FORTRAN precompiler DAFOR. Tech. Rep. AT--3: TN--87--32, Los Alamos National Laboratory, Los Alamos, N.M.
• 7: Bischof, C., Carle, A., Corliss, G., Grienwank, A., and Hoveland, P. 1992. ADIFOR: Generating derivative codes from Fortran programs. Sci. Prog. 1, 1, 11--29.
• 8: Bischof, C., Corliss, G., and Grienwank, A. 1991. ADIFOR exception handling. Tech. Rep. MCS-TM-159, Argonne Technical Memorandum.
• 9: 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]
• 10: Brown, S. 1995. OPRAD---A Users Guide to the OPtima Reverse Automatic Differentiation Tool. Numerical Optimization Centre, University of Hertfordsshire.
• 11: 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
• 12: Faure, C. and Papegay, Y. 1997. Odyssée Version 1.6. The Language Reference Manual. INRIA. Rapport Technique 211.
• 13: Giering, R. 1997. Tangent Linear and Adjoint Model Compiler Users Manual. Max-Planck Institut für Meteorologie.
• 14: Gill, P. E., Murray, W., and Wright, M. H. 1981. Practical Optimization, Chapter 2, pp. 11--12. Academic Press, San Diego, Calif.
• 15: Griewank, A. 2000. Evaluating Derivatives. SIAM, Philadelphia, Pa.
• 16: Griewank, A., Bischof, C., Corliss, G., Carle, A., and Williamson, K. 1993. Derivative convergence for iterative equation solvers. Optim. Meth. Softw. 2, 321--355.
• 17: 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]
• 18: Horwedel, J. E. 1991. GRESS Version 2.0 User's Manual. ORNL. TM-11951.
• 19: Kubota, K. 1996. PADRE2---FORTRAN Precompiler for Automatic Differentiation and Estimates of Rounding Errors. SIAM, Philadelphia, Pa., pp. 367--374.
• 20: Mark Lutz, Programming python, O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 21: J. N. Lyness, Numerical algorithms based on the theory of complex variable, Proceedings of the 1967 22nd national conference, p.125-133, January 1967, Washington, D.C., United States [doi>10.1145/800196.805983]
• 22: Lyness, J. N. and Moler, C. B. 1967. Numerical differentiation of analytic functions. SIAM J. Numer. Anal. 4, 2 (June), 202--210.
• 23: Martins, J. R. R. A. 2002. A Coupled-Adjoint Method for High-Fidelity Aero-Structural Optimization. Ph.D. dissertation. Stanford University, Stanford, CA 94305.
• 24: Martins, J. R. R. A. 2003. A Guide to the Complex-Step Derivative Approximation. http://mdolab.utias.utoronto.ca.
• 25: Martins, J. R. R. A., Alonso, J. J., and Reuther, J. J. 2002. Complete configuration aero-structural optimization using a coupled sensitivity analysis method. AIAA Paper 2002-5402 (Sept.).
• 26: Martins, J. R. R. A., Kroo, I. M., and Alonso, J. J. 2000. An automated method for sensitivity analysis using complex variables. AIAA Paper 2000-0689 (Jan.).
• 27: Martins, J. R. R. A., Sturdza, P., and Alonso, J. J. 2001. The connection between the complex-step derivative approximation and algorithmic differentiation. AIAA Paper 2001-0921 (Jan.).
• 28: Newman, J. C., Anderson, W. K., and Whitfield, L., D. 1998. Multidisciplinary sensitivity derivatives using complex variables. Tech. Rep. MSSU-COE-ERC-98-08 (July), Computational Fluid Dynamics Laboratory.
• 29: Olver, F. W. J. 1983. Error Analysis of Complex Arithmetic. Reidel, Dordrecht, Holland, pp. 279--292.
• 30: Pryce, J. D. and Reid, J. K. 1998. AD01, A Fortran 90 code for automatic differentiation. Report RAL-TR-1998-057, Rutherford Appleton Laboratory, Chilton, Didcot, Oxfordshire, OX11 OQX, U.K.
• 31: Reuther, J., Alonso, J. J., Jameson, A., Rimlinger, M., and Saunders, D. 1999a. Constrained multipoint aerodynamic shape optimization using an adjoint formulation and parallel computers: Part I. J. Aircraft 36, 1, 51--60.
• 32: Reuther, J., Alonso, J. J., Martins, J. R. R. A., and Smith, S. C. 1999b. A coupled aero-structural optimization method for complete aircraft configurations. AIAA Paper 99--0187.
• 33: Reuther, J., Alonso, J. J., Vassberg, J. C., Jameson, A., and Martinelli, L. 1997. An efficient multiblock method for aerodynamic analysis and design on distributed memory systems. AIAA Paper 97--1893 (June).
• 34: Rhodin, A. 1997. IMAS---Integrated Modeling and Analysis System for the solution of optimal control problems. Comput. Phys. Commun. 107 (Dec.), 21--38.
• 35: Shiriaev, D. 1996. ADOL--F automatic differentiation of Fortran codes. In Computational Differentiation: Techniques, Applications, and Tools, M. Berz, C. H. Bischof, G. F. Corliss, and A. Griewank, Eds., SIAM, Philadelphia, Pa., pp. 375--384.
• 36: William Squire , George Trapp, Using Complex Variables to Estimate Derivatives of Real Functions, SIAM Review, v.40 n.1, p.110-112, March 1998 [doi>10.1137/S003614459631241X]
• 37: Sturdza, P., Manning, V. M., Kroo, I. M., and Tracy, R. R. 1999. Boundary layer calculations for preliminary design of wings in supersonic flow. AIAA Paper 99--3104 (June).
• 38: Yao, J., Alonso, J. J., Jameson, A., and Liu, F. 2001. Development and validation of a massively parallel flow solver for turbomachinery flow. J. Prop. Power 17, 3 (June), 659--668.

INDEX TERMS

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

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

General Terms:
Algorithms, Performance

Keywords:
Automatic differentiation, complex-step derivative approximation, forward mode, gradients, overloading, sensitivities