Computing of B-series by automatic differentiation. (English) Zbl 1278.65020

Summary: 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.


65D25 Numerical differentiation
65L05 Numerical methods for initial value problems involving ordinary differential equations
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI


[1] P. Moan, <em>Symplectic elementary differential Runge-Kutta methods</em>,, Numerische Mathematik, (2004)
[2] C. Simó, <em>On the analytical and numerical approximation of invariant manifolds</em>,, Les Méthodes Modernes de la Mecánique Céleste, 285, (1990)
[3] G. Li, <em>The advantages of forward thinking in generating rooted and free trees</em>,, 10th annual ACM-SIAM symposium on discrete algorithms, 939, (1999) · Zbl 0929.68091
[4] A. Danis, “Parameter Estimation, Set Valued Numerics,”, in Preparation, (2013)
[5] F. Bartha, <em>Ad-trees software</em>,, <a href=
[6] S. Finch, <em>Two asymptotic series</em>,, <a href=
[7] C. Bendtsen, <em>FADBAD, a flexible C++ package for automatic differentiation,</em>, Tech. Rep. IMM-REP-1996-17, 1996, (1996)
[8] Computer Assisted Proofs in Dynamics Group, <em>CAPD Library - a C++ package for rigorous numerics</em>,, <a href=
[9] J. G. Siek, “The Boost Graph Library User Guide and Reference Manual,”, Addison-Wesley Professional, (2001)
[10] K. Ebrahimi-Fard, <em>The magnus expansion, trees and Knuth’s rotation correspondence</em>,, preprint · Zbl 1331.17016
[11] R. E. Moore, <em>DIFEQ integration routine - user’s manual,</em>, Tech. Rep. LMSC 6-90-64-6, 6, (1964)
[12] “Graph Drawing,”, Lecture Notes in Computer Science, 22, (2009) · Zbl 1185.68005
[13] A. Abad, <em>Algorithm 924: TIDES, a Taylor series Integrator for Differential EquationS,</em>, ACM Trans. Math. Software, 39, (2012) · Zbl 1295.65138
[14] M. Berz, <em>Algorithms for higher derivatives in many variables with applications to beam physics</em>,, SIAM Automatic Differentiation of Algorithms (Breckenridge, 147, (1991) · Zbl 0782.65018
[15] J. C. Butcher, <em>An algebraic theory of integration methods</em>,, Math. Comp., 26, 79, (1972) · Zbl 0258.65070
[16] F. Chapoton, <em>Pre-Lie algebras and the rooted trees operad</em>,, Internat. Math. Res. Notices, 2001, 395, (2001) · Zbl 1053.17001
[17] P. Chartier, <em>Numerical integrators based on modified differential equations</em>,, Math. Comp., 76, 1941, (2007) · Zbl 1122.65059
[18] A. Griewank, “Evaluating Derivatives,”, Frontiers in Applied Mathematics, (2000) · Zbl 0958.65028
[19] A. Griewank, <em>Evaluating higher derivative tensors by forward propagation of univariate Taylor series</em>,, Math. Comp., 69, 1117, (2000) · Zbl 0952.65028
[20] E. Hairer, “Geometric Numerical Integration,”, Springer Series in Computational Mathematics, (2006) · Zbl 1028.65136
[21] À. Jorba, <em>A software package for the numerical integration of ODEs by means of high-order Taylor methods,</em>, Experiment. Math., 14, 99, (2005) · Zbl 1108.65072
[22] J. M. Plotkin, <em>How to obtain an asymptotic expansion of a sequence from an analytic identity satisfied by its generating function</em>,, J. Austral. Math. Soc. Ser. A, 56, 131, (1994) · Zbl 0795.05002
[23] W. Tucker, “Validated Numerics,”, Princeton University Press, (2011) · Zbl 1231.65077
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.