On the Implementation of Lie Group Methods on the Stiefel Manifold

There are several applications in which one needs to integrate a system of ODEs whose solution is an n×p matrix with orthonormal columns. In recent papers algorithms of arithmetic complexity order np ² have been proposed. The class of Lie group integrators may seem like a worth while alternative for this class of problems, but it has not been clear how to implement such methods with O(np ²) complexity. In this paper we show how Lie group methods can be implemented in a computationally competitive way, by exploiting that analytic functions of n×n matrices of rank 2p can be computed with O(np ²) complexity.     

Cost Efficient Lie Group Integrators in the RKMK Class

In this work a systematic procedure is implemented in order to minimise the computational cost of the Runge—Kutta—Munthe-Kaas (RKMK) class of Lie-group solvers. The process consists of the application of a linear transformation to the stages of the method and the analysis of a graded free Lie algebra to reduce the number of commutators involved. We consider here RKMK integration methods up to order seven based on some of the most popular Runge—Kutta schemes.This revised version was published online in October 2005 with corrections to the Cover Date.     

A Note on the Construction of Crouch-Grossman Methods

Numerical integration methods based on rigid frames were introduced by Crouch and Grossman. The order theory of these methods were later analyzed by Owren and Marthinsen. The resulting order conditions are difficult to solve due to nonlinear relations on the weights of the methods. In this paper we propose a variant of the Crouch-Grossman method that uses modified vector fields so that the order conditions of this new method coincide with the classical order conditions for Runge-Kutta methods.     

Runge-Kutta Methods Adapted to Manifolds and Based on Rigid Frames

We consider numerical integration methods for differentiable manifolds as proposed by Crouch and Grossman. The differential system is phrased by means of a system of frame vector fields E ₁, ... , E _n on the manifold. The numerical approximation is obtained by composing flows of certain vector fields in the linear span of E ₁, ... , E _n that are tangent to the differential system at various points. The methods reduce to traditional Runge-Kutta methods if the frame vector fields are chosen as the standard basis of euclidean ⁿ . A complete theory for the order conditions involving ordered rooted trees is developed. Examples of explicit and diagonal implicit methods are presented, along with some numerical results.     

Partitioned Runge–Kutta Methods in Lie-Group Setting

We introduce partitioned Runge–Kutta (PRK) methods as geometric integrators in the Runge–Kutta–Munthe-Kaas (RKMK) method hierarchy. This is done by first noticing that tangent and cotangent bundles are the natural domains for the differential equations to be solved. Next, we equip the (co)tangent bundle of a Lie group with a group structure and treat it as a Lie group. The structure of the differential equations on the (co)tangent-bundle Lie group is such that partitioned versions of the RKMK methods are naturally introduced. Numerical examples are included to illustrate the new methods.     

The Newton Iteration on Lie Groups

We define the Newton iteration for solving the equation f(y) = 0, where f is a map from a Lie group to its corresponding Lie algebra. Two versions are presented, which are formulated independently of any metric on the Lie group. Both formulations reduce to the standard method in the Euclidean case, and are related to existing algorithms on certain Riemannian manifolds. In particular, we show that, under classical assumptions on f, the proposed method converges quadratically. We illustrate the techniques by solving a fixed-point problem arising from the numerical integration of a Lie-type initial value problem via implicit Euler.     

Symmetric Projection Methods for Differential Equations on Manifolds

Projection methods are a standard approach for the numerical solution of differential equations on manifolds. It is known that geometric properties (such as symplecticity or reversibility) are usually destroyed by such a discretization, even when the basic method is symplectic or symmetric. In this article, we introduce a new kind of projection methods, which allows us to recover the time-reversibility, an important property for long-time integrations.     

On the Implementation of the Method of Magnus Series for Linear Differential Equations

