In this paper, we present an abstract framework which describes algebraically the derivation of order conditions independently of the nature of differential equations considered or the type of integrators used to solve them. Our structure includes a Hopf algebra of functions, whose properties are used to answer several questions of prime interest in numerical analysis. In particular, we show that, under some mild assumptions, there exist integrators of arbitrarily high orders for arbitrary (modified) vector fields.
@article{M2AN_2009__43_4_607_0,
author = {Chartier, Philippe and Murua, Ander},
title = {An algebraic theory of order},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
volume = {43},
year = {2009},
pages = {607-630},
doi = {10.1051/m2an/2009029},
mrnumber = {2542867},
zbl = {pre05590606},
language = {en},
url = {http://dml.mathdoc.fr/item/M2AN_2009__43_4_607_0}
}
Chartier, Philippe; Murua, Ander. An algebraic theory of order. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 43 (2009) pp. 607-630. doi : 10.1051/m2an/2009029. http://gdmltest.u-ga.fr/item/M2AN_2009__43_4_607_0/
[1] and , Algebraic structures on ordered rooted trees and their significance to Lie group integrators, in Group theory and numerical analysis, CRM Proc. Lecture Notes, Amer. Math. Soc., Providence R.I. (2005) 49-63. | MR 2182810 | Zbl 1080.65056
[2] , Lie groups and Lie algebras. Springer-Verlag, Berlin-New York (1989). | MR 979493
[3] , An algebraic theory of integration methods. Math. Comput. 26 (1972) 79-106. | MR 305608 | Zbl 0258.65070
[4] , A primer of Hopf algebras, in Frontiers in number theory, physics, and geometry II. Springer, Berlin (2007) 537-615. | MR 2290769 | Zbl 1184.16031 | Zbl pre05120005
[5] and , Preserving first integrals and volume forms of additively split systems. IMA J. Numer. Anal. 27 (2007) 381-405. | MR 2317009 | Zbl 1118.65086
[6] , and , An algebraic approach to invariant preserving integators: the case of quadratic and Hamiltonian invariants. Numer. Math. 103 (2006) 575-590. | MR 2221062 | Zbl 1100.65115
[7] and , Hopf algebras, cyclic cohomology and the transverse index theorem. Commun. Math. Phys. 198 (1998). | MR 1657389 | Zbl 0940.58005
[8] , Möbius functions, incidence algebras and power-series representations, in Lecture Notes in Mathematics 1202, Springer-Verlag (1986). | MR 857100 | Zbl 0592.05006
[9] , and , Geometric Numerical Integration - Structure-Preserving Algorithms for Ordinary Differential Equations, Second edition, Springer Series in Computational Mathematics 31. Springer, Berlin (2006). | MR 2221614 | Zbl 1094.65125
[10] , Basic theory of algebraic groups and Lie algebras. Springer-Verlag (1981). | MR 620024 | Zbl 0589.20025
[11] , Quasi-shuffle products. J. Algebraic Comb. 11 (2000) 49-68. | MR 1747062 | Zbl 0959.16021
[12] , On the Hopf algebra structure of perturbative quantum field theories. Adv. Theor. Math. Phys. 2 (1998) 303-334. | MR 1633004 | Zbl 1041.81087
[13] and , On the structure of Hopf algebras. Ann. Math. 81 (1965) 211-264. | MR 174052 | Zbl 0163.28202
[14] and , On the Hopf algebraic structure of Lie group integrators. Found. Comput. Math. 8 (2008) 227-257. | MR 2407032 | Zbl 1147.16028
[15] , Formal series and numerical integrators, Part i: Systems of ODEs and symplectic integrators. Appl. Numer. Math. 29 (1999) 221-251. | MR 1666537 | Zbl 0929.65126
[16] , The Hopf algebra of rooted trees, free Lie algebras, and Lie series. Found. Comput. Math. 6 (2006) 387-426. | MR 2271214 | Zbl 1116.17004
[17] and , Order conditions for numerical integrators obtained by composing simpler integrators. Phil. Trans. R. Soc. A 357 (1999) 1079-1100. | MR 1694703 | Zbl 0946.65056