Computing of B-series by automatic differentiation

Ferenc A. Bartha; Hans Z. Munthe-Kaas

doi:10.3934/dcds.2014.34.903

Article Contents

2014, Volume 34, Issue 3: 903-914. Doi: 10.3934/dcds.2014.34.903

This issue Previous Article A Gaussian quadrature rule for oscillatory integrals on a bounded interval Next Article On Volterra integral operators with highly oscillatory kernels

Computing of B-series by automatic differentiation

Ferenc A. Bartha^1, and
Hans Z. Munthe-Kaas^1,

1.
University of Bergen, Department of Mathematics, Postbox 7800, N-5020 Bergen

Received: December 31, 2012

Revised: March 31, 2013

Published: February 2014

Abstract Related Papers Cited by

Abstract

We present an algorithm based on Automatic Differentiation for computing general B-series of vector fields $f\colon \mathbb{R}^n\rightarrow \mathbb{R}^n$. The algorithm has a computational complexity depending linearly on $n$, and provides a practical way of computing B-series up to a moderately high order $d$. Compared to Automatic Differentiation for computing Taylor series solutions of differential equations, the proposed algorithm is more general, since it can compute any B-series. However the computational cost of the proposed algorithm grows much faster in $d$ than a Taylor series method, thus very high order B-series are not tractable by this approach.

Keywords:

Mathematics Subject Classification: Primary: 65D25, 65L05, 65L06; Secondary: 65Y20.

Citation:

Related Papers

Cited by

References

[1]	P. Moan, A. Murua, G. Quispel, M. Sofroniou and G. Spaletta, Symplectic elementary differential Runge-Kutta methods, Numerische Mathematik, (2004).
[2]	C. Simó, On the analytical and numerical approximation of invariant manifolds, Les Méthodes Modernes de la Mecánique Céleste, (1990), 285-329.
[3]	G. Li and F. Ruskey, The advantages of forward thinking in generating rooted and free trees, 10th annual ACM-SIAM symposium on discrete algorithms, (1999), 939-940.
[4]	A. Danis, "Parameter Estimation, Set Valued Numerics," in Preparation, Ph.D thesis: Uppsala University, 2013.
[5]	F. Bartha, Ad-trees software, http://www2.math.uu.se/ warwick/CAPA/publications/supplements/Bseries.tar.gz.
[6]	S. Finch, Two asymptotic series, http://www.people.fas.harvard.edu/ sfinch/csolve/asym.pdf.
[7]	C. Bendtsen and O. Stauning, FADBAD, a flexible C++ package for automatic differentiation, Tech. Rep. IMM-REP-1996-17, TU Denmark, DK-2800 Lyngby, Denmark, (1996).
[8]	Computer Assisted Proofs in Dynamics Group, CAPD Library - a C++ package for rigorous numerics, http://capd.ii.uj.edu.pl.
[9]	J. G. Siek, L. Q. Leeand A. Lumsdaine, "The Boost Graph Library User Guide and Reference Manual," Addison-Wesley Professional, 2001.
[10]	K. Ebrahimi-Fard and D. Manchon, The magnus expansion, trees and Knuth's rotation correspondence, preprint, arXiv:1203.2878.
[11]	R. E. Moore, J. A. Davidson, H. R. Jaske and S. Shayer, DIFEQ integration routine - user's manual, Tech. Rep. LMSC 6-90-64-6, Lockheed Missiles and Space Co., Palo Alto, CA, (1964).
[12]	"Graph Drawing,", Lecture Notes in Computer Science, (2009),22. doi: 10.1007/978-3-642-11805-0.
[13]	A. Abad, R. Barrio, F. Blesa and M. Rodríguez, Algorithm 924: TIDES, a Taylor series Integrator for Differential EquationS, ACM Trans. Math. Software, 39 (2012), Art. 5, 28pp.doi: 10.1145/2382585.2382590.
[14]	M. Berz, Algorithms for higher derivatives in many variables with applications to beam physics, SIAM Automatic Differentiation of Algorithms (Breckenridge, CO, 1991), (1991), 147-156.
[15]	J. C. Butcher, An algebraic theory of integration methods, Math. Comp., 26 (1972), 79-106.doi: 10.1090/S0025-5718-1972-0305608-0.
[16]	F. Chapoton and M. Livernet, Pre-Lie algebras and the rooted trees operad, Internat. Math. Res. Notices, 2001 (2001), 395-408.doi: 10.1155/S1073792801000198.
[17]	P. Chartier, E. Hairer and G. Vilmart, Numerical integrators based on modified differential equations, Math. Comp., 76 (2007), 1941-1953.doi: 10.1090/S0025-5718-07-01967-9.
[18]	A. Griewank, "Evaluating Derivatives," Frontiers in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000.
[19]	A. Griewank, J. Utke and A. Walther, Evaluating higher derivative tensors by forward propagation of univariate Taylor series, Math. Comp., 69 (2000), 1117-1130.doi: 10.1090/S0025-5718-00-01120-0.
[20]	E. Hairer, C. Lubich and G. Wanner, "Geometric Numerical Integration," Springer Series in Computational Mathematics, Springer-Verlag, Berlin, 2006.
[21]	À. Jorba and M. Zou, A software package for the numerical integration of ODEs by means of high-order Taylor methods, Experiment. Math., 14 (2005), 99-117.doi: 10.1080/10586458.2005.10128904.
[22]	J. M. Plotkin and J. W. Rosenthal, How to obtain an asymptotic expansion of a sequence from an analytic identity satisfied by its generating function, J. Austral. Math. Soc. Ser. A, 56 (1994), 131-143.doi: 10.1017/S1446788700034777.
[23]	W. Tucker, "Validated Numerics," Princeton University Press, Princeton, NJ, 2011.