The method of Magnus series has recently been analysed by Iserles and Nørsett. It approximates the solution of linear differential equations y = a(t)y in the form y(t) = e ^(t) y ₀, solving a nonlinear differential equation for by means of an expansion in iterated integrals of commutators. An appealing feature of the method is that, whenever the exact solution evolves in a Lie group, so does the numerical solution.The subject matter of the present paper is practical implementation of the method of Magnus series. We commence by briefly reviewing the method and highlighting its connection with graph theory. This is followed by the derivation of error estimates, a task greatly assisted by the graph-theoretical connection. These error estimates have been incorporated into a variable-step fourth-order code. The concluding section of the paper is devoted to a number of computer experiments that highlight the promise of the proposed approach even in the absence of a Lie-group structure.     

Extrapolated Magnus Methods

This paper describes the use of extrapolation with Magnus methods for the solution of a system of linear differential equations. The idea is a generalization of extrapolation with symmetric methods for the numerical solution of ODEs, where each extrapolation step increases the order of the method by 2.This revised version was published online in October 2005 with corrections to the Cover Date.     

About the notion of non‐T‐resonance and applications to topological multiplicity results for ODEs on differentiable manifolds

By using topological methods, mainly the degree of a tangent vector field, we establish multiplicity results for T‐periodic solutions of parametrized T‐periodic perturbations of autonomous ODEs on a differentiable manifold M. In order to provide insights into the key notion of T‐resonance, we consider the elementary situations and . Doing so, we provide more comprehensive analysis of those cases and find improved conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

Lie-Butcher theory for Runge-Kutta methods

Runge-Kutta methods are formulated via coordinate independent operations on manifolds. It is shown that there is an intimate connection between Lie series and Lie groups on one hand and Butcher's celebrated theory of order conditions on the other. In Butcher's theory the elementary differentials are represented as trees. In the present formulation they appear as commutators between vector fields. This leads to a theory for the order conditions, which can be developed in a completely coordinate free manner. Although this theory is developed in a language that is not widely used in applied mathematics, it is structurally simple. The recursion for the order conditions rests mainly on three lemmas, each with very short proofs. The techniques used in the analysis are prepared for studying RK-like methods on general Lie groups and homogeneous manifolds, but these themes are not studied in detail within the present paper.     

Waveform Relaxation Methods for Lie-Group Equations

In this paper, we derive and analyse waveform relaxation (WR) methods for solving differential equations evolving on a Lie-group. We present both continuous-time and discrete-time WR methods and study their convergence properties. In the discrete-time case, the novel methods are constructed by combining WR methods with Runge-Kutta-Munthe-Kaas (RK-MK) methods. The obtained methods have both advantages of WR methods and RK-MK methods, which simplify the computation by decoupling strategy and preserve the numerical solution of Lie-group equations on a manifold. Three numerical experiments are given to illustrate the feasibility of the new WR methods.     

一阶微分方程数值解的一种误差估计方法

针对于微分方程数值解,介绍了一种新的误差估计方法.方法证实了伪谱方法具有精度高速度快的优点,进而引出了修正的伪谱方法.     

Dynamical Systems and Adaptive Timestepping in ODE Solvers

Initial value problems for ODEs are often solved numerically using adaptive timestepping algorithms. These algorithms are controlled by a user-defined tolerance which bounds from above the estimated error committed at each step. We formulate a large class of such algorithms as discrete dynamical systems which are discontinuous and of higher dimension than the underlying ODE. By assuming sufficiently strong finite-time convergence results on some neighbourhood of an attractor of the ODE we prove existence and upper semicontinuity results for a nearby numerical attractor as the tolerance tends to zero.This assumption of sufficiently strong finite-time convergence results is then examined for adaptive algorithms that use a pair of explicit Runge-Kutta methods of different order to estimate the one-step error. For arbitrary Runge-Kutta pairs the necessary finite-time convergence results fail to hold on a set of points in the phase space that includes all the equilibria of the ODE. Therefore, in general, the asymptotic convergence results cannot be applied to attractors containing equilibria. However, for a particular class of Runge-Kutta pairs, the finite-time convergence results can be strengthened to include neighbourhoods of equilibrium points for which the Jacobian is invertible.     

A Parallel Algorithm for the Estimation of the Global Error in Runge–Kutta Methods

