Forward and adjoint sensitivity analysis with continuous explicit Runge-Kutta schemes. (English) Zbl 1159.65071

Alexe, Mihai; Sandu, Adrian

Appl. Math. Comput. 208, No. 2, 328-346 (2009).

Summary: We study the numerical solution of tangent linear, first and second order adjoint models with high-order explicit, continuous Runge-Kutta pairs. The approaches currently implemented in popular packages such as SUNDIALS or DASPKADJOINT are based on linear multistep methods. For adaptive time integration of nonlinear models, interpolation of the forward model solution is required during the adjoint model simulation. We propose to use the dense output mechanism built in the continuous Runge-Kutta schemes as a highly accurate and cost-efficient interpolation method in the inverse problem run. We implement our approach in a Fortran library called DENSERKS, which is found to compare well to other similar software on a number of test problems.

MSC:

65L06	Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65L05	Numerical methods for initial value problems involving ordinary differential equations
34A34	Nonlinear ordinary differential equations and systems
65Y15	Packaged methods for numerical algorithms

Keywords:

sensitivity analysis; dense output; Runge-Kutta pairs; tangent linear models; adjoint models; automatic differentiation; numerical examples; linear multistep methods; Fortran library; DENSERKS

Software:

TAF; TAPENADE; CVODES; TAMC; MITgcm; SUNDIALS; KPP; DASPKADJOINT; DASPK 3.0; L-BFGS-B; L-BFGS; RODAS; LBFGS-B

References:

[1]	Navon, I.M., Practical and theoretical aspects of adjoint parameter estimation and identifiability in meteorology and oceanography, Dyn. atmos. oceans, 27, 55-79, (1997)
[2]	Damian, V.; Sandu, A.; Damian, M.; Potra, F.; Carmichael, G.R., The kinetic preprocessor KPP - a software environment for solving chemical kinetics, Comput. chem. eng., 26, 1567-1579, (2002)
[3]	LeDimet, F.X.; Navon, I.M.; Daescu, D., Second order information in data assimilation, Mon. weather rev., 130, 3, 629-648, (2002)
[4]	Griesse, R.; Walther, A., Parametric sensitivities for optimal control problems using automatic differentiation, Optim. control appl. methods, 28, 297-314, (2003) · Zbl 1073.93518
[5]	A. Adcroft, J.-M. Campin, P. Heimbach, C. Hill, J. Marshall, MIT General Circulation Model User’s Manual, MIT, Boston, MA, USA, 2007.
[6]	Sandu, A.; Daescu, D.; Carmichael, G.R.; Chai, T., Adjoint sensitivity analysis of regional air quality models, J. comput. phys., 204, 1, 222-252, (2005) · Zbl 1061.92061
[7]	Özyurt, D.B.; Barton, P.I., Large-scale dynamic optimization using the directional second-order adjoint method, Ind. eng. chem. res., 44, 1804-1811, (2005)
[8]	Hager, W.W., Runge – kutta methods in optimal control and the transformed adjoint system, Numer. math., 87, 2, 247-282, (2000) · Zbl 0991.49020
[9]	A. Sandu, On the properties of Runge-Kutta discrete adjoints, in: International Conference on Computational Science, vol. 4, 2006, pp. 550-557. · Zbl 1157.65421
[10]	Walther, A., Automatic differentiation of explicit runge – kutta methods for optimal control, Comput. optim. appl., 36, 1, 83-108, (2007) · Zbl 1278.49037
[11]	R. Giering, Tangent Linear and Adjoint Model Compiler, Users manual 1.4, 1999.
[12]	R. Giering, T. Kaminski, Applying TAF to generate efficient derivative code of Fortran 77-95 programs, Proc. Appl. Math. Mech. 2 (1) (2003) 54-57.
[13]	L. Hascöet, V. Pascual, TAPENADE 2.1 user’s guide, Tech. Rep. 0300, INRIA, Sophia Antipolis, France, 2004.
[14]	M. Alexe, A. Sandu, On the discrete adjoints of adaptive time stepping algorithms, Tech. Rep. TR-08-08, Virginia Polytechnic Institute and State University, Blacksburg, VA, USA, 2008. · Zbl 1177.65098
[15]	Eberhard, P.; Bischof, C., Automatic differentiation of numerical integration algorithms, Math. comput., 68, 226, 717-731, (1999) · Zbl 1017.65062
[16]	Baker, T.S.; Dormand, J.R.; Gilmore, J.P.; Prince, P.J., Continuous approximation with embedded runge – kutta methods, Appl. numer. math., 22, 1-3, 51-62, (1996) · Zbl 0871.65077
[17]	E. Hairer, S.P. Nrsett, G. Wanner, Solving ordinary differential equations: nonstiff problems, in: Computational Mathematics, vol. I, Springer-Verlag, 1993. · Zbl 0789.65048
[18]	Sharp, P.W.; Verner, J.H., Generation of high-order interpolants for explicit runge – kutta pairs, ACM trans. math. softw., 24, 1, 13-29, (1998) · Zbl 0928.65086
[19]	Özyurt, D.B.; Barton, P.I., Cheap second order directional derivatives of stiff ODE embedded functionals, SIAM J. sci. comput., 26, 5, 1725-1743, (2005) · Zbl 1076.65067
[20]	Hindmarsh, A.C.; Brown, P.N.; Grant, K.E.; Lee, S.L.; Serban, R.; Shumaker, D.E.; Woodward, C.S., SUNDIALS: suite of nonlinear and differential/algebraic equation solvers, ACM trans. math. softw., 31, 3, 363-396, (2005) · Zbl 1136.65329
[21]	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.
[22]	A.C. Hindmarsh, R. Serban, User documentation for CVODES v 2.5.0, Lawrence Livermore National Laboratory, Livermore, CA, USA, 2006.
[23]	Cao, Y.; Li, S.; Petzold, L.; Serban, R., Adjoint sensitivity analysis for differential-algebraic equations: the adjoint DAE system and its numerical solution, SIAM J. sci. comput., 24, 3, 1076-1089, (2002) · Zbl 1034.65066
[24]	S. Li, L. Petzold, Design of new DASPK for sensitivity analysis, Tech. Rep. TRCS99-28, University of California at Santa-Barbara, Santa Barbara, CA, USA, 1999.
[25]	S. Li, L. Petzold, Description of DASPKADJOINT: an adjoint sensitivity solver for differential-algebraic equations, Tech. Rep. TRCS99-28, University of California at Santa-Barbara, Santa Barbara, CA, USA, 2002.
[26]	A. Sandu, P. Miehe, Forward, tangent linear, and adjoint Runge-Kutta methods in KPP-2.2 for efficient chemical kinetic simulations, Tech. Rep. TR-06-17, Virginia Tech, Blacksburg, VA, USA, 2006. · Zbl 1157.80405
[27]	Daescu, D.N.; Sandu, A.; Carmichael, G.R., Direct and adjoint sensitivity analysis of chemical kinetic systems with KPP: II—numerical validation and applications, Atmos. environ., 37, 36, 5097-5114, (2003)
[28]	Sandu, A.; Daescu, D.; Carmichael, G.R., Direct and adjoint sensitivity analysis of chemical kinetic systems with KPP: part I—theory and software tools, Atmos. environ., 37, 36, 5083-5096, (2003)
[29]	Verner, J.H., Differentiable interpolants for high-order runge – kutta methods, SIAM J. numer. anal., 30, 5, 1446-1466, (1993) · Zbl 0787.65047
[30]	E. Hairer, G. Wanner, Solving ordinary differential equations: stiff and differential-algebraic problems, in: Computational Mathematics, vol. II, Springer-Verlag, 1994. · Zbl 0729.65051
[31]	Ostermann, A., Continuous extensions of rosenbrock-type methods, Computing, 44, 1, 59-68, (1990) · Zbl 0697.65055
[32]	Hairer, E.; Ostermann, A., Dense output for extrapolation methods, Numer. math., 58, 1, 419-439, (1990) · Zbl 0693.65048
[33]	Sandu, A.; Zhang, L., Discrete second order adjoints in atmospheric chemical transport modeling, J. comput. phys., 224, 12, 5949-5983, (2008) · Zbl 1144.92043
[34]	Dormand, J.R.; Prince, P.J., A family of embedded runge – kutta formulae, J. comput. appl. math., 6, 1, 19-26, (1980) · Zbl 0448.65045
[35]	Prince, P.J.; Dormand, J.R., High order embedded runge – kutta formulae, J. comput. appl. math., 7, 67-76, (1981) · Zbl 0449.65048
[36]	Dormand, J.R.; Lockyer, M.A.; McGorrigan, N.E.; Prince, P.J., Global error estimation with runge – kutta triples, Comput. math. appl., 18, 9, 835-846, (1989) · Zbl 0683.65054
[37]	Cao, Y.; Li, S.; Petzold, L., Adjoint sensitivity analysis for differential-algebraic equations: algorithms and software, J. comput. appl. math., 149, 1, 171-191, (2002) · Zbl 1013.65084
[38]	Griewank, A., Evaluating derivatives: principles and techniques of algorithmic differentiation, (2000), SIAM Philadelphia, PA, USA · Zbl 0958.65028
[39]	A.C. Hindmarsh, R. Serban, Example Programs for CVODES v.2.5.0, Lawrence Livermore National Laboratory, Livermore, CA, USA, November, 2006.
[40]	Zhu, C.; Byrd, R.H.; Lu, P.; Nocedal, J., Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM trans. math. softw., 23, 4, 550-560, (1997) · Zbl 0912.65057