Jul 17 2017 02:00 UTC

Olivier Verdier published How do nonholonomic integrators work?

A nonholonomic system is a mechanical system with velocity constraints not originating from position constraints: the typical example is rolling motion on a surface without slipping. A nonholonomic integrator is a numerical method specifically designed for nonholonomic systems. Such integrators are often based on discrete versions of the Lagrange--d'Alembert principle. It has been observed numerically that many nonholonomic integrators exhibit excellent long-time behaviour when applied to standard test problems. Here we give a rigorous explanation of this behaviour. In addition, we introduce a new family of nonholonomic problems that have the structure of being foliated over reversible integrable systems. Our study reveals that the standard test problems of nonholonomic mechanics have a bias: they are all reversible integrable. We therefore provide perturbed, unbiased test problems that are integrable but no longer reversible with respect to the standard reversibility map. We give numerical examples on an unbiased test problem using five different nonholonomic integrators; all but one of the tested methods fail to produce good long-time behaviour.

Mar 29 2017 02:00 UTC

Olivier Verdier published Numerical Algorithm for C2-splines on Symmetric Spaces

Cubic spline interpolation on Euclidean space is a standard topic in numerical analysis, with countless applications in science and technology. In several emerging fields, for example computer vision and quantum control, there is a growing need for spline interpolation on curved, non-Euclidean space. The generalization of cubic splines to manifolds is not self-evident, with several distinct approaches. One possibility is to mimic the acceleration minimizing property, which leads to Riemannian cubics. This, however, require the solution of a coupled set of non-linear boundary value problems that cannot be integrated explicitly, even if formulae for geodesics are available. Another possibility is to mimic De~Casteljau's algorithm, which leads to generalized Bézier curves. To construct C2-splines from such curves is a complicated non-linear problem, until now lacking numerical methods. Here we provide an iterative algorithm for C2-splines on Riemannian symmetric spaces, and we prove convergence of linear order. In terms of numerical tractability and computational efficiency, the new method surpasses those based on Riemannian cubics. Each iteration is parallel, thus suitable for multi-core implementation. We demonstrate the algorithm for three geometries of interest: the $n$-sphere, complex projective space, and the real Grassmannian.

Feb 10 2017 02:00 UTC

Olivier Verdier published Currents and finite elements as tools for shape space

The nonlinear spaces of shapes (unparameterized immersed curves or submanifolds) are of interest for many applications in image analysis, such as the identification of shapes that are similar modulo the action of some group. In this paper we study a general representation of shapes that is based on linear spaces and is suitable for numerical discretization, being robust to noise. We develop the theory of currents for shape spaces by considering both the analytic and numerical aspects of the problem. In particular, we study the analytical properties of the current map and the $H^{-s}$ norm that it induces on shapes. We determine the conditions under which the current determines the shape. We then provide a finite element discretization of the currents that is a practical computational tool for shapes. Finally, we demonstrate this approach on a variety of examples.

Jun 07 2016 02:00 UTC

Olivier Verdier published Numerical Study of Nonlinear Dispersive Wave Models with SpecTraVVave

In nonlinear dispersive evolution equations, the competing effects of nonlinearity and dispersion make a number of interesting phenomena possible. In the current work, the focus is on the numerical approximation of traveling-wave solutions of such equations. We describe our efforts to write a dedicated Python code which is able to compute traveling-wave solutions of nonlinear dispersive equations of the general form \beginequation* u_t + [f(u)]_x + \mathcalL u_x = 0, \endequation* where $\mathcal{L}$ is a self-adjoint operator, and $f$ is a real-valued function with $f(0) = 0$. The SpectraVVave code uses a continuation method coupled with a spectral projection to compute approximations of steady symmetric solutions of this equation. The code is used in a number of situations to gain an understanding of traveling-wave solutions. The first case is the Whitham equation, where numerical evidence points to the conclusion that the main bifurcation branch features three distinct points of interest, namely a turning point, a point of stability inversion, and a terminal point which corresponds to a cusped wave. The second case is the so-called modified Benjamin-Ono equation where the interaction of two solitary waves is investigated. It is found that is possible for two solitary waves to interact in such a way that the smaller wave is annihilated. The third case concerns the Benjamin equation which features two competing dispersive operators. In this case, it is found that bifurcation curves of periodic traveling-wave solutions may cross and connect high up on the branch in the nonlinear regime.