The object of this work is the estimate of the global error in the numerical solution of the IVP for a system of ODE's. Given a Runge–Kutta formula of order q, which yields an approximation y _n to the true value y(x _n ), a general, parallel method is presented, that provides a second value y _n ^* of order q+2; the global error e _n =y _n –y(x _n ) is then estimated by the difference y _n –y _n ^*. The numerical tests reported, show the very good performance of the procedure proposed. A comparison with the code GEM90 is also appended.     

On the Global Error of Discretization Methods for Highly-Oscillatory Ordinary Differential Equations

Commencing from a global-error formula, originally due to Henrici, we investigate the accumulation of global error in the numerical solution of linear highly-oscillating systems of the form y+ g(t)y = 0, where g(t) . Using WKB analysis we derive an explicit form of the global-error envelope for Runge-Kutta and Magnus methods. Our results are closely matched by numerical experiments.Motivated by the superior performance of Lie-group methods, we present a modification of the Magnus expansion which displays even better long-term behaviour in the presence of oscillations.     

Algorithms for Computing Characters for Symmetric Spaces

Symmetric spaces or more general symmetric k-varieties can be defined as the homogeneous spaces G _k /K _k , where G is a reductive algebraic group defined over a field k of characteristic not 2, K the fixed point group of an involution θ of G and G _k resp. K _k the sets k-rational points of G resp. K. These symmetric spaces have a fine structure of root systems, characters, Weyl groups etc., similar to the underlying algebraic group G. The relationship between the fine structure of the symmetric space and the group plays an important role in the study of these symmetric spaces and their applications. To develop a computer algebra package for symmetric spaces one needs explicit formulas expressing the fine structure of the symmetric space and group in terms of each other. In this paper we consider the case that k is algebraically closed and give explicit algorithmic formulas for expressing the characters of the weight lattice of the symmetric space in terms of the characters of the weight lattice of the group. These algorithms can easily be implemented in a computer algebra package. The root system of the symmetric space can be described as the image of the root system of the group under a projection π derived from an involution θ on . This implies that . Using these formulas for the characters of each of these lattices we show that in fact . A.G. Helminck is partially supported by N.S.F. Grant DMS-0532140.     

Algorithmic Modality Analysis for Parabolic Groups

For an algebraic group R acting morphically on an algebraic variety X the modality of the action, mod (R:X), is the maximal number of parameters upon which a family of R-orbits on X depends. Let G be a reductive algebraic group defined over an algebraically closed field K. Let P be a parabolic subgroup of G. Then P acts on its unipotent radical P_u via conjugation and on , the Lie algebra of P_u, via the adjoint action. The modality of P is defined as mod P:=mod (P: ). In this paper we discuss an algorithm which is used to compute upper bounds for mod P along with some results obtained by this algorithm. One is a classification of parabolic subgroups P of simple algebraic groups G of semisimple rank 2 and modality 0. For parabolic subgroups of semisimple rank 3 we present some partial results. This extends the results of Kashin and Popov and Röhrle, where the cases of semisimple rank 0 and 1 are handled. For exceptional groups G we show that P G has modality zero provided the class of nilpotency of P_u is at most two. The analogous result for classical groups is proved by Röhrle. For Borel subgroups B of simple groups we are able to determine the value for mod B in some small rank cases by combining lower bounds for mod B of Röhrle with upper bounds provided by the algorithm.     

Algorithms for Computations in Local Symmetric Spaces

In the last two decades much of the algebraic/combinatorial structure of Lie groups, Lie algebras, and their representations has been implemented in several excellent computer algebra packages, including LiE, GAP4, Chevie, Magma, and Maple. The structure of reductive symmetric spaces or more generally symmetric k-varieties is very similar to that of the underlying Lie group, with a few additional complications. A computer algebra package enabling one to do computations related to these symmetric spaces would be an important tool for researchers in many areas of mathematics, including representation theory, Harish Chandra modules, singularity theory, differential and algebraic geometry, mathematical physics, character sheaves, Lie theory, etc.

In this article we lay the groundwork for computing the fine structure of symmetric spaces over the real numbers and other base fields, give a complete set of algorithms for computing the fine structure of symmetric varieties and use this to compute nice bases for the local symmetric varieties.