betaFeedback

WorksMathematics

Accurate and Efficient Simulations of Hamiltonian Mechanical Systems with Discontinuous Potentials

Abstract

This article considers Hamiltonian mechanical systems with potential functions admitting jump discontinuities. The focus is on accurate and efficient numerical approximations of their solutions, which will be defined via the laws of reflection and refraction. Despite of the success of symplectic integrators for smooth mechanical systems, their construction for the discontinuous ones is nontrivial, and numerical convergence order can be impaired too. Several rather-usable numerical methods are proposed, including: a first-order symplectic integrator for general problems, a third-order symplectic integrator for problems with only one linear interface, arbitrarily high-order reversible integrators for general problems (no longer symplectic), and an adaptive time-stepping version of the previous high-order method. Interestingly, whether symplecticity leads to favorable long time performance is no longer clear due to discontinuity, as traditional Hamiltonian backward error analysis does not apply any more. Therefore, at this stage, our recommended default method is the last one. Various numerical evidence, on the order of convergence, long time performance, momentum map conservation, and consistency with the computationally-expensive penalty method, are supplied. A complex problem, namely the Sauteed Mushroom, is also proposed and numerically investigated, for which multiple bifurcations between trapped and ergodic dynamics are observed.

Dedicated to the centenary of the birth of Kang Feng

Introduction

The developments of accurate and efficient integrators for simulating smooth Hamiltonian mechanical systems, as well as the associated theoretical analysis, have been a major triumph of contemporary numerical analysis (see e.g., [34, 72, 23, 56, 4]). Symplectic integrators (e.g., [22, 73]), for instance, are a celebrated class of numerical methods suitable for such systems. For example, explicit symplectic integrators have been constructed, with arbitrarily high-order versions for both separable Hamiltonians (e.g., [15, 26, 80, 87]) and general, non-separable Hamiltonians [82]. Their explicitness and the ability to use relatively large timesteps lead to computationally efficient simulations (for stiff/multiscale problems, see also, e.g., [28, 74, 85, 84]), and the high-orderness, which has mostly been achieved by a powerful technique known as the splitting method (e.g., [63] for a review), yields high accuracy at least for short-time simulations. Moreover, favorable long-time properties of symplectic integrators have also been proved, including linear growth of error (for integrable systems, e.g., [10, 71]), near preservation of energy (e.g., [3]), and conservation of momentum maps associated with symmetries (e.g., [62]). Central to many of these beautiful analyses is what is nowadays known as (Hamiltonian) backward error analysis (e.g., [34]). It views the iterations of a symplectic integrator as stroboscopic samples of the solution of a near-by Hamiltonian system, which is to be found and hopefully close to the original Hamiltonian. In addition, also worth noting is another class of useful methods for structured continuous systems, namely reversible integrators. This class often overlaps with symplectic integrators, although they are not always the same, and for them one can also establish long term accuracy via (reversible) backward error analysis under reasonable assumptions (see Chap.XI of [34]).

On the other hand, if the potential of a mechanical system has discontinuity, each corresponding to a potential barrier1, most aforementioned results no longer hold. Even the sense in which one discusses the solution has to be defined, because the standard equations of motion known as the (canonical) Hamilton’s equation (i.e. q˙=∂H/∂p\dot{q} = \partial H/\partial p, p˙=−∂H/∂q\dot{p} = -\partial H/\partial q) is ill-defined due to indifferentiability of V(q)V(q). Following [45, 40] (and also its higher-dimensional extension to curved interfaces [41], for Hamiltonian systems with discontinuous Hamiltonians [48], as well as an earlier such approach for well-balanced schemes for the shallow-water equations [70]), we will define a solution based on physical principle, or more precisely, using the classical idea of particle refraction and reflection (used in optics and derived rigorously from Maxwell’s equation [39]). See Figure 1 for a simplified illustration and Figure 2 for a more general case. This definition will be numerically shown (§ 5.1 and 4.3) to be consistent with an alternative treatment termed as the penalty method (see § 2.1 for a brief discussion of the penalty method), which was also observed in [47], but with improved efficiency and accuracy.

Toy 1D illustration of reflection and refraction at a discontinuous barrier

Figure 1. Toy 1D illustration of the dichotomy of reflection and refraction: whether the particle goes through a discontinuous barrier depends on if it has enough kinetic energy to overcome it. In 1D, this is a consequence of energy conservation. Arrow size indicates the magnitude of momentum.

Figure 2. Two ways in which an impact can change the momentum, 2D illustration.

In the previous works [45, 48], the proposed schemes were in general neither symplectic nor of high order accuracy. In fact, since the so-defined solution will exhibit discontinuity, in particular in the momentum variable, as a response to the discontinuity in the potential, these two discontinuities make the construction of a symplectic integrator, or even just a reversible integrator, nontrivial. Designing high-order methods becomes even more challenging, as the splitting approach for boosting the convergence order will be shown no longer effective due to the discontinuity. Moreover, backward error analysis, either the one for symplectic integrators or the one for reversible integrators, fails as well, and long time performance guarantees are not proved any more.

In order to improve the numerical simulation for such singular Hamiltonian systems, we propose four numerical methods, each specializing in certain tasks. See Table 1. Properties of these methods are numerically studied in Sec. 4, such as convergence order (§ 5.1&§ 5.2), long time accuracy (§ 5.1,§ 5.2,§ 5.3), and the conservation of momentum map due to symmetry (§ 5.3).

sectionsymplectic?reversible?#global error*other feature(s)
3.1YesYes1st-ordergeneral
3.3YesYes3rd-order1 linear interface† only
3.4NoYesarbitrarygeneral
3.5NoYesarbitrarygeneral; adaptive time-stepping

Table 1. A brief summary of numerical methods proposed in this article.

: the more precise question is whether the integrator can be made reversible.

  • : global error considered here is that of position, away from interface interceptions. † : a linear interface is a co-dimension 1 hyperplane of discontinuities in the potential.

Related work

‘Nonsmooth mechanics’. A rich field termed ‘nonsmooth mechanics’ / ‘nonsmooth Hamiltonian systems’ / ‘mechanical systems with hard constraints’ / ‘unilaterally constrained systems’ / ‘contact integrators’ / ‘collision integrators’ already exists (e.g., [78, 64, 36, 79, 54, 50, 38, 76, 55, 68, 24, 13, 7, 16, 52, 21, 69, 53, 51, 17, 58]). Problems considered there correspond to a special case of this study.

More precisely, to the best of our knowledge, these literature mainly consider, in the language of this article, a discontinuous potential barrier of height +∞+\infty, so that trajectories can only stay within the finite potential region2. This setup is already very important in engineering and science applications; for example, in robotics, the interested mechanical object is often interacting with hard surfaces – think about a bipedal robot that walks by frequently impacting the ground (e.g., [31]), and in molecular and polymer dynamics molecules are sometimes viewed as hard spheres (so that they remain at least a certain distance from each other; e.g., [19]). However, in these cases, the boundary manifold (i.e., the interface(s)) cannot be crossed, and one will only have reflections but never refractions. Therefore, those interactions with the interface were commonly called in the literature ‘contacts’ and ‘collisions’.

On the contrary, the setup in [45, 48], which is adopted in this article, allows finite discontinuous jumps, and therefore the full dichotomy of reflection and refraction can both manifest in the dynamics.

In addition to this main difference, here are some more details on other aspects in which this research compares with the existing works in nonsmooth mechanics (all for +∞+\infty jump only): One objective of this article is to develop explicit symplectic integrators. Some pioneering breakthroughs developed symplectic integrators which are however implicit (e.g., [24, 58]). An intriguing paper [51] also noted that if one relaxes the symplecticity requirement and instead only requires symplecticity over smooth trajectories intervals, then it is possible to obtain better energy behaviors. This also reminds us of an inspiring and clever earlier work [7], which uses backward error analysis for continuous systems to design stabilized event-driven collision integrator. In addition, there is a collection of substantial works based on finite element (e.g., [50, 52, 13, 21]). Although inevitably incapable of discussing all results in the rich ‘+∞+\infty jump’ field, we also mention the relevant paper [17] in the context of symplectic integrator. Its main goal is to simulate smooth potentials, but it approximates the smooth potential by a piecewise constant or quadratic function and uses analytically obtained solution of the nonsmooth approximation as a numerical solution. What is new in this paper, in comparison, is we will have a continuous part of the potential in addition to this piecewisely-defined discontinuous part.

Penalty method / regularization. A popular idea commonly known as regularization/regularisation corresponds to modifying the discontinuous vector field of a differential equation and replacing its discontinuities by steep but continuous transitions. After the regularization both the equations of motion and the solution become well-defined. The hope is to recover the original dynamics as the steepness goes to infinity. This idea was proved to be very useful, for example, in engineering applications (e.g., [30]). It should be pointed out, however, that regularization generally creates artificial numerical stiffness (see two paragraphs below), and caution should be exercised even without considering numerics, as regularization doesn’t always guarantee a good, or even correct, approximation. In fact, general discontinuous problems may not even have unique solutions (e.g., [25, 18]), and [67], for example, provides a mathematical discussion on when regularization actually removes this ambiguity (we also refer to the notion of renormalized solution [20, 2], which is another way of removing ambiguity, not via regularization though). Also, regularization isn’t always possible (e.g., [61]). Furthermore, in the case of geometric optics through an interface, an arbitrary smoothing of the interface could lead to incorrect (partial) transmission and reflection rates [46]. Profound analyses exist and provide sufficient conditions for effective regularization (e.g., [27, 60, 59, 86, 61]), however only for several subclasses of problems.

The setup in this article is also just a subclass, because we only consider Newtonian mechanical systems and only the potential is discontinuous. In some sense this produces a higher-order singularity in the problem than what the previous paragraph discussed, as the forcing term in the ‘vector field’ will become not just discontinuous but Dirac. It is natural to interpret regularization in this case to be the (sufficiently differentiable) regularization of the potential function instead of the vector field. This idea appeared, for example, in the ‘softening’ of gravitational potential (e.g., [1]). Again, such regularization can work very well for specific scientific investigations, but its general validity is not warranted (e.g., [29] for an empirical example).

Focusing directly on the discontinuous problem, this article bares no ambition of investigating the general validity of regularized potentials, but only uses their numerical simulations as one of few available methods to compare to. We will simulate the regularized Hamiltonians using classical smooth symplectic integrators and use the numerical solutions as approximations of the discontinuous solutions. This approach will be called the penalty method thereafter. The specific form of regularization used in our experiments is based on sigmoid function (e.g., eq. (12),(13)), and for these examples, the regularized dynamics do appear to be a good approximation of our definition of the exact (discontinuous) solution. We conjecture the accuracy of this approximation to be O(1/α)+O((αh)p)O(1/\alpha) + O((\alpha h)^p), away from time points of interface crossing, if generic integrators are used (for some non-generic stiff integrators, see e.g., [8, 83], but their error bounds in this case are unclear yet). Here α\alpha is the steepest parameter that should go to ∞\infty, and hh and pp are respectively the step size and order of the smooth integrator used in the penalty method. One can see that the artificial stiffness created by the regularization poses a strong constraint on the step size, which renders the penalty method computationally inefficient; such severe time-step constraints were already known (e.g., [47]). Our proposed discontinuous integrators, on the other hand, do not have this restriction.

The definition of an exact solution

The setup of the problem

Consider a Newtonian mechanical system in a 2d2d-dimensional Euclidean phase space, whose potential function has jump discontinuities across interfaces. Assuming the location and size of each discontinuity is known, then the potential can be decomposed as the sum of a continuous part and a piecewise constant part. Assume also that the continuous part is two-times continuously differentiable. That is, formally, the system is governed by a Hamiltonian3

H(q,p)=12pTp+V(q)+U(q),(1)H(q,p) = \frac{1}{2}p^{T}p + V(q) + U(q), \tag*{(1)}

where U(⋅)U(\cdot) is a C2C^{2} function, and V(q)=ViV(q)=V_i for some constant ViV_i when q∈Diq \in D_i. DiD_i’s for i=1,…,Mi=1,\ldots,M are open sets whose closure form a partition of the configuration space Rd\mathbb{R}^{d}. Let