May 25 2016 02:00 UTC

Olivier Verdier published Full affine equivariance and weak natural transformations in numerical analysis - the case of B-Series

Many algorithms in numerical analysis are affine equivariant: they are immune to changes of affine coordinates. This is because those algorithms are defined using affine invariant constructions. There is, however, a crucial ingredient missing: most algorithms are in fact defined regardless of the underlying dimension. As a result, they are also invariant with respect to non-invertible affine transformation from spaces of different dimensions. We formulate this property precisely: these algorithms fall short of being natural transformations between affine functors. We give a precise definition of what we call a weak natural transformation between functors, and illustrate the point using examples coming from numerical analysis, in particular B-Series.

Apr 04 2016 02:00 UTC

Olivier Verdier published Extension of Matrix Pencil Reduction to Abelian Categories

Matrix pencils, or pairs of matrices, are used in a variety of applications. By the Kronecker decomposition Theorem, they admit a normal form. This normal form consists of four parts, one part based on the Jordan canonical form, one part made of nilpotent matrices, and two other dual parts, which we call the observation and control part. The goal of this paper is to show that large portions of that decomposition are still valid for pairs of morphisms of modules or abelian groups, and more generally in any abelian category. % This gives a new perspective even in the vector space case, as we have to use radically new proof techniques to work on abelian categories. In the vector space case, we recover the full Kronecker decomposition theorem. The main technique is that of reduction, which extends readily to the abelian category case. Reductions naturally arise in two flavours, which are dual to each other. There are a number of properties of those reductions which extend remarkably from the vector space case to abelian categories. First, both types of reduction commute. Second, at each step of the reduction, one can compute three sequences of invariant spaces (objects in the category), which generalize the Kronecker decomposition into nilpotent, observation and control blocks. These sequences indicate whether the system is reduced in one direction or the other. In the category of modules, there is also a relation between these sequences and the resolvent set of the pair of morphisms, which generalizes the regular pencil theorem. We also indicate how this allows to define invariant subspaces in the vector space case, and study the notion of strangeness as an example.

Dec 16 2015 02:00 UTC

Olivier Verdier published Symmetry reduction for central force problems

We given an elementary illustration of symmetry reduction for central force problems, drawing phase portraits of the reduced dynamics as the intersection of Casimir and energy level sets in three dimensions. These systems form a classic example of symplectic reduction which can usefully be compared to the more-commonly seen case of the free rigid body.

Dec 04 2015 02:00 UTC

Olivier Verdier published Butcher series: A story of rooted trees and numerical methods for evolution equations

Butcher series appear when Runge-Kutta methods for ordinary differential equations are expanded in power series of the step size parameter. Each term in a Butcher series consists of a weighted elementary differential, and the set of all such differentials is isomorphic to the set of rooted trees, as noted by Cayley in the mid 19th century. A century later Butcher discovered that rooted trees can also be used to obtain the order conditions of Runge-Kutta methods, and he found a natural group structure, today known as the Butcher group. It is now known that many numerical methods also can be expanded in Butcher series; these are called B-series methods. A long-standing problem has been to characterize, in terms of qualitative features, all B-series methods. Here we tell the story of Butcher series, stretching from the early work of Cayley, to modern developments and connections to abstract algebra, and finally to the resolution of the characterization problem. This resolution introduces geometric tools and perspectives to an area traditionally explored using analysis and combinatorics.

