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

Computing of B-series by automatic differentiation

1. 

University of Bergen, Department of Mathematics, Postbox 7800, N-5020 Bergen, Norway, Norway

Received  January 2013 Revised  April 2013 Published  August 2013

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.
Citation: Ferenc A. Bartha, Hans Z. Munthe-Kaas. Computing of B-series by automatic differentiation. Discrete & Continuous Dynamical Systems - A, 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.

[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.

[4]

A. Danis, "Parameter Estimation, Set Valued Numerics,", in Preparation, (2013).

[5]

F. Bartha, Ad-trees software,, , ().

[6]

S. Finch, Two asymptotic series,, , ().

[7]

C. Bendtsen and O. Stauning, FADBAD, a flexible C++ package for automatic differentiation,, Tech. Rep. IMM-REP-1996-17, (1996), 1996.

[8]

Computer Assisted Proofs in Dynamics Group, CAPD Library - a C++ package for rigorous numerics,, , ().

[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, ().

[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, (1964), 6.

[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). 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, (1991), 147.

[15]

J. C. Butcher, An algebraic theory of integration methods,, Math. Comp., 26 (1972), 79. 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. doi: 10.1155/S1073792801000198.

[17]

P. Chartier, E. Hairer and G. Vilmart, Numerical integrators based on modified differential equations,, Math. Comp., 76 (2007), 1941. doi: 10.1090/S0025-5718-07-01967-9.

[18]

A. Griewank, "Evaluating Derivatives,", Frontiers in Applied Mathematics, (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. doi: 10.1090/S0025-5718-00-01120-0.

[20]

E. Hairer, C. Lubich and G. Wanner, "Geometric Numerical Integration,", Springer Series in Computational Mathematics, (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. 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. doi: 10.1017/S1446788700034777.

[23]

W. Tucker, "Validated Numerics,", Princeton University Press, (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.

[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.

[4]

A. Danis, "Parameter Estimation, Set Valued Numerics,", in Preparation, (2013).

[5]

F. Bartha, Ad-trees software,, , ().

[6]

S. Finch, Two asymptotic series,, , ().

[7]

C. Bendtsen and O. Stauning, FADBAD, a flexible C++ package for automatic differentiation,, Tech. Rep. IMM-REP-1996-17, (1996), 1996.

[8]

Computer Assisted Proofs in Dynamics Group, CAPD Library - a C++ package for rigorous numerics,, , ().

[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, ().

[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, (1964), 6.

[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). 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, (1991), 147.

[15]

J. C. Butcher, An algebraic theory of integration methods,, Math. Comp., 26 (1972), 79. 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. doi: 10.1155/S1073792801000198.

[17]

P. Chartier, E. Hairer and G. Vilmart, Numerical integrators based on modified differential equations,, Math. Comp., 76 (2007), 1941. doi: 10.1090/S0025-5718-07-01967-9.

[18]

A. Griewank, "Evaluating Derivatives,", Frontiers in Applied Mathematics, (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. doi: 10.1090/S0025-5718-00-01120-0.

[20]

E. Hairer, C. Lubich and G. Wanner, "Geometric Numerical Integration,", Springer Series in Computational Mathematics, (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. 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. doi: 10.1017/S1446788700034777.

[23]

W. Tucker, "Validated Numerics,", Princeton University Press, (2011).

[1]

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

[2]

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 & Continuous Dynamical Systems - B, 2014, 19 (10) : i-ii. doi: 10.3934/dcdsb.2014.19.1i

[3]

J. Delon, A. Desolneux, Jose-Luis Lisani, A. B. Petro. Automatic color palette. Inverse Problems & Imaging, 2007, 1 (2) : 265-287. doi: 10.3934/ipi.2007.1.265

[4]

Lluís Alsedà, David Juher, Deborah M. King, Francesc Mañosas. Maximizing entropy of cycles on trees. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3237-3276. doi: 10.3934/dcds.2013.33.3237

[5]

Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems & Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1

[6]

Tanja Eisner, Jakub Konieczny. Automatic sequences as good weights for ergodic theorems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (8) : 4087-4115. doi: 10.3934/dcds.2018178

[7]

L. Igual, J. Preciozzi, L. Garrido, A. Almansa, V. Caselles, B. Rougé. Automatic low baseline stereo in urban areas. Inverse Problems & Imaging, 2007, 1 (2) : 319-348. doi: 10.3934/ipi.2007.1.319

[8]

Tom Maertens, Joris Walraevens, Herwig Bruneel. Controlling delay differentiation with priority jumps: Analytical study. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 657-673. doi: 10.3934/naco.2011.1.657

[9]

Bun Theang Ong, Masao Fukushima. Global optimization via differential evolution with automatic termination. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 57-67. doi: 10.3934/naco.2012.2.57

[10]

Jianzhong Wang. Wavelet approach to numerical differentiation of noisy functions. Communications on Pure & Applied Analysis, 2007, 6 (3) : 873-897. doi: 10.3934/cpaa.2007.6.873

[11]

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

[12]

Gusein Sh. Guseinov. Spectral method for deriving multivariate Poisson summation formulae. Communications on Pure & Applied Analysis, 2013, 12 (1) : 359-373. doi: 10.3934/cpaa.2013.12.359

[13]

Wenxue Huang, Qitian Qiu. Forward supervised discretization for multivariate with categorical responses. Big Data & Information Analytics, 2016, 1 (2&3) : 217-225. doi: 10.3934/bdia.2016005

[14]

Ferrán Valdez. Veech groups, irrational billiards and stable abelian differentials. Discrete & Continuous Dynamical Systems - A, 2012, 32 (3) : 1055-1063. doi: 10.3934/dcds.2012.32.1055

[15]

Manuel V. C. Vieira. Derivatives of eigenvalues and Jordan frames. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 115-126. doi: 10.3934/naco.2016003

[16]

Armengol Gasull, Francesc Mañosas. Subseries and signed series. Communications on Pure & Applied Analysis, 2019, 18 (1) : 479-492. doi: 10.3934/cpaa.2019024

[17]

Bertrand Maury, Delphine Salort, Christine Vannier. Trace theorems for trees and application to the human lungs. Networks & Heterogeneous Media, 2009, 4 (3) : 469-500. doi: 10.3934/nhm.2009.4.469

[18]

Xavier Dubois de La Sablonière, Benjamin Mauroy, Yannick Privat. Shape minimization of the dissipated energy in dyadic trees. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 767-799. doi: 10.3934/dcdsb.2011.16.767

[19]

Thierry Coulbois. Fractal trees for irreducible automorphisms of free groups. Journal of Modern Dynamics, 2010, 4 (2) : 359-391. doi: 10.3934/jmd.2010.4.359

[20]

Chris Bernhardt. Vertex maps for trees: Algebra and periods of periodic orbits. Discrete & Continuous Dynamical Systems - A, 2006, 14 (3) : 399-408. doi: 10.3934/dcds.2006.14.399

2017 Impact Factor: 1.179

Metrics

  • PDF downloads (2)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]