Bij={Di‾∩Dj‾,i≠j∅,i=jB_{ij} = \begin{cases} \overline{D_i} \cap\overline{D_j}, & i \ne j \\ \varnothing, & i=j \end{cases}

denote the discontinuity interfaces and assume they are either empty or 1-codimensional C1C^{1} submanifolds.

Exact solution via physical laws of reflection and refraction

Due to the non-differentiability of V(⋅)V(\cdot), Hamilton’s equation can no longer be used to describe the (meta)particle’s global motion. Nevertheless, one can turn to mechanical behavior of particles at the interface to define the solution, as proposed in [45, 48, 40] (for curved interface in high dimension see [41]): basically, in order for the solution to make sense physically, a corresponding particle should simply evolve locally according to the smooth Hamiltonian dynamics given by H^=12pTp+U(q)\hat{H}=\frac{1}{2}p^{T}p+U(q), until it hits an interface, and then the particle will either reflect or refract instantaneously, depending on the normal momentum magnitude and whether the jump in VV corresponds to a potential barrier or dip across the interface. Then the particle evolves again locally in some DiD_i according to H^\hat{H}, until the next interface hitting.

More precisely, under nontrivial but not too restrictive assumptions (see Conditions 1 and 2), the solution will be well-defined as an alternation between two phases, flow and impact, which will now be detailed. To do so, denote by ϕt\phi^{t} the time-tt-flow map of H^\hat{H}, and by QQ the operator that projects [q,p][q,p] to the qq-component. Let t0t_0 be the initial time of evolution, and let it0i_{t_0} be the integer such that the initial condition satisfies q(t0)∈Dit0q(t_0)\in D_{i_{t_0}} (note: if the initial condition is on an interface, it0i_{t_0} is not unique, and its choice needs to be specified as part of the initial condition). The next hitting time is defined to be

tk+1=tk+min⁡j=1,…,Minf⁡{δ∣δ>0, Q∘ϕδ[q(tk),p(tk)]∈Bit0j}.t_{k+1}=t_k+\min_{j=1,\ldots,M}\inf\left\{\delta\mid\delta>0,\ Q\circ\phi^{\delta}[q(t_k),p(t_k)]\in B_{i_{t_0}j}\right\}.

let

itk+1=arg⁡min⁡j=1,…,M inf⁡{δ∣δ>0, Q∘ϕδ[q(tk),p(tk)]∈Bit0j},i_{t_{k+1}}=\underset{j=1,\ldots,M}{\arg\min}\ \inf\left\{\delta\mid\delta>0,\ Q\circ\phi^{\delta}[q(t_k),p(t_k)]\in B_{i_{t_0}j}\right\},

and let the solution on time interval [tk,tk+1][t_k,t_{k+1}] be defined by

[q(tk+δ),p(tk+δ)]=ϕδ[q(tk),p(tk)],0≤δ≤tk+1−tk.[q(t_k+\delta),p(t_k+\delta)]=\phi^{\delta}[q(t_k),p(t_k)], \qquad0\leq\delta\leq t_{k+1}-t_k.

This gives one of the two phases of the solution, which shall be called flow.

Remark 2.1. It is easy to see flow preserves both (i) the differentiable part of the total energy, H^\hat{H}, and (ii) the total energy HH as long as time points tkt_k and tk+1t_{k+1} are not considered (on which VV is ill-defined).

After flow, the other phase, called impact, will take place (unless tk+1=∞t_{k+1} = \infty). To define impact, let n^\hat{n} be the unit normal vector of the interface Bitkitk+1B_{i_{t_k}i_{t_{k+1}}} at q(tk+1)q(t_{k+1}), in the direction of from DitkD_{i_{t_k}} to Ditk+1D_{i_{t_{k+1}}}. Decompose the pre-impact momentum as p(tk+1)=pk+1t+pk+1np(t_{k+1}) = p^t_{k+1} + p^n_{k+1}, where pk+1n=(p(tk+1)⋅n^)n^p^n_{k+1} = (p(t_{k+1}) \cdot\hat{n})\hat{n} is the projection onto the normal direction. Let ΔV=Vtk+1−Vtk\Delta V = V_{t_{k+1}} - V_{t_k}.

If the particle has enough normal momentum to transmit through the interface, i.e.,

∥pk+1n∥2/2≥ΔV,\lVert p^n_{k+1}\rVert^2/2 \ge\Delta V,

a refraction will happen in the sense that the post-impact normal momentum will be reduced, and the value of p(tk+1)p(t_{k+1}) will be overwritten by conservation of energy and tangential momentum:

p(tk+1)=pk+1t+∥pk+1n∥2−2ΔVn^.(2)p(t_{k+1}) = p^t_{k+1} + \sqrt{\lVert p^n_{k+1}\rVert^2 - 2\Delta V}\hat{n}. \tag*{(2)}

If there is not enough normal momentum on the other hand, i.e.,

∥pk+1n∥2/2<ΔV,\lVert p^n_{k+1}\rVert^2/2 < \Delta V,

a reflection will take place in the sense that the post-impact normal momentum will simply change its sign, and the value of p(tk+1)p(t_{k+1}) will be overwritten by

p(tk+1)=pk+1t−pk+1n.(3)p(t_{k+1}) = p^t_{k+1} - p^n_{k+1}. \tag*{(3)}

However, in both cases, the value of the position, q(tk+1)q(t_{k+1}), will remain unchanged. An illustration of refraction and reflection is provided in Figure 2.

After impact, which is instantaneous in time (at tk+1t_{k+1}), the solution will be continued by flow again, and these two types of behaviors alternate.

Remark 2.2. Unlike flow which produces continuous trajectories, impact creates discontinuities in pp (qq is still continuous).

Remark 2.3. It is not very meaningful to state if impact conserves the total energy, because it is an instantaneous change of momentum, and at the impact, the position q(tk+1)q(t_{k+1}) is on an interface where V(⋅)V(\cdot) is undefined. However, if one considers the composition of an infinitesimal-time pre-impact flow, the impact, and another infinitesimal-time post-impact flow, then the composed map conserves the total energy HH.

Important to mention is, the above definition of the exact solution requires two conditions, namely:

Condition 1. In the interested time horizon, the interface hitting position of the solution, q(tk+1)q(t_{k+1}), only belongs to one interface Bitkitk+1B_{i_{t_k}i_{t_{k+1}}} for each kk. For example, the rare situation of an impact at the intersection of three pieces illustrated in Figure 3 is assumed to never happen, because in this case there is no unique way of defining the post-impact momentum.

Figure 3. Ambiguity in post-impact momentum due to multiple-interface intersection.

Condition 2. For any tt in the interested time horizon such that the aforedefined q(t)q(t) belongs to some interface BijB_{ij}, we have p(t)∉Tq(t)Bijp(t) \notin T_{q(t)}B_{ij}. That is, sliding along an interface for a nonzero amount of time is assumed to never happen.

Remark 2.4. Because the discontinuity in our problem is in the scalar-valued potential V(⋅)V(\cdot) instead in the vector field, we do not face challenges such as sliding motion in Filippov systems (e.g., [25, 57, 18]), and defining a solution is easier.

If Cond.2 is not satisfied, i.e., sliding along an interface occurs, one needs to use Geometrical Theory of Diffraction; see [49].

It is unclear, however, how to relax Condition 1 in a deterministic way. We feel that how to define a unique deterministic solution when Condition 1 fails will be problem dependent and requiring additional information about how the problem is set up. On the other hand, it is possible to define a stochastic solution by mimicking quantum mechanics; this is beyond the scope of the current work.

Analytical solution for the quadratic case

When the local Hamiltonian H^=12pTp+U(q)\widehat{H} = \frac{1}{2}p^{T}p + U(q) is integrable, the exact flow of the full problem H=H^+V(q)H = \widehat{H} + V(q) is obtainable. As an example, this subsection will consider the case where UU is quadratic, and its exact solution will be used later for two purposes: (i) as part of a numerical algorithm (§ 4.3), and (ii) as a benchmark for assessing numerical accuracy (§ 5.1).

For simplicity, consider one degree-of-freedom problems. Assume without loss of generality that VV corresponds to only 1 interface, i.e.,

U(q)=ω2(q−qoff)2/2,V(q)={ΔV,q>qjump0,q<qjumpundefined,q=qjump(4)U(q) = \omega^{2}(q-q_{\mathrm{off}})^{2}/2,\qquad V(q) = \begin{cases} \Delta V, & q > q_{\mathrm{jump}} \\ 0, & q < q_{\mathrm{jump}} \\ \text{undefined}, & q = q_{\mathrm{jump}} \end{cases} \tag*{(4)}

where ω\omega, qoffq_{\mathrm{off}}, qjumpq_{\mathrm{jump}}, ΔV\Delta V are constant scalar parameters.

Let q,pq,p denote the current position and momentum, and let Q,PQ,P denote those after time hh. Assume hh is small enough such that the interface is encountered at most once in time hh (if hh is large, break it into smaller time lapses and iterate the following). Q,PQ,P can be obtained in the following way: compute a position proposal: q~=qoff+cos⁡(ωh)(q−qoff)+sin⁡(ωh)p/ω\tilde{q}=q_{\mathrm{off}}+\cos(\omega h)(q-q_{\mathrm{off}})+\sin(\omega h)p/\omega, which corresponds to the new position when no interface crossing happens;

if (q−qjump)(q~−qjump)<0(q-q_{\mathrm{jump}})(\tilde{q}-q_{\mathrm{jump}})<0, i.e., interface is crossed, then

compute p^\hat{p} the pre-impact momentum: p^=σω2(q−qoff)2+p2−ω2(qjump−qoff)2\hat{p}=\sigma\sqrt{\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}-\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2}}, where σ=−1\sigma=-1 if q−qjump>0q-q_{\mathrm{jump}}>0 and σ=1\sigma=1 if q−qjump<0q-q_{\mathrm{jump}}<0;

compute tt the time to impact: let t1=atan2⁡(p^/ω,qjump−qoff)−atan2⁡(p/ω,q−qoff)t_{1}=\operatorname{atan2}(\hat{p}/\omega,q_{\mathrm{jump}}-q_{\mathrm{off}})-\operatorname{atan2}(p/\omega,q-q_{\mathrm{off}}),

t2={t1if t1≥0,t1+2πif t1<0,t_{2}=\begin{cases}t_{1} & \text{if }t_{1}\geq0,\\ t_{1}+2\pi& \text{if }t_{1}<0,\end{cases} and t=(2π−t2)/ωt=(2\pi-t_{2})/\omega;

use post-impact position qˉ=qjump\bar{q}=q_{\mathrm{jump}} and compute post-impact momentum pˉ\bar{p}:

if q−qjump<0q-q_{\mathrm{jump}}<0, i.e. crossing is from left to right, then

if ω2(q−qoff)2+p2>2ΔV+ω2(qjump−qoff)2\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}>2\Delta V+\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2} then

pˉ=ω2(q−qoff)2+p2−2ΔV−ω2(qjump−qoff)2\bar{p}=\sqrt{\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}-2\Delta V-\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2}}, i.e., refraction;

else

pˉ=−ω2(q−qoff)2+p2−ω2(qjump−qoff)2\bar{p}=-\sqrt{\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}-\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2}}, i.e., reflection;

end

else

if ω2(q−qoff)2+p2>−2ΔV+ω2(qjump−qoff)2\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}>-2\Delta V+\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2} then

pˉ=−ω2(q−qoff)2+p2+2ΔV−ω2(qjump−qoff)2\bar{p}=-\sqrt{\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}+2\Delta V-\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2}}, i.e., refraction;

else

pˉ=ω2(q−qoff)2+p2−ω2(qjump−qoff)2\bar{p}=\sqrt{\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}-\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2}}, i.e., reflection;

end

end

Q=qoff+cos⁡(ω(h−t))(qˉ−qoff)+sin⁡(ω(h−t))pˉ/ωQ=q_{\mathrm{off}}+\cos(\omega(h-t))(\bar{q}-q_{\mathrm{off}})+\sin(\omega(h-t))\bar{p}/\omega,

P=−ωsin⁡(ω(h−t))(qˉ−qoff)+cos⁡(ω(h−t))pˉP=-\omega\sin(\omega(h-t))(\bar{q}-q_{\mathrm{off}})+\cos(\omega(h-t))\bar{p}, i.e., flow tt-time after impact.

else

Q=qoff+cos⁡(ωh)(q−qoff)+sin⁡(ωh)p/ωQ=q_{\mathrm{off}}+\cos(\omega h)(q-q_{\mathrm{off}})+\sin(\omega h)p/\omega,