May 19 2015 02:00 UTC

Olivier Verdier published Geometry of discrete-time spin systems

Classical Hamiltonian spin systems are continuous dynamical systems on the symplectic phase space $(S^2)^n$. In this paper we investigate the underlying geometry of a time discretization scheme for classical Hamiltonian spin systems called the spherical midpoint method. As it turns out, this method displays a range of interesting geometrical features, that yield insights and sets out general strategies for geometric time discretizations of Hamiltonian systems on non-canonical symplectic manifolds. In particular, our study provides two new, completely geometric proofs that the discrete-time spin systems obtained by the spherical midpoint method preserve symplecticity. The study follows two paths. First, we introduce an extended version of the Hopf fibration to show that the spherical midpoint method can be seen as originating from the classical midpoint method on $T^*\mathbf{R}^{2n}$ for a collective Hamiltonian. Symplecticity is then a direct, geometric consequence. Second, we propose a new discretization scheme on Riemannian manifolds called the Riemannian midpoint method. We determine its properties with respect to isometries and Riemannian submersions and, as a special case, we show that the spherical midpoint method is of this type for a non-Euclidean metric. In combination with Kähler geometry, this provides another geometric proof of symplecticity.

Dec 22 2014 02:00 UTC

Olivier Verdier published A classification of volume preserving generating forms in R^3

In earlier work, Lomeli and Meiss used a generalization of the symplectic approach to study volume preserving generating differential forms. In particular, for the $\mathbb{R}^3$ case, the first to differ from the symplectic case, they derived thirty-six one-forms that generate exact volume preserving maps. Xue and Zanna had studied these differential forms in connection with the numerical solution of divergence-free differential equations: can such forms be used to devise new volume preserving integrators or to further understand existing ones? As a partial answer to this question, Xue and Zanna showed how six of the generating volume form were naturally associated to consistent, first order, volume preserving numerical integrators. In this paper, we investigate and classify the remaining cases. The main result is the reduction of the thirty-six cases to five essentially different cases, up to variable relabeling and adjunction. We classify these five cases, identifying two novel classes and associating the other three to volume preserving vector fields under a Hamiltonian or Lagrangian representation. We demonstrate how these generating form lead to consistent volume preserving schemes for volume preserving vector fields in $\mathbb{R}^3$.

Nov 25 2014 02:00 UTC

Olivier Verdier published Multi-symplectic discretisation of wave map equations

We present a new multi-symplectic formulation of constrained Hamiltonian partial differential equations, and we study the associated local conservation laws. A multi-symplectic discretisation based on this new formulation is exemplified by means of the Euler box scheme. When applied to the wave map equation, this numerical scheme is explicit, preserves the constraint and can be seen as a generalisation of the Shake algorithm for constrained mechanical systems. Furthermore, numerical experiments show excellent conservation properties of the numerical solutions.

Sep 04 2014 01:00 UTC

Olivier Verdier published B-series methods are exactly the affine equivariant methods

Butcher series, also called B-series, are a type of expansion, fundamental in the analysis of numerical integration. Numerical methods that can be expanded in B-series are defined in all dimensions, so they correspond to \emphsequences of maps---one map for each dimension. A long-standing problem has been to characterise those sequences of maps that arise from B-series. This problem is solved here: we prove that a sequence of smooth maps between vector fields on affine spaces has a B-series expansion if and only if it is \emphaffine equivariant, meaning it respects all affine maps between affine spaces.

Feb 28 2014 01:00 UTC

Olivier Verdier published Integrators on homogeneous spaces: Isotropy choice and connections

