On the dimension of certain graded Lie algebras arising in geometric integration of differential equations

Many discretization methods for differential equations that evolve in Lie groups and homogeneous spaces advance the solution in the underlying Lie algebra. The main expense of computation is the calculation of commutators, a task that can be made significantly cheaper by the introduction of appropriate bases of function values and exploitation of redundancies inherent in a Lie-algebraic structure by means of graded spaces. In many Lie groups of practical interest a convenient alternative to the exponential map is a Cayley transformation and the subject of this paper is the investigation of graded algebras that occur in this context. To this end we introduce a new concept, a {\em hierarchical algebra,\/} a Lie algebra equipped with a countable number of $m$-nary multilinear operations which display alternating symmetry and a `hierarchy condition'. We present explicit formulae for the dimension of graded subspaces of free hierarchical algebras and an algorithm for the construction of their basis. The paper is concluded by reviewing a number of applications of our results to numerical methods in a Lie-algebraic setting.