Computing of B-series by automatic differentiation

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

March 2014, 34(3): 903-914. doi: 10.3934/dcds.2014.34.903

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, Norway, Norway

Received January 2013 Revised April 2013 Published August 2013

Abstract
Related Papers

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: elementary differentials, automatic differentiation, multivariate derivatives, B-series, rooted trees..

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

Citation: Ferenc A. Bartha, Hans Z. Munthe-Kaas. Computing of B-series by automatic differentiation. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 903-914. doi: 10.3934/dcds.2014.34.903

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.

show all references

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.

[1]	Geir Bogfjellmo. Algebraic structure of aromatic B-series. Journal of Computational Dynamics, 2019, 6 (2) : 199-222. doi: 10.3934/jcd.2019010
[2]	Patrick Joly, Maryna Kachanovska, Adrien Semin. Wave propagation in fractal trees. Mathematical and numerical issues. Networks and Heterogeneous Media, 2019, 14 (2) : 205-264. doi: 10.3934/nhm.2019010
[3]	Joan Gimeno, Àngel Jorba. Using automatic differentiation to compute periodic orbits of delay differential equations. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4853-4867. doi: 10.3934/dcdsb.2020130
[4]	Richard D. Neidinger. Efficient recurrence relations for univariate and multivariate Taylor series coefficients. Conference Publications, 2013, 2013 (special) : 587-596. doi: 10.3934/proc.2013.2013.587
[5]	Robert Stephen Cantrell, Suzanne Lenhart, Yuan Lou, Shigui Ruan. Preface on the special issue of Discrete and Continuous Dynamical Systems- Series B in honor of Chris Cosner on the occasion of his 60th birthday. Discrete and Continuous Dynamical Systems - B, 2014, 19 (10) : i-ii. doi: 10.3934/dcdsb.2014.19.1i
[6]	Hui Li, Manjun Ma. Corrigendum on “H. Li and M. Ma, global dynamics of a virus infection model with repulsive effect, Discrete and Continuous Dynamical Systems, Series B, 24(9) 4783-4797, 2019”. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4925-4925. doi: 10.3934/dcdsb.2020299
[7]	J. Delon, A. Desolneux, Jose-Luis Lisani, A. B. Petro. Automatic color palette. Inverse Problems and Imaging, 2007, 1 (2) : 265-287. doi: 10.3934/ipi.2007.1.265
[8]	Karl Petersen, Ibrahim Salama. Entropy on regular trees. Discrete and Continuous Dynamical Systems, 2020, 40 (7) : 4453-4477. doi: 10.3934/dcds.2020186
[9]	Lluís Alsedà, David Juher, Deborah M. King, Francesc Mañosas. Maximizing entropy of cycles on trees. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3237-3276. doi: 10.3934/dcds.2013.33.3237
[10]	Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems and Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1
[11]	Ana-Maria Acu, Laura Hodis, Ioan Rasa. Multivariate weighted kantorovich operators. Mathematical Foundations of Computing, 2020, 3 (2) : 117-124. doi: 10.3934/mfc.2020009
[12]	Tom Maertens, Joris Walraevens, Herwig Bruneel. Controlling delay differentiation with priority jumps: Analytical study. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 657-673. doi: 10.3934/naco.2011.1.657
[13]	Jianzhong Wang. Wavelet approach to numerical differentiation of noisy functions. Communications on Pure and Applied Analysis, 2007, 6 (3) : 873-897. doi: 10.3934/cpaa.2007.6.873
[14]	Dawei Chen. Strata of abelian differentials and the Teichmüller dynamics. Journal of Modern Dynamics, 2013, 7 (1) : 135-152. doi: 10.3934/jmd.2013.7.135
[15]	Ferrán Valdez. Veech groups, irrational billiards and stable abelian differentials. Discrete and Continuous Dynamical Systems, 2012, 32 (3) : 1055-1063. doi: 10.3934/dcds.2012.32.1055
[16]	Lluís Alsedà, David Juher, Francesc Mañosas. Forward triplets and topological entropy on trees. Discrete and Continuous Dynamical Systems, 2022, 42 (2) : 623-641. doi: 10.3934/dcds.2021131
[17]	Bin Han. Some multivariate polynomials for doubled permutations. Electronic Research Archive, 2021, 29 (2) : 1925-1944. doi: 10.3934/era.2020098
[18]	Tanja Eisner, Jakub Konieczny. Automatic sequences as good weights for ergodic theorems. Discrete and Continuous Dynamical Systems, 2018, 38 (8) : 4087-4115. doi: 10.3934/dcds.2018178
[19]	L. Igual, J. Preciozzi, L. Garrido, A. Almansa, V. Caselles, B. Rougé. Automatic low baseline stereo in urban areas. Inverse Problems and Imaging, 2007, 1 (2) : 319-348. doi: 10.3934/ipi.2007.1.319
[20]	Mariusz Lemańczyk, Clemens Müllner. Automatic sequences are orthogonal to aperiodic multiplicative functions. Discrete and Continuous Dynamical Systems, 2020, 40 (12) : 6877-6918. doi: 10.3934/dcds.2020260

2021 Impact Factor: 1.588

Tools

Metrics

Other articles
by authors

on AIMS
Ferenc A. Bartha Hans Z. Munthe-Kaas
on Google Scholar
Ferenc A. Bartha Hans Z. Munthe-Kaas

[Back to Top]