We consider numerical integrators of ODEs on homogeneous spaces (spheres, affine spaces, hyperbolic spaces). Homogeneous spaces are equipped with a built-in symmetry. A numerical integrator respects this symmetry if it is equivariant. One obtains homogeneous space integrators by combining a Lie group integrator with an isotropy choice. We show that equivariant isotropy choices combined with equivariant Lie group integrators produce equivariant homogeneous space integrators. Moreover, we show that the RKMK, Crouch--Grossman or commutator-free methods are equivariant. To show this, we give a novel description of Lie group integrators in terms of stage trees and motion maps, which unifies the known Lie group integrators. We then proceed to study the equivariant isotropy maps of order zero, which we call connections, and show that they can be identified with reductive structures and invariant principal connections. We give concrete formulas for connections in standard homogeneous spaces of interest, such as Stiefel, Grassmannian, isospectral, and polar decomposition manifolds. Finally, we show that the space of matrices of fixed rank possesses no connection.

Feb 18 2014 01:00 UTC

Olivier Verdier published Symplectic integrators for spin systems

We present a symplectic integrator, based on the canonical midpoint rule, for classical spin systems in which each spin is a unit vector in $\mathbb{R}^3$. Unlike splitting methods, it is defined for all Hamiltonians, and is $O(3)$-equivariant. It is a rare example of a generating function for symplectic maps of a noncanonical phase space. It yields an integrable discretization of the reduced motion of a free rigid body.

Feb 15 2014 01:00 UTC

Olivier Verdier published A minimal-variable symplectic integrator on spheres

We construct a symplectic, globally defined, minimal-coordinate, equivariant integrator on products of 2-spheres. Examples of corresponding Hamiltonian systems, called spin systems, include the reduced free rigid body, the motion of point vortices on a sphere, and the classical Heisenberg spin chain, a spatial discretisation of the Landau-Lifschitz equation. The existence of such an integrator is remarkable, as the sphere is neither a vector space, nor a cotangent bundle, has no global coordinate chart, and its symplectic form is not even exact. Moreover, the formulation of the integrator is very simple, and resembles the geodesic midpoint method, although the latter is not symplectic.

Aug 31 2013 01:00 UTC

Olivier Verdier published Collective symplectic integrators

We construct symplectic integrators for Lie-Poisson systems. The integrators are standard symplectic (partitioned) Runge--Kutta methods. Their phase space is a symplectic vector space with a Hamiltonian action with momentum map $J$ whose range is the target Lie--Poisson manifold, and their Hamiltonian is collective, that is, it is the target Hamiltonian pulled back by $J$. The method yields, for example, a symplectic midpoint rule expressed in 4 variables for arbitrary Hamiltonians on $\mathfrak{so}(3)^*$. The method specializes in the case that a sufficiently large symmetry group acts on the fibres of $J$, and generalizes to the case that the vector space carries a bifoliation. Examples involving many classical groups are presented.

Aug 28 2013 01:00 UTC

Olivier Verdier published Aromatic Butcher Series

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.

Jul 10 2013 01:00 UTC

Olivier Verdier published Collective Lie-Poisson integrators on $\mathbf{R}^{3}$

We develop Lie-Poisson integrators for general Hamiltonian systems on $\mathbf{R}^{3}$ equipped with the rigid body bracket. The method uses symplectic realisation of $\mathbf{R}^{3}$ on $T^{*}\mathbf{R}^{2}$ and application of symplectic Runge-Kutta schemes. As a side product, we obtain simple symplectic integrators for general Hamiltonian systems on the sphere $S^{2}$.

Jan 01 2013 01:00 UTC

Olivier Verdier published Integrability of Nonholonomically Coupled Oscillators

We study a family of nonholonomic mechanical systems. These systems consist of harmonic oscillators coupled through nonholonomic constraints. In particular, the family includes the so called contact oscillator, which has been used as a test problem for numerical methods for nonholonomic mechanics. Furthermore, the systems under study constitute simple models for continuously variable transmission gearboxes. The main result is that each system in the family is integrable reversible with respect to the canonical reversibility map on the cotangent bundle. This result may explain previous numerical observations, that some discretisations of the contact oscillator have favourable structure preserving properties.

