Abstract
We show that without other further assumption than affine equivariance and locality, a numerical integrator has an expansion in a generalized form of Butcher series (B-series), which we call aromatic B-series. We obtain an explicit description of aromatic B-series in terms of elementary differentials associated to aromatic trees, which are directed graphs generalizing trees. We also define a new class of integrators, the class of aromatic Runge–Kutta methods, that extends the class of Runge–Kutta methods and have aromatic B-series expansion but are not B-series methods. Finally, those results are partially extended to the case of more general affine group equivariance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.V. Alekseevskii, R.V. Gamkrelidze, V.V. Lychagin, and A.M. Vinogradov. Geometry 1. Number v. 2 in Encyclopaedia of mathematical sciences: Geometry. Springer-Verlag, 1991. ISBN 9780387519999.
C. Berge. Graphs. North-Holland Mathematical Library. Elsevier, 1991. ISBN 9780444876030.
J. C. Butcher. An algebraic theory of integration methods. Mathematics of Computation, 26(117):79–106, 1972. doi:10.1090/S0025-5718-1972-0305608-0.
P. Chartier and A. Murua. Preserving first integrals and volume forms of additively split systems. IMA journal of numerical analysis, 27(2):381–405, 2007. doi:10.1093/imanum/drl039.
M. Fontes and O. Verdier. Time-Periodic Solutions of the Burgers Equation. Journal of Mathematical Fluid Mechanics, 11:303–323, 2009. doi:10.1007/s00021-007-0260-z.
D.B. Fuks. Cohomology of infinite-dimensional Lie algebras. Monographs in Contemporary Mathematics. Springer, 1986. ISBN 978-0306109904.
H. N. Gabow and R. E. Tarjan. A linear-time algorithm for finding a minimum spanning pseudoforest. Information Processing Letters, 27(5):259 – 263, 1988. doi:10.1016/0020-0190(88)90089-0.
W.H. Greub. Multilinear Algebra. Graduate Texts in Mathematics. Springer, 1981. ISBN 978-0387901107.
E. Hairer. Backward analysis of numerical integrators and symplectic methods. Ann. Numer. Math., 1 (1-4):107–132, 1994.
E. Hairer and G. Wanner. Solving ordinary differential equations. II: Stiff and differential-algebraic problems. Reprint of the 1996 2nd revised ed. Berlin: Springer, 2010. ISBN 978-3-642-05221-7. doi:10.1007/978-3-642-05221-7.
E. Hairer, C. Lubich, and G. Wanner. Geometric numerical integration: structure-preserving algorithms for ordinary differential equations. Springer series in computational mathematics. Springer, 2006. ISBN 9783540306634.
A. Iserles, G. R. W. Quispel, and P. Tse. B-series methods cannot be volume-preserving. BIT Numerical Mathematics, 47(2):351–378, 2007. doi:10.1007/s10543-006-0114-8.
I. Kolar, P.W. Michor, and J. Slovak. Natural Operations in Differential Geometry. Electronic library of mathematics. Springer, 1993. ISBN 9783540562351. URL http://www.emis.de/monographs/KSM/kmsbookh.pdf.
H. Kraft and C. Procesi. Classical Invariant Theory - A Primer, 1996. URL http://jones.math.unibas.ch/~kraft/Papers/KP-Primer.pdf.
A. Kriegl and P.W. Michor. The convenient setting of global analysis. AMS Mathematical Surveys and Monographs. American Mathematical Society, 1997. ISBN 9780821807804. URL http://www.mat.univie.ac.at/~michor/kmsbookh.pdf.
K. Kuratowski and A. Mostowski. Set Theory, with an Introduction to Descriptive Set Theory, volume 86 of Studies in Logic and the Foundations of Mathematics. 1976.
M. Markl. \(\text{ GL }_{n}\)-invariant tensors and graphs. Arch. Math., Brno, 44(5):449–463, 2008. URL http://hdl.handle.net/10338.dmlcz/127128.
R. I. McLachlan, K. Modin, H. Z. Munthe-Kaas, and O. Verdier. B-series methods are exactly the local, affine equivariant methods, 2014. URL http://arxiv.org/abs/1409.1019. arXiv.
R. I. McLachlan, H. Z. Munthe-Kaas, and O. Verdier. Solenoidal Affine Equivariant Series. In preparation, 2014.
RI McLachlan and GR Quispel. Six lectures on the geometric integration of ODEs. In Foundations of Computational Mathematics, London Mathematical Society Lecture Note Series, pages 155–210. Cambridge University Press, 2001. ISBN 9780521003490.
G.R.W. Quispel and D.I. McLaren. A new class of energy-preserving numerical integration methods. J. Phys. A, Math. Theor., 41(4):7, 2008. doi:10.1088/1751-8113/41/4/045206.
D.J. Saunders. The Geometry of Jet Bundles. Cambridge University Press, 1989. ISBN 9780521369480.
Acknowledgments
The authors would like to thank Robert McLachlan for many comments and discussions. This research was supported by the Spade Ace Project, by a Marie Curie International Research Staff Exchange Scheme Fellowship within the 7th European Community Framework Programme, and by the J.C. Kempe memorial fund.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Ernst Hairer.
Rights and permissions
About this article
Cite this article
Munthe-Kaas, H., Verdier, O. Aromatic Butcher Series. Found Comput Math 16, 183–215 (2016). https://doi.org/10.1007/s10208-015-9245-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-015-9245-0
Keywords
- B-Series
- Butcher series
- Equivariance
- Aromatic series
- Aromatic trees
- Functional graph
- Directed pseudo-forest