P=−ωsin⁡(ωh)(q−qoff)+cos⁡(ωh)pP=-\omega\sin(\omega h)(q-q_{\mathrm{off}})+\cos(\omega h)p, i.e., no impact, flow hh-time only;

end

The numerical methods

A first-order in position time-reversible symplectic integrator

A symplectic integrator for (1) can be constructed via the approach of Hamiltonian splitting and composition [34].

More precisely, denote by ϕ1δ\phi_{1}^{\delta} the δ\delta-time flow of the Hamiltonian H1=U(q)H_{1}=U(q), and by ϕ2δ\phi_{2}^{\delta} the δ\delta-time flow of H2=12pTp+V(q)H_{2}=\frac{1}{2}p^{T}p+V(q). Although the exact flow of HH, ϕδ\phi^{\delta}, is generally not numerically obtainable, the actions of ϕ1δ\phi_{1}^{\delta} and ϕ2δ\phi_{2}^{\delta} can be exactly obtained in explicit forms. Then appropriate compositions of ϕ1\phi_{1} and ϕ2\phi_{2} (e.g., Integrator 1) will provide symplectic approximations of ϕ\phi with vanishing error as δ→0\delta\to0. More specifically, ϕ1\phi_1 is easy to evaluate:

ϕ1δ:[q,p]↦[q,p−δ∇U(q)](5)\phi_1^\delta: [q,p] \mapsto[q,p-\delta\nabla U(q)] \tag*{(5)}

On the other hand, ϕ2δ[q,p]\phi_2^\delta[q,p] can be obtained by evolving the exact flow of H2H_2 for δ\delta-time. Section 2.2 described how to do so by alternating flow and impact phases. In fact, ϕ2\phi_2 is analytically computable, because H2H_2 does not contain the nonlinear potential U(⋅)U(\cdot), and each flow phase simply corresponds to free drift in a straight line. Therefore, the only nontrivial parts for evaluating ϕ2\phi_2 are (i) to compute, given q,pq,p vectors, how much time a particle at position qq with momentum (same as velocity) pp first hits one of the known interfaces, and (ii) to alter the momentum afterwards. How to compute the first hitting time depends on how the interfaces is provided in the problem setup.

The demonstrative case in which the interface geometry is analytically known. In this case, we can always find an affine transformation of qq and an associated linear transformation of pp (for making the transformation of both qq and pp canonical), such that pp is rotated to align with the xx-axis, qq is on the xx-axis, and the relevant interface4 passes through the origin; denote the unit tangent vector of the interface at origin by t^\hat{t}. Then [Q,P]=ϕ2δ[q,p][Q,P] = \phi_2^\delta[q,p] will be given by the following steps: first, let

τ=−q/p,(6)\tau= -q/p, \tag*{(6)}

where the division is understood as a ratio between their xx-components; τ\tau is the time to hit the interface. If τ>δ\tau> \delta or τ<0\tau< 0, i.e., no impact within this step, then let

Q=q+δp,P=p(7)Q = q+\delta p,\qquad P=p \tag*{(7)}

and ϕ2\phi_2 computation is completed; otherwise, let

qa=0,pa=p(8)q_a=0,\qquad p_a=p \tag*{(8)}

be the result of the pre-impact flow, let

pat=(pa⋅t^)t^,andpan=pa−patp_{at}=(p_a\cdot\hat{t})\hat{t},\qquad\text{and}\qquad p_{an}=p_a-p_{at}

be the tangential and normal components of the incident momentum at the interface, denote by ΔV=(V(0−)−V(0+))sgn⁡(x^⋅q)\Delta V=(V(0^-)-V(0^+))\operatorname{sgn}(\hat{x}\cdot q) the potential jump across the interface, let