Aug 16 2012 01:00 UTC

Olivier Verdier published Reductions of Operator Pencils

We study problems associated with an operator pencil, i.e., a pair of operators on Banach spaces. Two natural problems to consider are linear constrained differential equations and the description of the generalized spectrum. The main tool to tackle either of those problems is the reduction of the pencil. There are two kinds of natural reduction operations associated to a pencil, which are conjugate to each other. Our main result is that those two kinds of reductions commute, under some mild assumptions that we investigate thoroughly. Each reduction exhibits moreover a pivot operator. The invertibility of all the pivot operators of all possible successive reductions corresponds to the notion of regular pencil in the finite dimensional case, and to the inf-sup condition for saddle point problems on Hilbert spaces. Finally, we show how to use the reduction and the pivot operators to describe the generalized spectrum of the pencil.

Jul 24 2012 01:00 UTC

Olivier Verdier published High order semi-Lagrangian methods for the incompressible Navier-Stokes equations

We propose a class of semi-Lagrangian methods of high approximation order in space and time, based on spectral element space discretizations and exponential integrators of Runge-Kutta type. We discuss the extension of these methods to the Navier-Stokes equations, and their implementation using projections. Semi-Lagrangian methods up to order three are implemented and tested on various examples. The good performance of the methods for convection-dominated problems is demonstrated with numerical experiments.

Jul 19 2012 01:00 UTC

Olivier Verdier published Symplectic integrators for index one constraints

We show that symplectic Runge-Kutta methods provide effective symplectic integrators for Hamiltonian systems with index one constraints. These include the Hamiltonian description of variational problems subject to position and velocity constraints nondegenerate in the velocities, such as those arising in sub-Riemannian geometry and control theory.

Jul 17 2012 01:00 UTC

Olivier Verdier published Geometric Generalisations of SHAKE and RATTLE

A geometric analysis of the Shake and Rattle methods for constrained Hamiltonian problems is carried out. The study reveals the underlying differential geometric foundation of the two methods, and the exact relation between them. In addition, the geometric insight naturally generalises Shake and Rattle to allow for a strictly larger class of constrained Hamiltonian systems than in the classical setting. In order for Shake and Rattle to be well defined, two basic assumptions are needed. First, a nondegeneracy assumption, which is a condition on the Hamiltonian, i.e., on the dynamics of the system. Second, a coisotropy assumption, which is a condition on the geometry of the constrained phase space. Non-trivial examples of systems fulfilling, and failing to fulfill, these assumptions are given.

May 08 2012 01:00 UTC

Olivier Verdier published Reduction and Normal Forms of Matrix Pencils

Matrix pencils, or pairs of matrices, may be used in a variety of applications. In particular, a pair of matrices (E,A) may be interpreted as the differential equation E x' + A x = 0. Such an equation is invariant by changes of variables, or linear combination of the equations. This change of variables or equations is associated to a group action. The invariants corresponding to this group action are well known, namely the Kronecker indices and divisors. Similarly, for another group action corresponding to the weak equivalence, a complete set of invariants is also known, among others the strangeness. We show how to define those invariants in a directly invariant fashion, i.e. without using a basis or an extra Euclidean structure. To this end, we will define a reduction process which produces a new system out of the original one. The various invariants may then be defined from operators related to the repeated application of the reduction process. We then show the relation between the invariants and the reduced subspace dimensions, and the relation with the regular pencil condition. This is all done using invariant tools only. Making special choices of basis then allows to construct the Kronecker canonical form. In a related manner, we construct the strangeness canonical form associated to weak equivalence.

May 04 2012 01:00 UTC

Olivier Verdier published Time-Periodic Solutions of the Burgers Equation

We investigate the time periodic solutions to the viscous Burgers equation $u_t -\mu u_{xx} + uu_x = f$ for irregular forcing terms. We prove that the corresponding Burgers operator is a diffeomorphism between appropriate function spaces.