×

On the discrete adjoints of adaptive time stepping algorithms. (English) Zbl 1177.65098

Summary: We investigate the behavior of adaptive time stepping numerical algorithms under the reverse mode of automatic differentiation (AD). By differentiating the time step controller and the error estimator of the original algorithm, reverse mode AD generates spurious adjoint derivatives of the time steps. The resulting discrete adjoint models become inconsistent with the adjoint ordinary differential equation, and yield incorrect derivatives. To regain consistency, one has to cancel out the contributions of the non-physical derivatives in the discrete adjoint model.
We demonstrate that the discrete adjoint models of one-step, explicit adaptive algorithms, such as the Runge-Kutta schemes, can be made consistent with their continuous counterparts using simple code modifications. Furthermore, we extend the analysis to cover second order adjoint models derived through an extra forward mode differentiation of the discrete adjoint code. Several numerical examples support the mathematical derivations.

MSC:

65L05 Numerical methods for initial value problems involving ordinary differential equations
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
34A34 Nonlinear ordinary differential equations and systems
65L50 Mesh generation, refinement, and adaptive methods for ordinary differential equations
65L20 Stability and convergence of numerical methods for ordinary differential equations
65L70 Error bounds for numerical methods for ordinary differential equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Griewank, A.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation (2008), SIAM: SIAM Philadelphia, PA, USA · Zbl 1159.65026
[2] Griewank, A.; Juedes, D.; Utke, J., Algorithm 755: ADOL-C: A package for the automatic differentiation of algorithms written in C/C++, ACM Transactions on Mathematical Software, 22, 2, 131-167 (1996) · Zbl 0884.65015
[3] Coleman, T. F.; Verma, A., ADMIT-1: Automatic differentiation and MATLAB interface toolbox, ACM Transactions on Mathematical Software, 26, 1, 150-175 (2000) · Zbl 1137.65329
[4] Bischof, C. H.; Roh, L.; Mauer-Oats, A. J., ADIC: An extensible automatic differentiation tool for ANSI-C, Software: Practice and Experience, 27, 12, 1427-1456 (1997)
[5] C. H. Bischof, A. Carle, P. M. Khademi, A. Mauer, The ADIFOR 2.0 system for the automatic differentiation of Fortran 77 programs, Tech. Rep. MCS-P481-1194, Argonne, IL, USA, 1994; C. H. Bischof, A. Carle, P. M. Khademi, A. Mauer, The ADIFOR 2.0 system for the automatic differentiation of Fortran 77 programs, Tech. Rep. MCS-P481-1194, Argonne, IL, USA, 1994
[6] Giering, R.; Kaminski, T., Applying TAF to generate efficient derivative code of Fortran 77-95 programs, Proceedings in Applied Mathematics and Mechanics, 2, 1, 54-57 (2003)
[7] R. Giering, Tangent linear and Adjoint Model Compiler, Users manual 1.4, 1999; R. Giering, Tangent linear and Adjoint Model Compiler, Users manual 1.4, 1999
[8] L. Hascöet, V. Pascual, TAPENADE 2.1 User’s guide, Tech. Rep. 0300, INRIA, Sophia Antipolis, France, 2004; L. Hascöet, V. Pascual, TAPENADE 2.1 User’s guide, Tech. Rep. 0300, INRIA, Sophia Antipolis, France, 2004
[9] Beck, T., Automatic differentiation of iterative processes, (ICCAM’92: Proceedings of the Fifth International Conference on Computational and Applied Mathematics (1994), Elsevier Science Publishers B.V.: Elsevier Science Publishers B.V. Amsterdam, The Netherlands) · Zbl 0806.65012
[10] Griewank, A.; Bischof, C. H.; Corliss, G. F.; Carle, A.; Williamson, K., Derivative convergence for iterative equation solvers, Optimization Methods and Software, 2, 321-355 (1993)
[11] Hager, W. W., Runge-Kutta methods in optimal control and the transformed adjoint system, Numerische Mathematik, 87, 2, 247-282 (2000) · Zbl 0991.49020
[12] Walther, A., Automatic differentiation of explicit Runge-Kutta methods for optimal control, Computational Optimization and Applications, 36, 1, 83-108 (2007) · Zbl 1278.49037
[13] Sandu, A., On the properties of Runge-Kutta discrete adjoints, (International Conference on Computational Science, vol. 4 (2006)) · Zbl 1157.65421
[14] Eberhard, P.; Bischof, C., Automatic differentiation of numerical integration algorithms, Mathematics of Computation, 68, 226, 717-731 (1999) · Zbl 1017.65062
[15] Bischof, C. H.; Bücker, H. M.; Rasch, A., Sensitivity analysis of turbulence models using automatic differentiation, SIAM Journal on Scientific Computing, 26, 2, 510-522 (2005) · Zbl 1077.68932
[16] Toivanen, J. I.; Mäkinen, R. A.E.; Järvenpää, S.; Ylä-Oijala, P.; Rahola, J., Electromagnetic sensitivity analysis and shape optimization using method of moments and automatic differentiation, IEEE Transactions on Antennas and Propagation, 57, 1, 168-175 (2009) · Zbl 1369.78951
[17] Tadjouddine, M.; Forth, S. A.; Keane, A. J., Adjoint differentiation of a structural dynamics solver, (Bücker, H. M.; Corliss, G.; Hovland, P.; Naumann, U.; Norris, B., Automatic Differentiation: Applications, Theory, and Implementations. Automatic Differentiation: Applications, Theory, and Implementations, Lecture Notes in Computational Science and Engineering (2005), Springer) · Zbl 1270.74203
[18] Bischof, C. H.; Bücker, H. M.; an Mey, D., A case study of computational differentiation applied to neutron scattering, (Corliss, G.; Faure, C.; Griewank, A.; Hascoët, L.; Naumann, U., Automatic Differentiation of Algorithms: From Simulation to Optimization, Computer and Information Science (2002), Springer: Springer New York, NY), 69-74, (chapter 6)
[19] Fennel, K.; Losch, M.; Schröter, J.; Wenzel, M., Testing a marine ecosystem model: Sensitivity analysis and parameter optimization, Journal of Marine Systems, 28, 45-63 (2001)
[20] Sandu, A.; Daescu, D.; Carmichael, G. R.; Chai, T., Adjoint sensitivity analysis of regional air quality models, Journal of Computational Physics, 204, 1, 222-252 (2005) · Zbl 1061.92061
[21] A. Sandu, L. Zhang, Discrete second order adjoints in atmospheric chemical transport modeling, Journal of Computational Physics, in print; A. Sandu, L. Zhang, Discrete second order adjoints in atmospheric chemical transport modeling, Journal of Computational Physics, in print · Zbl 1144.92043
[22] Cao, Y.; Li, S.; Petzold, L.; Serban, R., Adjoint sensitivity analysis for differential-algebraic equations: The adjoint DAE system and its numerical solution, SIAM Journal on Scientific Computing, 24, 3, 1076-1089 (2002) · Zbl 1034.65066
[23] Sandu, A.; Daescu, D.; Carmichael, G. R., Direct and adjoint sensitivity analysis of chemical kinetic systems with KPP: Part I—Theory and software tools, Atmospheric Environment, 37, 36, 5083-5096 (2003)
[24] R. Serban, A.C. Hindmarsh, CVODES: The sensitivity-enabled ODE solver in SUNDIALS, Tech. Rep. UCRL-JP-200037, Lawrence Livermore National Laboratory, Livermore, CA, USA, 2003; R. Serban, A.C. Hindmarsh, CVODES: The sensitivity-enabled ODE solver in SUNDIALS, Tech. Rep. UCRL-JP-200037, Lawrence Livermore National Laboratory, Livermore, CA, USA, 2003
[25] LeDimet, F. X.; Navon, I. M.; Daescu, D., Second order information in data assimilation, Monthly Weather Review, 130, 3, 629-648 (2002)
[26] Wang, Z.; Navon, I. M.; LeDimet, F. X.; Zou, X., The second order adjoint analysis: Theory and applications, Meteorology and Atmospheric Physics, 50, 1-3, 3-20 (1992)
[27] Özyurt, D. B.; Barton, P. I., Cheap second order directional derivatives of stiff ODE embedded functionals, SIAM Journal on Scientific Computing, 26, 5, 1725-1743 (2005) · Zbl 1076.65067
[28] Hairer, E.; Nørsett, S. P.; Wanner, G., (Solving Ordinary Differential Equations: Nonstiff Problems. Solving Ordinary Differential Equations: Nonstiff Problems, Computational Mathematics, vol. I (1993), Springer-Verlag) · Zbl 0789.65048
[29] A. Sandu, On consistency properties of discrete adjoint linear multistep methods, Tech. Rep. TR-07-40, Virginia Polytechnic Institute and State University, Blacksburg, VA, USA, 2007; A. Sandu, On consistency properties of discrete adjoint linear multistep methods, Tech. Rep. TR-07-40, Virginia Polytechnic Institute and State University, Blacksburg, VA, USA, 2007
[30] Giering, R.; Kaminski, T., Recipes for adjoint code construction, ACM Transactions on Mathematical Software, 24, 4, 437-474 (1998) · Zbl 0934.65027
[31] Dormand, J. R.; Prince, P. J., A family of embedded Runge-Kutta formulae, Journal of Computational and Applied Mathematics, 6, 1, 19-26 (1980) · Zbl 0448.65045
[32] Shampine, L. F.; Reichelt, M. W., The matlab ode suite, SIAM Journal on Scientific Computing, 18, 1, 1-22 (1997) · Zbl 0868.65040
[33] Prothero, A.; Robinson, A., On the stability and accuracy of one-step methods for solving stiff systems of ordinary differential equations, Mathematics of Computation, 28, 125, 145-162 (1974) · Zbl 0309.65034
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.