qb=0,pb={pat−pan∥pan∥2/2<ΔVpat+pan∥pan∥∥pan∥2−2ΔV∥pan∥2/2>ΔV(9)q_b=0,\qquad p_b= \begin{cases} p_{at}-p_{an} & \lVert p_{an}\rVert^2/2<\Delta V\\ p_{at}+\dfrac{p_{an}}{\lVert p_{an}\rVert}\sqrt{\lVert p_{an}\rVert^2-2\Delta V} & \lVert p_{an}\rVert^2/2>\Delta V \end{cases} \tag*{(9)}

be the result of impact (the first case is reflection and the second refraction), and let

Q=(δ−τ)pb,P=pb(10)Q=(\delta-\tau)p_b,\qquad P=p_b \tag*{(10)}

be the result of the post-impact flow. The result of ϕ2δ\phi_2^\delta will be Q,PQ, P.

It is not difficult to see that the same calculation works in general coordinate systems as long as the interface geometries are simple enough such that the first hitting time τ\tau is a computable function of qq and pp.

When the interface geometry is too complex to be explicitly and analytically characterized, τ\tau can be numerically computed to machine precision rapidly. See § 4.2 for details when interfaces are provided by either (i) level sets of C1C^1 functions, or (ii) discontinuous V(⋅)V(\cdot) values.

Two additional comments. Necessary to further clarify is, in order to have guaranteed accuracy of our numerical methods, δ\delta needs to be sufficiently small, not only for controlling the error of the composition, but also for ensuring there is at most one impact per δ\delta-sized time step. We will also describe a numerical method that can account for multiple impacts per step; however, whether all impacts within a step can be detected depends on how interfaces are provided. If the numerical algorithms in § 4.2 need to be used, there is no guarantee on the capture of the earliest impact if δ\delta is too large.

It is also notable that although the above description of ϕ2δ\phi_2^\delta evaluation might appear ‘discrete’, it is exact. In practice, of course, its accuracy will be limited by the machine precision. It is possible to algorithmically alleviate some limitation of machine precision and we refer to the innovative idea in [37], but in this article we will equate ‘accurate to machine precision’ with ‘exact’.

As the explicit evaluations of ϕ1\phi_1 and ϕ2\phi_2 are obtained, a numerical integrator can be constructed by composing these maps. The method proposed in this section is a one-step method that uses a constant step size of δ\delta and a one-step update given by

Integrator 1 (1st-order in position, time-reversible, symplectic). Use one step update

[qn+1,pn+1]=ϕ1δ/2∘ϕ2δ∘ϕ1δ/2[qn,pn],[q_{n+1},p_{n+1}] = \phi_1^{\delta/2} \circ\phi_2^\delta\circ\phi_1^{\delta/2}[q_n,p_n],

where ϕ1\phi_1 is given by (5) and ϕ2\phi_2 is given by (6–10).

Symplecticity. Obviously ϕ1δ\phi_1^\delta defined in (5) is a symplectic map. If ϕ2δ\phi_2^\delta is also symplectic as it should be (since it is the exact flow of some Hamiltonian system), then Integrator 1 is symplectic because it is the composition of symplectic maps. And indeed ϕ2δ\phi_2^\delta is symplectic. In fact, both the ‘no impact’ case (7) and the reflection/refraction case correspond to symplectic maps. The former is obvious, and for the latter we have:

Theorem 3.1. Under Conditions 1 and 2, the reflection/refraction case corresponds to symplectic ϕ2δ\phi_2^\delta.

Proof. Substituting (6), (8), (9) into (10) and computing the Jacobian J=d[Q,P]/d[q,p]J = \mathrm{d}[Q,P]/\mathrm{d}[q,p], one can verify that JTΩJ=ΩJ^T\Omega J = \Omega where Ω=[0I−I0]\Omega= \begin{bmatrix} 0 & I \\ -I & 0 \end{bmatrix} for each case of (9). This shows the preservation of the canonical symplectic 2-form in vector space.

Remark 3.1. One may worry that when transforming an infinitesimal phase space volume by ϕ2δ\phi_2^\delta, part of it undergoes reflection and another part undergoes refraction, which would challenge the above case-by-case demonstration of symplecticity. However, this possibility is ruled out by Condition 2, because the transition between reflection and refraction corresponds to sliding along the interface.

Worth commenting, however, is that neither of the three submaps of ϕ2δ\phi_2^\delta, namely pre-impact flow (8), impact (9), or post-impact flow (10), is symplectic (simple algebra will show JTΩJ≠ΩJ^{T}\Omega J \ne\Omega). The intuition is, (8) and (10) are drifts, but unlike simple drifts over constant time which are symplectic, they have additional q,pq,p dependence through τ\tau (see (6)), which breaks the symplecticity; for (9), both the reflection and refraction cases rescale one component of the momentum without changing anything else, and thus cannot be symplectic. Therefore, it is a nontrivial fact that their composition, ϕ2δ\phi_2^\delta, resumes to be symplectic.

What will the symplecticity of the proposed integrator imply about its accuracy in numerical simulations? We do not yet have a theory. Traditionally, the favorable long time performances of symplectic integrators are supported by elegant theoretical guarantees such as backward error analysis (e.g., [65, 32, 3, 34]), linear error growth for integrable systems (e.g., [11, 10, 71, 34]), and near-preservation of adiabatic invariants [33, 14, 34]. However, none of them can be directly applied to the discontinuous Hamiltonian problem, mainly due to a lack of differentiability in both the Hamiltonian and the pp trajectory. However, symplectic integrators proposed in this article were still observed to exhibit pleasant long time accuracy in numerical experiments (see § 5), and this is intuitive because symplecticity would still be desired at least in flow phases, in which the numerical solution only fluctuates the energy instead of drifting it as many nonsymplectic methods may do, and for most of the time the particle is in flow phases. We imagine that a proof of long time accuracy might require a discontinuous generalization of canonical perturbation theory, which is beyond the scope of this article.

Order of accuracy, time-reversibility, and higher-order splitting schemes Since H=H1+H2H = H_1 + H_2, Integrator 1 can be recognized as a Strang splitting method [77]. In the traditional (smooth) theory this would suggest that ϕ1δ=ϕ1δ/2∘ϕ2δ∘ϕ1δ/2+O(δ3)\phi_1^\delta= \phi_1^{\delta/2} \circ\phi_2^\delta\circ\phi_1^{\delta/2} + O(\delta^3), i.e., Integrator 1 is 2nd-order due to a 3rd-order truncation error. However, that is no longer the case due to discontinuities in pp (momentum), and the method actually only has 2nd-order local truncation error in position (see Appendix § 8.1 for a detailed demonstration).

More generally, a common technique for turning a 1st-order method into 2nd-order is to compose it with its adjoint (see e.g., Chap II.4 in [34]). It is true that ϕ1\phi_1 and ϕ2\phi_2 are self-adjoint (a.k.a. symmetric or time-reversible) and they respectively form semigroups, and Integrator 1 thus may be seen as a 1st-order method ψδ/2:=ϕ1δ/2∘ϕ2δ/2\psi^{\delta/2} := \phi_1^{\delta/2} \circ\phi_2^{\delta/2} composed with its adjoint (ψδ/2)∗=ϕ2δ/2∘ϕ1δ/2(\psi^{\delta/2})^* = \phi_2^{\delta/2} \circ\phi_1^{\delta/2}. However, the tradition proof of the increased order of ψδ/2∘(ψδ/2)∗\psi^{\delta/2} \circ(\psi^{\delta/2})^* relies on Taylor expansion, which is no longer applicable due to the discontinuity produced by ϕ2\phi_2. Because of this, Integrator 1 loses some order of convergence, although the symmetric nature of its composition makes the method time-reversible.

One may also wonder if higher-order splitting schemes will work as designed, such as triple jump (whose one step update is given by ϕ1δγ/2∘ϕ2δγ∘ϕ1δ(1−γ)/2∘ϕ2δ(1−2γ)∘ϕ1δ(1−γ)/2∘ϕ2δγ∘ϕ1δγ/2\phi_{1}^{\delta\gamma/2} \circ\phi_{2}^{\delta\gamma} \circ\phi_{1}^{\delta(1-\gamma)/2} \circ\phi_{2}^{\delta(1-2\gamma)} \circ\phi_{1}^{\delta(1-\gamma)/2} \circ\phi_{2}^{\delta\gamma} \circ\phi_{1}^{\delta\gamma/2}, with γ=1/(2−21/3)\gamma= 1/(2-2^{1/3})) [15, 26, 80, 87], which normally is 4th-order, or more versions given in, for instance, [63, 12, 35, 5, 6]. Unfortunately, they cannot produce anything beyond 1st-order (in position), again due to the lost of smoothness; the constant in the error bound may be improved though. Detailed proof by a counterexample is analogous to that in Appendix § 8.1 and omitted.

Also important to note is, Integrator 1 only has a 1st-order local truncation error in momentum if the step includes a discontinuous momentum change. Without considering the problem’s specific structure, this would imply a 0th-order global error, not only in momentum but also in the position variable as they are coupled. Such a ‘bad accuracy’ is actually expected to some extent, because the momentum exhibits a jump discontinuity across each interface. To better explain this, suppose the actual time of an interface crossing is different from the crossing time of a numerical simulation, then no matter how close these two time points are and how accurate the numerical momentum is outside the interval limited by these two times, inside this time interval the numerical error in momentum is O(1)\mathcal{O}(1), because there either the numerical solution or the exact solution has already completed an O(1)\mathcal{O}(1) jump in momentum, but not both.

However, for our specific problem and specific integrator, ‘bad accuracy’ is actually localized. Observed in all numerical experiments (§ 5) was, the method still exhibited 1st-order global error in position, and while the momentum did not have 1st-order global error uniformly in time, away from interface crossing events the momentum was still 1st-order accurate. The intuition is, the numerical momentum will still catch up with the exact momentum after both solutions complete the interface crossing, and the effect of this lag will not be much amplified because we assumed there is no immediate consecutive interface crossings, and impact and flow have to alternate.

Computing the time to impact in complex situations

Given qq, pp and a generic explicit flow map Φh[q,p]\Phi^{h}[q,p], which is either provided by an exact solution (the case of (7), used for example in the 1st-order method in § 4.1), or provided by a numerical integrator (the case for the high-order construction in § 4.4), we can accurately and efficiently compute the time τ\tau such that the position component of Φτ[q,p]\Phi^{\tau}[q,p] exactly hits an interested interface BijB_{ij}. In [48] a linear interpolation was used to approximate τ\tau. Here we will compute it more accurately. Two cases will be discussed.

For simplified notation, Q(h)Q(h) will denote the position component of Φh[q,p]\Phi^{h}[q,p].

  • When the interface is given by a level set. If Bij=f−1({0})B_{ij}=f^{-1}(\{0\}) for some known C1C^{1} function f(⋅)f(\cdot), and Q(h)Q(h) is a C1C^{1} function (any exact flow of a continuous system satisfies this property, and so should any reasonable approximation of an exact

flow), we use Newton’s method to solve for τ\tau in

f(Q(τ))=0.f(Q(\tau)) = 0.

The solution is given by the simple iteration

τk+1=τk−f(Q(τk))f′(Q(τk))Q′(τk).\tau_{k+1} = \tau_k - \frac{f(Q(\tau_k))}{f'(Q(\tau_k))Q'(\tau_k)}.

Under standard (reasonable) assumptions this iteration converges quadratically. This means that τ\tau can be computed to machine precision by a small amount of iterations. Since τ\tau is just 1-dimensional, these iterations are computationally cheap. Initialization can be made efficient too, for instance via

τ0=−δf(Q(0))f(Q(δ)),\tau_0 = -\delta\frac{f(Q(0))}{f(Q(\delta))},

derived from 0=f(Q(τ))≈f(Q(0))+τδf(Q(δ))0 = f(Q(\tau)) \approx f(Q(0)) + \frac{\tau}{\delta} f(Q(\delta)). This case is demonstrated by the numerical experiment in § 5.3.

  • When the interface is only known indirectly through V(⋅)V(\cdot) values, we use the bisection method: Initially, let tl=0t_l = 0 and tr=δt_r = \delta. At each iteration, let tm=(tl+tr)/2t_m = (t_l + t_r)/2 and compare V(Q(tm))V(Q(t_m)) with V(Q(tl))V(Q(t_l)) and V(Q(tr))V(Q(t_r)); if it agrees with the left value, update by tr←tmt_r \leftarrow t_m, and otherwise update by tl←tmt_l \leftarrow t_m. Terminate the iteration when tr−tl<ϵt_r - t_l < \epsilon for some preset small ϵ\epsilon, and let τ=tm\tau= t_m.

This way, no derivative information is needed, and the convergence of estimated τ\tau values is linear, which implies an exponential decay of error. This speed of convergence is slower than that of Newton, but difficult to improve in this setup because one can only evaluate VV’s values at chosen locations and VV is piecewise constant. On the other hand, to obtain any prefixed accuracy, one still only needs logarithmically many iterations. Therefore, machine precision can again be achieved with a small computational budget.

This case is demonstrated by the numerical experiment in § 5.3.

A third-order in position time-reversible symplectic integrator, when there is only one interface and one degree of freedom

When UU is at least a C3C^3 function, position is one-dimensional and there is only one interface, we are able to increase the order of convergence while maintaining the symplecticity. To do so, denote the interface location by qjumpq_{\mathrm{jump}}, and we first decompose the smooth nonlinear potential UU into a quadratic approximation centered at qjumpq_{\mathrm{jump}} and a nonlinear correction: let

Uquad(q):=U(qjump)+dUdq(qjump)(q−qjump)+12d2Udq2(qjump)(q−qjump)2,U_{\mathrm{quad}}(q) := U(q_{\mathrm{jump}}) + \frac{\mathrm{d}U}{\mathrm{d}q}(q_{\mathrm{jump}})(q-q_{\mathrm{jump}}) + \frac{1}{2}\frac{\mathrm{d}^2U}{\mathrm{d}q^2}(q_{\mathrm{jump}})(q-q_{\mathrm{jump}})^2,
Ucorr(q):=U(q)−Uquad(q).U_{\mathrm{corr}}(q) := U(q) - U_{\mathrm{quad}}(q).

Then we split the original Hamiltonian as the sum of a discontinuous quadratic problem and a correction: let

H1=12pTp+V(q)+Uquad(q)andH2=Ucorr(q)(11)H_1 = \frac{1}{2}p^T p + V(q) + U_{\mathrm{quad}}(q) \qquad\text{and}\qquad H_2 = U_{\mathrm{corr}}(q) \tag*{(11)}

and denote by ϕ1δ\phi_1^\delta and ϕ2δ\phi_2^\delta respectively their exact solution flows. Then both are symplectic maps and explicitly obtainable: the latter is a simple drift in the momentum, and the former is given in Section 2.2.1. More precisely, to convert to notations in § 3.2.1, it is easy to see

Uquad=12ω2(q−qoff)2+(an unimportant constant),U_{\mathrm{quad}} = \frac{1}{2}\omega^2(q-q_{\mathrm{off}})^2 + (an\ unimportant\ constant),

where ω2=U′′(qjump)\omega^2=U^{\prime\prime}(q_{\mathrm{jump}}), \qquad qoff=qjump−U′(qjump)/U′′(qjump)q_{\mathrm{off}}=q_{\mathrm{jump}}-U^\prime(q_{\mathrm{jump})}/U^{\prime\prime}(q_{\mathrm{jump}}).

Finally, we combine this splitting and the classical idea of triple-jump to obtain a method whose one step update is given by:

Integrator 2 (3rd-order in position, time-reversible, symplectic). Use one step update

[qn+1,pn+1]=ϕ2δγ/2∘ϕ1δγ∘ϕ2δ(1−γ)/2∘ϕ1δ(1−2γ)∘ϕ2δ(1−γ)/2∘ϕ1δγ∘ϕ2δγ/2[qn,pn],[q_{n+1},p_{n+1}] = \phi_2^{\delta\gamma/2}\circ\phi_1^{\delta\gamma}\circ\phi_2^{\delta(1-\gamma)/2}\circ\phi_1^{\delta(1-2\gamma)}\circ\phi_2^{\delta(1-\gamma)/2}\circ\phi_1^{\delta\gamma}\circ\phi_2^{\delta\gamma/2}[q_n,p_n],

where γ=1/(2−21/3)\gamma=1/(2-2^{1/3}).

Remark 3.2 (order reduction). This method does not have a 4th-order global error as a continuous analogue would have, but numerically observed is that it has 3rd-order global accuracy in terms of qq, and the global error of pp is also 3rd-order whenever at a time point sufficiently away from impact.

Remark 3.3 (an alternative approach). Triple-jump is a classical way of obtaining a 4th-order smooth integrator, but it is not the only approach. Another classical example is Suzuki’s fractal [80], which in our case is

ϕ2δγ/2∘ϕ1δγ∘ϕ2δγ∘ϕ1δγ∘ϕ2δ(1−3γ)/2∘ϕ1δ(1−4γ)∘ϕ2δ(1−3γ)/2∘ϕ1δγ∘ϕ2δγ∘ϕ1δγ∘ϕ2δγ/2\phi_2^{\delta\gamma/2}\circ\phi_1^{\delta\gamma}\circ\phi_2^{\delta\gamma}\circ\phi_1^{\delta\gamma}\circ\phi_2^{\delta(1-3\gamma)/2}\circ\phi_1^{\delta(1-4\gamma)}\circ\phi_2^{\delta(1-3\gamma)/2}\circ\phi_1^{\delta\gamma}\circ\phi_2^{\delta\gamma}\circ\phi_1^{\delta\gamma}\circ\phi_2^{\delta\gamma/2}

where γ=1/(4−41/3)\gamma=1/(4-4^{1/3}). It often leads to error at the same order but with smaller prefactor, however at the expense of using more stages.

Suzuki’s fractal doesn’t directly transfer to our non-smooth setup either. If one uses the ϕ1\phi_1 and ϕ2\phi_2 constructed in § 4.1 for generic problems, the resulting method remains only 1st-order. With the specialized ϕ1\phi_1 and ϕ2\phi_2 in this section, the result will be 3rd-order (in position, away from impact), same as triple jump (note the order reduction). Symplecticity and reversibility, however, can be obtained.

Remark 3.4 (2nd-order in position, time-reversible, symplectic integrator). If a one-step update of ϕ2δ/2∘ϕ1δ∘ϕ2δ/2\phi_2^{\delta/2}\circ\phi_1^\delta\circ\phi_2^{\delta/2} is used instead (i.e., Strang splitting), numerical experiments suggest that the method has a 2nd-order global error; that is, no order was lost. This is an improvement of the generic method in § 4.1.

Our intuition behind the reduced order (4→3) is, away from interfaces the triple-jump and the Strang splitting will have regular 5th-order and 3rd-order local truncation errors, and their truncation errors degrade to lower order only when the current step involves an impact. However, to encounter an impact, the current position must be O(h)\mathcal{O}(h) away from the interface, which means, according to Taylor expansion, UcorrU_{\mathrm{corr}} is O(h3)\mathcal{O}(h^3) and Ucorr′U'_{\mathrm{corr}} is O(h2)\mathcal{O}(h^2). This exact scaling allows the splitting (global) accuracy to increase from 1st-order (see § 4.1) to 3rd-order near the impact. If a splitting scheme of order higher than 3 in a smooth setup is used (e.g., triple jump), 3rd-order will be retained; in the case of Strang splitting, itself is only 2nd-order, and therefore its discontinuous version based on (11) is still just 2nd-order due to limitations of non-impact steps.

The aforementioned methods based on triple jump and Strang splitting, or any symmetric composition of ϕ1\phi_1 and ϕ2\phi_2, are reversible.

Remark 3.5. The method in this section generalizes to only a small subset of multidegree-of-freedom problems: if there is only one interface and it is linear, then we can similarly construct UquadU_{\mathrm{quad}} by expanding UU in the direction normal to the interface; if there are multiple interfaces and all of them are linear, a Voronoi decomposition may help construct a continuous, piecewise quadratic UquadU_{\mathrm{quad}}; however, it is unclear whether the idea in this subsection can work for nonlinear interface(s).

High-order time-reversible but nonsymplectic integrators

Although it is difficult to obtain a high-order symplectic method due to discontinuity in momentum (see discussions in § 4.1 and § 4.3), an event-driven approach can be adopted to construct arbitrarily high-order time-reversible methods. It is not clear yet what would be the disadvantage of losing symplecticity, as numerical experiments will also demonstrate pleasant long-time properties, similar to those given by the long time error analysis of smooth reversible integrator for reversible integrable systems [34]; note however that a theoretical explanation is lacking.

The one-step update of the new method, with step size denoted by δ\delta, will be constructed based on an ll-th order symplectic integrator for the smooth Hamiltonian H^=12pTp+U(q)\widehat{H} = \frac{1}{2}p^{T}p + U(q). The construction of such integrators is well known (see e.g., [34], or [81] for a recap). Denote the one-step update of this integrator by ψδ\psi^{\delta}, where δ\delta is the step size. We will also assume the explicit existence of a function I(q)I(q) that return ii if q∈Diq \in D_i, the ii-th component of the partition of position space into smooth regions (see its definition below (1)). Then a high-order integrator for the discontinuous problem HH can be constructed through the following stages:

Integrator 3 (ll-th order in position, time-reversible (if the legacy method ψ\psi is reversible)).

  1. Given the current dd-dimensional position qq and momentum pp, check if an impact will occur in δ\delta time. To do so, compute [Q,P]=ψδ[q,p][Q,P] = \psi^\delta[q,p]. If I(q)≠I(q^)I(q) \ne I(\hat{q}), at least one impact occurred.

If no impact occurred, update [q,p][q,p] by [Q,P][Q,P], and go back to Stage 1 for the next step. Otherwise, continue and denote by BijB_{ij} the relevant interface BI(q)I(q^)B_{I(q)I(\hat{q})}.

  1. Otherwise, numerically approximate the time τ\tau (under the flow of H^\hat{H}) to impact. Depending on how the interface BB is provided, this first hitting time τ\tau may be explicitly computable, or it needs to be numerically estimated. For the latter case, § 4.2 provides details about τ\tau’s rapid computation to machine precision, when the interface is provided (i) as a level set of a C1C^1 function, or (ii) in the general case, purely through values of the discontinuous potential V(⋅)V(\cdot).

  1. Update q,pq,p using one step of the continuous symplectic integrator with step size τ\tau; i.e.,

[q,p]←ψτ[q,p][q,p] \gets\psi^\tau[q,p]
  1. Compute the action of an impact. That is, based on (i) the jump size of VV given by the interface BijB_{ij}, and (ii) the normal vector of BijB_{ij} at position qq from DiD_i to DjD_j, perform an instantaneous update of pp either via refraction (eq. (2)) or reflection (eq. (3)).

Note: if BijB_{ij} is only implicitly described by VV values, the normal vector has to be numerically searched, but this search can again be done efficiently and to machine precision using the bisection method, which will take poly-log time.

  1. Update q,pq,p again using one step of the continuous symplectic integrator, this time with step size δ−τ\delta-\tau; i.e.,

[q,p]←ψδ−τ[q,p][q,p] \gets\psi^{\delta-\tau}[q,p]

Remark 3.6 (Applicability). As long as δ\delta is small enough, there is at most one impact per step under Conditions 1, 2 and the assumption that DiD_i’s are open sets.

Remark 3.7 (Non-symplecticity). (i) If τ\tau were a constant (independent of q,pq,p), then Stage 3 and Stage 5 are both symplectic updates; however, Stage 4 is not symplectic. (ii) If τ\tau were the exact hitting time (q,pq,p dependent) and ψ\psi were the exact flow of H^\hat{H}, the new method would be symplectic, but this is unlikely to be possible because then the new method is in fact exact. In this case, neither Stage 3, 4 or 5 is symplectic, but their composition is. (iii) For the new method, Stage 4 remains non-symplectic, neither Stage 3 or 5 is symplectic because τ\tau depends on q,pq,p, and the composition of stages is generally not symplectic.

Remark 3.8 (Order of accuracy). The accuracy of the new method is numerically observed in experiments to be ll-th order (same as the legacy smooth integrator ψ\psi), however in a modified sense that the global error of position is O(δl)O(\delta^l), and that of momentum is O(δl)O(\delta^l) at time points away from interface crossings (the accuracy in pp is 0th-order near interface crossings). The intuition is, during simulation till a fixed O(1)O(1) time, there are only finitely many interface crossing events, which means the O(δl)O(\delta^l) error of ψ\psi will only be amplified at most by a constant factor.

Remark 3.9 (Reversibility). The new method can be easily checked to be reversible if (i) ψ\psi is reversible, (ii) the hitting time is solved for exactly, (iii) there is at most one interface crossing per step.

The adaptive version for safer usages of large timesteps

Depending on the problem, there might be a regime of δ\delta values that are small enough for resolving the dynamics generated by the smooth Hamiltonian H^\hat{H}, however too large in the sense that multiple interface crossings can be encountered within one step. This can happen, for instance, when an interface has a large curvature, which may result in consecutive impacts that are close in time. In this case, methods proposed cannot be accurate when the step size δ\delta is large.

To avoid this deterioration of accuracy, one could of course simply reduce δ\delta, so that at most one interface crossing occurs per step. However, this is not the most computationally efficient solution. Instead, we propose to employ an adaptive time-stepping approach. Our way of introducing adaptivity will destroy symplecticity, and therefore it will be demonstrated on the high-order nonsymplectic method in § 4.4. Most parts will be the same as before, except for a handful of modifications which are underlined:

Integrator 4 (ll-th order in position, adaptive). At the beginning of each step, let δ^=δ\hat{\delta} = \delta. Then,

  1. Given the current dd-dimensional position qq and momentum pp, check if an impact will occur in δ^\hat{\delta} time. To do so, compute [Q,P]=ψδ^[q,p][Q,P] = \psi^{\hat{\delta}}[q,p]. If I(q)≠I(q^)I(q) \ne I(\hat{q}), at least one impact occurred.

    If no impact occurred, update [q,p][q,p] by [Q,P][Q,P], and the current step is completed. Otherwise, continue.

  1. Numerically approximate the time τ\tau (under the flow of H^\hat{H}) to the first impact. Depending on how the interface BB is provided, this first hitting time τ\tau may be explicitly computable, or it needs to be numerically estimated. For the latter case, § 4.2 provides details about τ\tau’s rapid computation to machine precision, when the interface is provided (i) as a level set of a C1C^1 function, or (ii) in the general case, purely through values of the discontinuous potential V(⋅)V(\cdot). Note that there is no guarantee those numerical estimations really correspond to the first hitting time, if δ^\hat{\delta} is too large.

  1. Update q,pq,p using one step of the continuous symplectic integrator with step size τ\tau; i.e.,

[q,p]←ψτ[q,p][q,p] \leftarrow\psi^\tau[q,p]
  1. Compute the action of an impact. That is, based on (i) the jump size of VV given by the interface BijB_{ij}, and (ii) the normal vector of BijB_{ij} at position qq from DiD_i to

DjD_j, perform an instantaneous update of pp either via refraction (eq. (2)) or reflection (eq. (3)).

Note: if BijB_{ij} is only implicitly described by VV values, the normal vector has to be numerically searched, but this search can again be done efficiently and to machine precision using the bisection method, which will take poly-log time.

  1. Update the remaining time using δ^←δ^−τ\hat{\delta} \leftarrow\hat{\delta} - \tau, and return to Stage 1.

Remark 3.10. This method no longer requires at most one impact per step, and it is effective as long as the computed hitting time corresponds to the first hitting. It is not symplectic. Order of accuracy is numerically observed to be ll in the same sense as before. Reversibility is achieved if (i) ψ\psi is reversible, and (ii) every time the first (backward) hitting time is exactly solved for.

The example in Section 4.4 showcases the efficacy of this adaptive method. There the interface actually has kinks (corresponding to corners). Numerically these corners are never exactly reached, but impacts near them can be clustered in time.

Numerical experiments

Quantification via a quadratic benchmark problem

Setup. Consider a one degree-of-freedom problem where the smooth part of the potential is a quadratic function and the jump part corresponds to only one interface, i.e., (4). This is an analytically solvable case (see § 3.2.1), and we chose it so that numerical and exact solutions can be compared to precisely quantify long time accuracy and numerical order of convergence.

Here we use parameters ω=2\omega= 2, qoff=1q_{\mathrm{off}} = 1, ΔV=3\Delta V = 3, qjump=2q_{\mathrm{jump}} = 2.

Figure 4 compares the performances of our 1st-order symplectic Integrator 1 (§ 4.1), a non-symplectic version of this 1st-order method, our 4th-order reversible Integrator 3 (based on a 4th-order reversible smooth integrator) (§ 4.4), an irreversible version of this 4th-order method (based on a smooth integrator of 4th-order Runge-Kutta), and the penalty method (based on a regularized Hamiltonian and a 4th-order reversible symplectic integration of this smooth Hamiltonian). The 3rd-order symplectic integrator in § 4.3 is excluded because it gives the exact solution for this example. The exact solution is periodic with period ≈3\approx3, and the comparison is over T=103T = 10^3 which should be considered as a long time.

Figure 4. A benchmark problem: potential = quadratic + step function. First 4 rows: respectively, 1st-order symplectic, 1st-order non-symplectic, 4th-order reversible, 4th-order irreversible (Runge-Kutta based); left: h=0.01h = 0.01, right: h=0.1h = 0.1. Last row: penalty method, i.e., 4th-order symplectic integration of a regularized Hamiltonian; left: α=104\alpha= 10^4, h=10−5h = 10^{-5}, right: α=103\alpha= 10^3, h=10−5h = 10^{-5}.

The penalty method simulates a regularized smooth penalty Hamiltonian

H(q,p)=∥p∥22/2+U(q)+ΔV11+exp⁡(−α(q−qjump)).(12)H(q,p) = \lVert p\rVert_2^2/2 + U(q) + \Delta V \frac{1}{1+\exp\left(-\alpha(q-q_{\mathrm{jump}})\right)}. \tag*{(12)}

The simulation uses 4th-order symplectic integrator based on triple jump (see e.g., [34]).

The non-symplectic 1st-order integrator used is simply a forward Euler type, with one hh-step update given by

[q,p]↦[q,p]+(ϕ1h/2−id)[q,p]+(ϕ2h−id)[q,p]+(ϕ1h/2−id)[q,p],[q,p] \mapsto[q,p] + (\phi_1^{h/2}-id)[q,p] + (\phi_2^h-id)[q,p] + (\phi_1^{h/2}-id)[q,p],

where ϕ1\phi_1 is given by (5), ϕ2\phi_2 is given by (6–10), and idid is the identity map. As a reminder and a comparison, the symplectic 1st-order integrator used here is [q,p]↦ϕ1h/2∘ϕ2h∘ϕ1h/2[q,p][q,p] \mapsto\phi_1^{h/2} \circ\phi_2^h \circ\phi_1^{h/2}[q,p].

Results. The left half of Figure 4 shows that the 1st-order symplectic method and the 4th-order reversible method exhibit linear growth of error, and almost no drift in energy but only fluctuations. Both are similar to that of the symplectic/reversible integration of smooth integrable systems. On the contrast, the 1st-order non-symplectic method has too much artificial energy injected due to the numerics, and the 4th-order irreversible method (Runge-Kutta based) has artificial energy dissipation, although the amount is small due to small hh, high-order, and TT not too large. More on long time performance will follow.

Comparing the first 4 rows of the left and right halves of Figure 4, which differ by different step sizes, one sees consistency with the claimed order of each method. More on convergence order will follow.

The 5th row shows that the penalty method, when used with a sufficiently small hh, such as o(1/α)o(1/\alpha), has error that is only 1st order in 1/α1/\alpha.

To further study these observations, performances over even longer time span (T=2×105T = 2 \times10^5) are investigated in Figure 5. We see rather irregular, however bounded global error of the 1st-order symplectic method. This should not be surprising as the classical Hamiltonian backward error analysis no longer applies due to discontinuity. The 4th-order irreversible (Runge-Kutta based) method artificially dissipates energy, and its solution error changes like the traditional exponential error growth of non-symplectic methods for smooth problems. The 4th-order reversible (symplectic integrator based) method seems to exhibit linear error growth; however, we note a small but definite drift in its energy error, which is not solely oscillatory. We hope that a symplectic counterpart would not have this drift, but its design remains an open problem.

Figure 5. Super long time performances of proposed methods. 3 rows: respectively, 1st-order symplectic, 4th-order reversible, 4th-order irreversible. Penalty method unaffordable.

Figure 6 confirms that our 1st-order symplectic integrator and 4th-order reversible integrator are indeed 1st and 4th order (note time points of impact are few and therefore negligible after the averaging).

Figure 6. Verifications of orders of 1st-order symplectic Integrator 1 and 4th-order reversible Integrator 3 (based on a symplectic reversible smooth integrator). Root-meansquare errors are computed as 1/(T/h+1)∑i=0T/h(qinum−qexact(ih))2\sqrt{1/(T/h+1)\sum_{i=0}^{T/h}(q_i^{num}-q^{exact}(ih))^2}, T=1000T=1000.

Improved accuracy when there is only one linear interface: a nonlinear example

Let’s now consider a problem with smooth and jump potentials, respectively,

U(q)=(q−qc)4/12,V(q)={ΔV,q>qjump0,q<qjumpundefined,q=qjumpU(q)=(q-q_{\mathrm{c}})^4/12,\qquad V(q)= \begin{cases} \Delta V, & q>q_{\mathrm{jump}} \\ 0, & q<q_{\mathrm{jump}} \\ \text{undefined}, & q=q_{\mathrm{jump}} \end{cases}

Due to the nonlinearity created by UU, no exact solution is available as a benchmark to compare against. However, as there is only one linear interface, the high-order symplectic method in § 4.3 applies.

Figure 7 compares the performances of a 3rd-order Integrator 2, a 2nd-order integrator (Remark 3.4), and a 1st-order Integrator 1, all symplectic. The results indicate consistency with the claimed orders of the methods (Figure 8 further confirms this), and the 2nd- and 3rd-order versions have much more regular long time energy behaviors (note: all three are reversible!)

Long time performances of 1st-, 2nd-, and 3rd-order symplectic integrators; panels labelled “1st-order sympl: phase portrait”, “energy error”, “error in position”, “2nd-order sympl: phase portrait”, “energy error”, “error in position”, “3rd-order sympl: phase portrait”, “energy error”, and “error in position”; axes labelled momentum, position, and time

Figure 7. Long time performances of 1st-, 2nd-, and 3rd-order symplectic integrators for a nonlinear problem with one linear interface.

Figure 8. Verifications of the orders of 1st-, 2nd-, and 3rd-order symplectic methods (Integrator 1, that in Rmk. 3.4, and Integrator 2). Averaged global errors are root-mean-square errors, computed as 1(T/h+1)∑i=0T/h(qinum−qbenchmark(ih))2\sqrt{\frac{1}{(T/h+1)}\sum_{i=0}^{T/h}(q_i^{num}-q^{benchmark}(ih))^2}, T=100T=100.

In these experiments, ΔV=2\Delta V=2, qjump=0q_{\mathrm{jump}}=0, qc=1q_{\mathrm{c}}=1. Trajectory errors are computed by comparing against a tiny step-sized (h=10−5h=10^{-5}) 3rd-order (Integrator 2) simulation.

An example in which the interface is given by a level set; conservation of momentum map

Setup. We now consider an example in which the discontinuous Hamiltonian has a symmetry. For continuous Hamiltonians, this would imply the conservation of a corresponding momentum map, due to Noether’s theorem [66]. Moreover, a symplectic discretization of the continuous Hamiltonian system can inherit this conservation under nontrivial but reasonable conditions (see [62] Chap. 1.3.3 and 1.4.2 for details). Unfortunately, the analogous results for discontinuous Hamiltonians are currently unknown. For our specific example, however, the exact solution would still have a symmetry-based conservation law in addition to energy conservation, and this section investigates whether symplectic Integrator 1 numerically captures this conservation too.

This example has 2 degrees of freedom and significant nonlinearity. The smooth potential is gravitational, U(q)=−1/∥q∥2U(q)=-1/\lVert q\rVert_{2}. However, the solution does not follow the classical 1-body dynamics which corresponds to Keplerian orbits, as there is an additional nonsmooth potential

V(q)={0,∥q∥<rjump,ΔV,∥q∥>rjump.V(q)= \begin{cases} 0, & \lVert q\rVert< r_{jump},\\ \Delta V, & \lVert q\rVert> r_{jump}. \end{cases}

Obviously here the discontinuous interface is nonlinear, and representable by the zero level set of function ∥q∥−rjump\lVert q\rVert-r_{jump}.

The Hamiltonian ∥p∥22/2+U(q)+V(q)\lVert p\rVert_{2}^{2}/2+U(q)+V(q) is invariant under rotations in the plane, and it is not hard to see its exact solution conserves the angular momentum L:=p×q=p1q2−p2q1L:=p\times q=p_{1}q_{2}-p_{2}q_{1} as impact only changes the radial component of pp.

Meanwhile, note that although the Hamiltonian is invariant under rotations, its trajectory is not. Even without the jump discontinuity, the solution as a Keplerian orbit is not a circle, unless its initial condition is special enough to lead to a zero eccentricity.

Figure 9 compares our 1st-order symplectic simulation (by Integrator 1) with a benchmark solution that uses ∼100×\sim100\times computational cost, as well as a nonsymplectic version of Integrator 1. ΔV=0.125\Delta V=0.125, rjump=1.2r_{jump}=1.2, q(0)=[1,0]q(0)=[1,0], p(0)=[0,1.4]p(0)=[0,1.4].

Figure 9. (a) orbit projected to the [q1,q2][q_1,q_2] plane; (b) energy error; (c) angular momentum error; (d) errors in angular momentum LL and energy EE over super long time; note these are unavailable for the benchmark method, and blowing up for the nonsymplectic method. Conservation of angular momentum in the presence of rotational symmetry

The nonsymplectic version used is simply a forward Euler type, with one hh-step update given by

[q,p]↦[q,p]+(ϕ1h−id)[q,p]+(ϕ2h−id)[q,p].[q,p]\mapsto[q,p]+(\phi_{1}^{h}-id)[q,p]+(\phi_{2}^{h}-id)[q,p].

where ϕ1\phi_{1} is given by (5), ϕ2\phi_{2} is given by (6–10), and idid is the identity map. For a fair comparison, the symplectic version used here is an irreversible variation (based on Lie-Trotter splitting instead of Strang splitting), with one hh-step update given by.

[q,p]↦ϕ1h∘ϕ2h[q,p].[q,p]\mapsto\phi_{1}^{h}\circ\phi_{2}^{h}[q,p].

The benchmark solution was generated by fine symplectic simulation of a regularized smooth penalty Hamiltonian

H(q,p)=∥p∥22/2+U(q)+ΔV11+exp⁡(−α(∥q∥−rjump)).(13)H(q,p)=\lVert p\rVert_{2}^{2}/2+U(q)+\Delta V\frac{1}{1+\exp\left(-\alpha(\lVert q\rVert-r_{jump})\right)}. \tag*{(13)}

This simulation uses 4th-order symplectic integrator based on triple jump (see e.g., [34]) with h=10−5h = 10^{-5}, with penalty parameter α=105\alpha= 10^{5}. Both parameters α\alpha and hh were tuned to ensure high precision with lowest possible computational cost.

Results. Figure 9a illustrates the orbits and our method agrees well with the benchmark but uses a 100×100\times larger stepsize, and that even if it uses a 1000×1000\times larger stepsize, the long time error is still moderate (mainly due to accumulated phase error). For the purpose of visualizing the orbit, the simulation time is chosen to be T=500T = 500, which is relatively long, as one can see a nonsymplectic method gradually loses its energy and the particle eventually drops to an orbit with a large semi-major axis which no longer crosses the interface.

Figure 9b and 9c respectively plot how the energy and angular momentum, computed from the numerical solutions, deviates from their true values in time dependent ways. As expected, (i) the 1st-order symplectic method exhibits O(h)O(h) fluctuation in energy, while a nonsymplectic version accumulates error in energy; (ii) angular momentum is numerically conserved; the small error is due to limited machine precision, and h=0.001h = 0.001 gives more error than h=0.01h = 0.01 because it uses 10×10\times more steps, each of which induces a small arithmetic error. Figure 9d confirms that these deviations are truly bounded over super long time (T=100,000T = 100,000).

Sauteed Mushroom: irregular interface geometry and complex dynamics (trapped or ergodic?)

Finally, we demonstrate the capability of the proposed approach using an example where both the interface and the corresponding dynamics are complicated. Among all methods mentioned in this paper, only the adaptive Integrator 4 suits the investigation of the ergodic aspect of the dynamics, which requires accurate and affordable long-time simulation, because it can be ≥4\ge4th-order and capable of capturing multiple impacts in a short duration while still using a large step size. Note the purpose of this section changed a little bit, as we are shifting from demonstrating the correctness of the proposed method to using it as a tool that, for the first time, allows us to probe some hard problems and make conjectures.

More precisely, let’s study a system that complicates the Bunimovich Mushroom, which is a classical example of Hamiltonian systems in divided phase space that ‘demonstrates a continuous transition from a completely chaotic system (stadium) to a completely integrable one (circle)’ [9]. The specific mushroom we consider is a subset of R2\mathbb{R}^{2}, defined as

M={(x,y)∣x2+y2≤2,y≥0}∪{(x,y)∣∣x∣≤1,∣y∣≤1,y≤0}\mathcal{M} = \{(x,y) \mid x^{2} + y^{2} \le2, y \ge0\} \cup\{(x,y) \mid|x| \le1, |y| \le1, y \le0\}

In the language of this paper, the classical Bunimovich Mushroom considers the discontinuous Hamiltonian dynamics of a particle, with initial condition inside M\mathcal{M}, without any smooth potential (i.e., U(q)=0U(q) = 0), and an infinite potential barrier at the mushroom boundary (i.e., V(q)=0V(q) = 0 if q∈M∘q \in\mathcal{M}^{\circ}, V(q)=+∞V(q) = +\infty if q∈Mcq \in\mathcal{M}^{c}, and undefined otherwise). The particle basically travels in straight line at constant speed until hitting the boundary, and then be reflected and travels as a free particle again until the next reflection, and the whole procedure repeats. Note the reflections can be arbitrarily frequent due to sharp corners (and hence our choice of an adaptive integrator). Among many beautiful results, one was the demonstration of that the phase space splits an integrable island and a chaotic sea [9], and initial conditions in one region will not be able to percolate into the other region.

New to this paper is the addition of a nontrivial smooth potential. We are interested in how it could change the global dynamics. Specifically, consider the aforementioned jump potential VV and a smooth potential U(q)=a((q1−q1s)4+(q2−q2s)4)/4U(q) = a((q_1-q_1^s)^4+(q_2-q_2^s)^4)/4, where aa and vector qsq^s are constant parameters, corresponding to a vectorial anharmonic attraction to qsq^s.

In all experiments presented here, the sautee source is fixed at qs=[−0.5;−2]q_s=[-0.5;-2], i.e., the left bottom of the mushroom. The initial condition is fixed as q(0)=[1.5;0.2]q(0)=[1.5;0.2], p(0)=[0;1]p(0)=[0;1], which is in the regular island of the classical mushroom (i.e., a=0a=0).

Figure 10 shows distinct dynamics for different values of aa (short time simulations were provided in addition to long time ones for visualizing the dynamics). The same initial condition is used for all aa values. Although this initial condition corresponds to a regular island in the classical Bunimovich mushroom (Figure 10a), when a=0.008a=0.008 the dynamics appears to be chaotic and ergodic on the entire mushroom. When aa takes a larger value of 0.080.08, however, it seems the dynamics is no longer ergodic any more, although still possibly chaotic, and the trajectory remains trapped in part of the mushroom.

Figure 10. Sauteed mushroom: switching between trapped and ergodic dynamics controlled by the sautee parameter aa. (a) a=0a = 0, medium time; (b) a=0.008a = 0.008, medium time; (c) a=0.08a = 0.08, medium time; (d) a=0a = 0, long time; (e) a=0.008a = 0.008, long time; (f) a=0.08a = 0.08, long time.

Of course, these observations depend on the choice of the sautee source qsq^s too.

Here both the legacy code ψ\psi used by Integrator 4 and the integrator in the bisection method (§ 4.2) for estimating the time to impact are the 4th-order symplectic integrator based on triple jump.

Discussion and conclusion

The accurate and efficient simulation of Hamiltonian mechanical systems with discontinuous potentials is an important problem. In fact, a special case, namely ‘impact/collision/contact integrators’ for potentials with infinitely-high discontinuous barrier(s), has been extensively studied due to extensive applications in engineering and sciences.

The general case where jumps can be finite, however, appears to be insufficiently studied yet. To that end, this article, along the line of [45, 40, 48] in which the particle reflection and refraction at the interface are built into the dynamics, proposes four numerical methods, each with distinct applicability. As for general problems, the first method that we recommend to try (among the four plus the penalty method) is the adaptive high-order Integrator 4. This is because of its robustness to complex interface geometry, together with the fact that whether/how symplecticity benefits long time accuracy is no longer clear (yet) in the discontinuous setting. This integrator already has, at least empirically, pleasant long time behaviors, and is computationally rather

efficient too.

Several questions remain open. For example, (i) How to construct high-order symplectic integrators for general discontinuous potentials? Although we did obtain a 1st-order version for general problems, severe order-reduction from the classical continuous theory is encountered, and it is unclear if there is an order barrier or it is just that a higher-order explicit version remains to be developed. (ii) What would be the advantage(s) of having a symplectic method? Backward error analysis, if still applicable, needs to be completely revamped, and this includes both the modified equation/Hamiltonian theory and the error propagation analysis.

Moreover, the rich field of ‘impact/collision/contact integrators’ has already developed a number of brilliant ideas, and we think many of them can be extrapolated to the more general setting in this article. For example, stabilization techniques may lead to further improved long term behaviors. Such (and more) explorations will be left as future work.

Other applications and extensions of these methods include geometrical optics, where waves can be partially transmitted and reflected [46] at interfaces, high frequency elastic waves through interfaces [41], surface hopping problems [44] in computational chemistry, and quantum-classical couping algorithms [42, 43].

A side remark is that the sauteed mushroom (Sec.4.4) is definitely under-investigated in this article from a dynamical system perspective, but we hope it could demonstrate the applicability of our numerical integrator, and provoke thinking about its global dynamics and bifurcation in the future.

Acknowledgment

MT is thankful for the partial support by NSF DMS-1847802 and ECCS-1936776. SJ was supported by NSFC grant No. 12031013 and by the Strategic Priority Research Program of Chinese Academy of Sciences Grant No. XDA25010404.

Appendix

Why does Strang splitting no longer produce a 2nd-order method

This section will give an example for which Integrator 1 does not have a 3rd-order local truncation error, even though it is a time-reversible method constructed via symmetric Strang splitting (which is guaranteed to have a 3rd-order truncation error in the smooth case).

Consider the quadratic problem given in § 3.2.1 and denote by qq, pp the current position and momentum. Assume q=qjump−Chq=q_{\mathrm{jump}}-Ch for some bounded constant C>0C>0, and p>0p>0 is sufficiently large, so that an impact will happen in hh-time and the interface crossing will be a refraction. In this case, the exact solution after hh-time, QQ, PP, is given by

p^=ω2(q−qoff)2+p2−ω2(qjump−qoff)2\hat{p}=\sqrt{\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}-\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2}}
t=2π−atan2⁡(p^/ω,qjump−qoff)+atan2⁡(p/ω,q−qoff)ωt=\frac{2\pi-\operatorname{atan2}(\hat{p}/\omega,q_{\mathrm{jump}}-q_{\mathrm{off}})+\operatorname{atan2}(p/\omega,q-q_{\mathrm{off}})}{\omega}
pˉ=ω2(q−qoff)2+p2−2ΔV−ω2(qjump−qoff)2\bar{p}=\sqrt{\omega^{2}(q-q_{\mathrm{off}})^{2}+p^{2}-2\Delta V-\omega^{2}(q_{\mathrm{jump}}-q_{\mathrm{off}})^{2}}
Q=qoff+cos⁡(ω(h−t))(qjump−qoff)+sin⁡(ω(h−t))pˉ/ωQ=q_{\mathrm{off}}+\cos(\omega(h-t))(q_{\mathrm{jump}}-q_{\mathrm{off}})+\sin(\omega(h-t))\bar{p}/\omega
P=−ωsin⁡(ω(h−t))(qjump−qoff)+cos⁡(ω(h−t))pˉ.P=-\omega\sin(\omega(h-t))(q_{\mathrm{jump}}-q_{\mathrm{off}})+\cos(\omega(h-t))\bar{p}.

The numerical solution produced by Integrator 1, denoted by Q1Q_{1}, P1P_{1}, is given by

p^1=p−hω2/2(q−qoff)\hat{p}_{1}=p-h\omega^{2}/2(q-q_{\mathrm{off}})
τ=(qjump−q)/p^1\tau=(q_{\mathrm{jump}}-q)/\hat{p}_{1}
p^2=p^12−2ΔV\hat{p}_{2}=\sqrt{\hat{p}_{1}^{2}-2\Delta V}
Q1=qjump+(h−τ)p^2Q_{1}=q_{\mathrm{jump}}+(h-\tau)\hat{p}_{2}
P1=p^2−hω2/2(Q1−qoff)P_{1}=\hat{p}_{2}-h\omega^{2}/2(Q_{1}-q_{\mathrm{off}})

Position. Its truncation error is only 2nd-order. More precisely, we check how well Q1Q_{1} approximates QQ by letting

a0=lim⁡h→0(Q−Q1),a1=lim⁡h→0Q−Q1−a0h,a2=lim⁡h→0Q−Q1−a0−a1hh2.a_{0}=\lim_{h\to0}(Q-Q_{1}),\qquad a_{1}=\lim_{h\to0}\frac{Q-Q_{1}-a_{0}}{h},\qquad a_{2}=\lim_{h\to0}\frac{Q-Q_{1}-a_{0}-a_{1}h}{h^{2}}.

Laborious algebra will show that

a0=0,a1=0,a2=2CΔV+(Cp−p2)(p−p2−2ΔV)2p3p2−2ΔV(C−p)(qoff−qjump)ω2,a_{0}=0,\qquad a_{1}=0,\qquad a_{2}=\frac{2C\Delta V+(Cp-p^{2})(p-\sqrt{p^{2}-2\Delta V})}{2p^{3}\sqrt{p^{2}-2\Delta V}}(C-p)(q_{\mathrm{off}}-q_{\mathrm{jump}})\omega^{2},

which means Q=Q1+O(h2)Q=Q_{1}+O(h^{2}). However, if ΔV=0\Delta V=0, it can be checked that a2=0a_{2}=0, which means the truncation error returns to be 3rd-order, and that is consistent with the fact that the integrator should be 2nd-order in the smooth case.

Momentum. Its truncation error is only 1st-order. More precisely, we check how well P1P_1 approximates PP by letting

b0=lim⁡h→0(P−P1),b1=lim⁡h→0P−P1−b0h,b2=lim⁡h→0P−P1−b0−b1hh2.b_0 = \lim_{h \to0}(P-P_1), \qquad b_1 = \lim_{h \to0}\frac{P-P_1-b_0}{h}, \qquad b_2 = \lim_{h \to0}\frac{P-P_1-b_0-b_1h}{h^2}.

Laborious algebra will show that

b0=0,b1=p−p2−2ΔV2pp2−2ΔV(2C−p)(qoff−qjump)ω2,b_0=0,\qquad b_1=\frac{p-\sqrt{p^2-2\Delta V}}{2p\sqrt{p^2-2\Delta V}}(2C-p)(q_{\mathrm{off}}-q_{\mathrm{jump}})\omega^2,
b2=ω24p3α4(−2C2(4ΔV2(pα−β)−2ΔVp2(pα−2β)+p3(α−p)β)−4CΔVp2α3+ΔVp3αβ),b_2=\frac{\omega^2}{4p^3\alpha^4}\left(-2C^2\left(4\Delta V^2(p\alpha-\beta)-2\Delta Vp^2(p\alpha-2\beta)+p^3(\alpha-p)\beta\right)-4C\Delta Vp^2\alpha^3+\Delta Vp^3\alpha\beta\right),

where α=p2−2ΔV\alpha=\sqrt{p^2-2\Delta V} and β=ω2(qjump−qoff)2\beta=\omega^2(q_{\mathrm{jump}}-q_{\mathrm{off}})^2. This means P=P1+O(h)P=P_1+\mathcal{O}(h). However, if ΔV=0\Delta V=0, it can be checked that b1=0b_1=0 and b2=0b_2=0, which means the truncation error returns to be 3rd-order. That is again consistent with the 2nd-order nature in the smooth case.

References

References

  1. [1]S. J. Aarseth and F. Hoyle, Dynamical evolution of clusters of galaxies, i, Monthly Notices of the Royal Astronomical Society, 126 (1963), pp. 223–255.DOI
  2. [2]L. Ambrosio, Transport equation and cauchy problem for bv vector fields, Inventiones mathematicae, 158 (2004), pp. 227–260.DOI
  3. [3]G. Benettin and A. Giorgilli, On the hamiltonian interpolation of near-to-the identity symplectic mappings with application to symplectic integration algorithms, Journal of Statistical Physics, 74 (1994), pp. 1117–1143.DOI
  4. [4]S. Blanes and F. Casas, A concise introduction to geometric numerical integration, CRC press, 2017.
  5. [5]S. Blanes, F. Casas, P. Chartier, and A. Murua, Optimized high-order splitting methods for some classes of parabolic equations, Mathematics of Computation, 82 (2013), pp. 1559–1576.arxiv.org/abs/1102.1622
  6. [6]S. Blanes, F. Casas, A. Farres, J. Laskar, J. Makazaga, and A. Murua, New families of symplectic splitting methods for numerical integration in dynamical astronomy, Applied Numerical Mathematics, 68 (2013), pp. 58–72.DOI
  7. [7]S. D. Bond and B. J. Leimkuhler, Stabilized integration of hamiltonian systems with hard-sphere inequality constraints, SIAM Journal on Scientific Computing, 30 (2008), pp. 134–147.DOI
  8. [8]F. A. Bornemann and C. Schütte, Homogenization of Hamiltonian systems with a strong constraining potential, Phys. D, 102 (1997), pp. 57–77.DOI
  9. [9]L. A. Bunimovich, Mushrooms and other billiards with divided phase space, Chaos: An Interdisciplinary Journal of Nonlinear Science, 11 (2001), pp. 802–808.pubmed.ncbi.nlm.nih.gov/12779519
  10. [10]M.-P. Calvo and E. Hairer, Accurate long-term integration of dynamical systems, Appl. Numer. Math., 18 (1995), pp. 95–105.DOI
  11. [11]M. P. Calvo and J. Sanz-Serna, The development of variable-step symplectic integrators, with application to the two-body problem, SIAM Journal on Scientific Computing, 14 (1993), pp. 936–952.DOI
  12. [12]F. Castella, P. Chartier, S. Descombes, and G. Vilmart, Splitting methods with complex times for parabolic equations, BIT Numerical Mathematics, 49 (2009), pp. 487–508.DOI
  13. [13]F. Cirak and M. West, Decomposition contact response (dcr) for explicit finite element dynamics, International Journal for Numerical Methods in Engineering, 64 (2005), pp. 1078–1110.DOI
  14. [14]D. Cohen, T. Jahnke, K. Lorenz, and C. Lubich, Numerical integrators for highly oscillatory Hamiltonian systems: a review, in Analysis, modeling and simulation of multiscale problems, Springer, Berlin, 2006, pp. 553–576.DOI
  15. [15]M. Creutz and A. Gocksch, Higher-order hybrid Monte Carlo algorithms, Physical Review Letters, 63 (1989), p. 9.pubmed.ncbi.nlm.nih.gov/10040419
  16. [16]P. Deuflhard, R. Krause, and S. Ertel, A contact-stabilized newmark method for dynamical contact problems, International Journal for Numerical Methods in Engineering, 73 (2008), pp. 1274–1290.DOI
  17. [17]S. Dharmaraja, H. Kesari, E. Darve, and A. J. Lew, Time integrators based on approximate discontinuous hamiltonians, International journal for numerical methods in engineering, 89 (2012), pp. 71–104.
  18. [18]L. Dieci and L. Lopez, Sliding motion in flippo differential systems: theoretical results and a computational approach, SIAM Journal on Numerical Analysis, 47 (2009), pp. 2023–2051.DOI
  19. [19]M. Dijkstra, Phase behavior of hard spheres with a short-range yukawa attraction, Physical Review E, 66 (2002), p. 021402.pubmed.ncbi.nlm.nih.gov/12241173
  20. [20]R. J. DiPerna and P.-L. Lions, Ordinary differential equations, transport theory and sobolev spaces, Inventiones mathematicae, 98 (1989), pp. 511–547.DOI
  21. [21]D. Doyen, A. Ern, and S. Piperno, Time-integration schemes for the finite element dynamic Signorini problem, SIAM Journal on Scientific Computing, 33 (2011), pp. 223–249.DOI
  22. [22]K. Feng, Difference schemes for Hamiltonian formalism and symplectic geometry, J. Comput. Math., 4 (1986), pp. 279–289.DOI
  23. [23]K. Feng and M. Qin, Symplectic geometric algorithms for Hamiltonian systems, Springer, 2010.DOI
  24. [24]R. C. Fetecau, J. E. Marsden, M. Ortiz, and M. West, Nonsmooth lagrangian mechanics and variational collision integrators, SIAM Journal on Applied Dynamical Systems, 2 (2003), pp. 381–416.DOI
  25. [25]A. F. Filippov, Differential equations with discontinuous righthand sides: control systems, vol. 18, Springer Science & Business Media, 2013.
  26. [26]E. Forest, Canonical integrators as tracking codes, in AIP Conf. Proc., vol. 184, AIP Publishing, 1989, pp. 1106–1136.
  27. [27]L. M. Fridman, Slow periodic motions with internal sliding modes in variable structure systems, International Journal of Control, 75 (2002), pp. 524–537.
  28. [28]B. García-Archilla, J. M. Sanz-Serna, and R. D. Skeel, Long-time-step methods for oscillatory differential equations, SIAM J. Sci. Comput., 20 (1999), pp. 930–963.
  29. [29]R. A. Gerber, Global effects of softening n-body galaxies, The Astrophysical Journal, 466 (1996), p. 724.DOI
  30. [30]Y. Gonthier, J. McPhee, C. Lange, and J.-C. Piedboeuf, A regularized contact model with asymmetric damping and dwell-time dependent friction, Multibody System Dynamics, 11 (2004), pp. 209–233.
  31. [31]J. W. Grizzle, C. Chevallereau, R. W. Sinnet, and A. D. Ames, Models, feedback control, and open problems of 3d bipedal robotic walking, Automatica, 50 (2014), pp. 1955–1988.
  32. [32]E. Hairer, Backward analysis of numerical integrators and symplectic methods, Annals of Numerical Mathematics, 1 (1994), pp. 107–132.
  33. [33]E. Hairer and C. Lubich, Long-time energy conservation of numerical methods for oscillatory differential equations, SIAM journal on numerical analysis, 38 (2000), pp. 414–441.DOI
  34. [34]E. Hairer, C. Lubich, and G. Wanner, Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, Springer, Berlin Heidelberg New York, second ed., 2006.
  35. [35]E. Hansen and A. Ostermann, High order splitting methods for analytic semigroups exist, BIT Numerical Mathematics, 49 (2009), pp. 527–542.DOI
  36. [36]D. Heyes, Molecular dynamics simulations of restricted primitive model 1: 1 electrolytes, Chemical Physics, 69 (1982), pp. 155–163.DOI
  37. [37]N. J. Higham, The accuracy of floating point summation, SIAM Journal on Scientific Computing, 14 (1993), pp. 783–799.DOI
  38. [38]Y. A. Houndonougbo, B. B. Laird, and B. J. Leimkuhler, A molecular dynamics algorithm for mixed hard-core/continuous potentials, Molecular Physics, 98 (2000), pp. 309–316.
  39. [39]J. D. Jackson, Classical electrodynamics, John Wiley & Sons, 2007.
  40. [40]S. Jin, Numerical methods for hyperbolic systems with singular coefficients: well-balanced scheme, hamiltonian preservation, and beyond, Hyperbolic Problems: Theory, Numerics and Applications, 67 (2009), p. 93.DOI
  41. [41]S. Jin and X. Liao, A hamiltonian-preserving scheme for high frequency elastic waves in heterogeneous media, Journal of Hyperbolic Differential Equations, 3 (2006), pp. 741–777.DOI
  42. [42]S. Jin and K. A. Novak, A semiclassical transport model for thin quantum barriers, Multiscale Modeling & Simulation, 5 (2006), pp. 1063–1086.
  43. [43]—, A semiclassical transport model for two-dimensional thin quantum barriers, Journal of Computational Physics, 226 (2007), pp. 1623–1644.DOI
  44. [44]S. Jin, P. Qi, and Z. Zhang, An eulerian surface hopping method for the schrödinger equation with conical crossings, Multiscale Modeling & Simulation, 9 (2011), pp. 258–281.DOI
  45. [45]S. Jin and X. Wen, Hamiltonian-preserving schemes for the liouville equation with discontinuous potentials, Communications in Mathematical Sciences, 3 (2005), pp. 285–315.DOI
  46. [46]—, A hamiltonian-preserving scheme for the liouville equation of geometrical optics with partial transmissions and reflections, SIAM Journal on Numerical Analysis, 44 (2006), pp. 1801–1828.DOI
  47. [47]—, Hamiltonian-preserving schemes for the liouville equation of geometrical optics with discontinuous local wave speeds, Journal of Computational Physics, 214 (2006), pp. 672–697.DOI
  48. [48]S. Jin, H. Wu, and Z. Huang, A hybrid phase-flow method for hamiltonian systems with discontinuous hamiltonians, SIAM Journal on Scientific Computing, 31 (2009), pp. 1303–1321.DOI
  49. [49]S. Jin and D. Yin, Computational high frequency waves through curved interfaces via the liouville equation and geometric theory of diffraction, Journal of Computational Physics, 227 (2008), pp. 6106–6139.DOI
  50. [50]C. Kane, E. A. Repetto, M. Ortiz, and J. E. Marsden, Finite element analysis of nonsmooth contact, Computer methods in applied mechanics and engineering, 180 (1999), pp. 1–26.DOI
  51. [51]D. M. Kaufman and D. K. Pai, Geometric numerical integration of inequality constrained, nonsmooth hamiltonian systems, SIAM Journal on Scientific Computing, 34 (2012), pp. A2670–A2703.arxiv.org/abs/1007.2233
  52. [52]H. B. Khenous, P. Laborde, and Y. Renard, Mass redistribution method for finite element contact problems in elastodynamics, European Journal of Mechanics-A/Solids, 27 (2008), pp. 918–932.DOI
  53. [53]R. Krause and M. Walloth, Presentation and comparison of selected algorithms for dynamic contact based on the newmark scheme, Applied Numerical Mathematics, 62 (2012), pp. 1393–1410.DOI
  54. [54]T. Laursen and V. Chawla, Design of energy conserving algorithms for frictionless dynamic contact problems, International Journal for Numerical Methods in Engineering, 40 (1997), pp. 863–886.doi.org/10.1002/(sici)1097-0207(19970315)40:5<863::aid-nme92>3.0.co;2-v
  55. [55]T. Laursen and G. Love, Improved implicit integrators for transient impact problems—geometric admissibility within the conserving framework, International Journal for Numerical Methods in Engineering, 53 (2002), pp. 245–274.DOI
  56. [56]B. Leimkuhler and S. Reich, Simulating Hamiltonian dynamics, vol. 14, Cambridge University Press, 2004.DOI
  57. [57]R. I. Leine and H. Nijmeijer, Dynamics and bifurcations of non-smooth mechanical systems, vol. 18, Springer Science & Business Media, 2013.
  58. [58]S. Leyendecker, C. Hartmann, and M. Koch, Variational collision integrator for polymer chains, Journal of Computational Physics, 231 (2012), pp. 3896–3911.DOI
  59. [59]J. Llibre, P. R. Da Silva, and M. A. Teixeira, Regularization of discontinuous vector fields on R^3 via singular perturbation, Journal of Dynamics and Differential Equations, 19 (2007), pp. 309–331.DOI
  60. [60]J. Llibre, P. R. Da Silva, M. A. Teixeira, et al., Sliding vector fields via slow-fast systems, Bulletin of the Belgian Mathematical Society-Simon Stevin, 15 (2008), pp. 851–869.DOI
  61. [61]O. Makarenkov and J. S. Lamb, Dynamics and bifurcations of nonsmooth systems: A survey, Physica D: Nonlinear Phenomena, 241 (2012), pp. 1826–1844.DOI
  62. [62]J. E. Marsden and M. West, Discrete mechanics and variational integrators, Acta Numer., 10 (2001), pp. 357–514.DOI
  63. [63]R. McLachlan and G. R. W. Quispel, Splitting methods, Acta Numer., (2002), pp. 341–434.
  64. [64]W. J. McNeil and W. G. Madden, A new method for the molecular dynamics simulation of hard core molecules, The Journal of Chemical Physics, 76 (1982), pp. 6221–6226.DOI
  65. [65]J. Moser, Lectures on Hamiltonian systems, vol. 81, American Mathematical Soc., 1968.
  66. [66]E. Noether, Invariant variationsprobleme, Nachr. D. König. Gesellsch. D. Wiss. Zu Göttingen, Math-phys. Klasse, (1918), pp. 235–257.
  67. [67]A. Nordmark, H. Dankowicz, and A. Champneys, Friction-induced reverse chatter in rigid-body mechanisms with impacts, IMA Journal of Applied Mathematics, 76 (2011), pp. 85–119.DOI
  68. [68]A. Pandolfi, C. Kane, J. E. Marsden, and M. Ortiz, Time-discretized variational formulation of non-smooth frictional contact, International Journal for Numerical Methods in Engineering, 53 (2002), pp. 1801–1829.DOI
  69. [69]D. Pekarek and T. D. Murphey, Variational nonsmooth mechanics via a projected hamilton’s principle, in 2012 American Control Conference (ACC), IEEE, 2012, pp. 1040–1046.
  70. [70]B. Perthame and C. Simeoni, A kinetic scheme for the saint-venant system with a source term, Calcolo, 38 (2001), pp. 201–231.
  71. [71]G. Quispel and C. Dyt, Volume-preserving integrators have linear error growth, Phys. Lett. A, 242 (1998), pp. 25–30.
  72. [72]J. Sanz-Serna and M. Calvo, Numerical Hamiltonian problems, Chapman and Hall/CRC, 1st ed., 1994.
  73. [73]J. M. Sanz-Serna, Symplectic integrators for Hamiltonian problems: an overview, Acta Numer., 1 (1992), pp. 243–286.
  74. [74]J. M. Sanz-Serna, Mollified impulse methods for highly oscillatory differential equations, SIAM J. Numer. Anal., 46 (2) (2008), pp. 1040–1059.
  75. [75]A. Souza and M. Tao, Metastable transitions in inertial Langevin systems: what can be different from the overdamped case?, European Journal of Applied Mathematics, (2018).arxiv.org/abs/1801.05776
  76. [76]D. E. Stewart, Rigid-body dynamics with friction and impact, SIAM review, 42 (2000), pp. 3–39.DOI
  77. [77]G. Strang, On the construction and comparison of difference schemes, SIAM J. Numer. Anal., 5 (1968), pp. 506–517.DOI
  78. [78]R. M. Stratt, S. L. Holmgren, and D. Chandler, Constrained impulsive molecular dynamics, Molecular Physics, 42 (1981), pp. 1233–1143.DOI
  79. [79]S.-H. Suh, L. Mier-Y Teran, H. White, and H. Davis, Molecular dynamics study of the primitive model of 1–3 electrolyte solutions, Chemical physics, 142 (1990), pp. 203–211.DOI
  80. [80]M. Suzuki, Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations, Phys. Lett. A, 146 (1990), pp. 319–323.DOI
  81. [81]M. Tao, Explicit high-order symplectic integrators for charged particles in general electromagnetic fields, Journal of Computational Physics, 327 (2016), pp. 245–251.DOI
  82. [82]——, Explicit symplectic approximation of nonseparable Hamiltonians: algorithm and long time performance, Phys. Rev. E, 94 (2016), p. 043303.DOI
  83. [83]M. Tao and H. Owhadi, Variational and linearly-implicit integrators, with applications, IMA Journal of Numerical Analysis, 36 (2016), pp. 80–107.arxiv.org/abs/1103.4645
  84. [84]M. Tao, H. Owhadi, and J. E. Marsden, Nonintrusive and structure preserving multiscale integration of stiff ODEs, SDEs and Hamiltonian systems with hidden slow dynamics via flow averaging, Multiscale Modeling & Simulation: A SIAM Interdisciplinary Journal, 8 (2010), pp. 1269–1324.
  85. [85]——, From efficient symplectic exponentiation of matrices to symplectic integration of high-dimensional Hamiltonian systems with slowly varying quadratic stiff potentials, Appl. Math. Res. Express, (2011), pp. 242–280.arxiv.org/abs/1006.4659
  86. [86]M. A. Teixeira and P. R. da Silva, Regularization and singular perturbation techniques for non-smooth systems, Physica D: Nonlinear Phenomena, 241 (2012), pp. 1948–1955.DOI
  87. [87]H. Yoshida, Construction of higher order symplectic integrators, Phys. Lett. A, 150 (1990), pp. 262–268.

Paper details

vlnc:W_h8sebvxz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents