betaFeedback

WorksMathematics

Robust computation of higher-dimensional invariant tori from individual trajectories

Abstract

We present a method for computing invariant tori of dimension greater than one. The method uses a single short trajectory of a dynamical system without any continuation or initial guesses. No preferred coordinate system is required, meaning the method is practical for physical systems where the user does not have much a priori knowledge. Three main tools are used to obtain the rotation vector of the invariant torus: the reduced rank extrapolation method, Bayesian maximum a posteriori estimation, and a Korkine-Zolatarev lattice basis reduction. The parameterization of the torus is found via a least-squares approach. The robustness of the algorithm is demonstrated by accurately computing many two-dimensional invariant tori of a standard map example. Examples of islands and three-dimensional invariant tori are shown as well.

Introduction

Invariant tori are central to the study of low-dimensional Hamiltonian dynamical systems. Familiar examples in celestial mechanics are elliptic orbits in the two-body problem and quasiperiodic trojan orbits in the restricted three-body problem [1]. In plasma confinement, invariant tori appear for both magnetic fieldline dynamics and charged particle motion [2, 3]. For both areas, the predictable bounded motion of integrable trajectories is critical for downstream physics and engineering problems. In this paper, we will parameterize these tori.

There is a variety of existing methods for computing invariant tori. The most common one is the parameterization method [4, 5, 6, 7] which directly solves the conjugacy that defines an invariant torus. One of the primary benefits of the parameterization method is its connection to Kolmogorov-Arnold-Moser (KAM) theory [8, 9, 10, 11], where a convergent numerical algorithm amounts to a proof of the existence of a torus [12]. The parameterization method is used within astrodynamics for the computation of quasiperiodic orbits [13, 14, 15, 16] A similar method known as quadratic flux minimizing (QFMin) surfaces [17, 18] is used for flux surfaces in stellarators [19, 20] (see [21] for another approach). QFMin recovers an invariant torus when it exists and otherwise it returns optimal surfaces that cut through island chains and chaos.

The appealing aspect of both the parameterization method and QFMin is the accuracy with which an invariant torus can be computed. However, these methods also come with a practical downside: a good initial guess is required. This is typically solved by continuation either in a physical parameter or within phase space. For instance, given the location of an elliptic fixed point of a 2D symplectic map (an “o-point”), one can use continuation to compute nested invariant tori about that point. Alternatively, parameter continuation is typically used to track invariant tori as the magnitude of some forcing term increases. In higher dimensional systems, continuation becomes significantly more complicated, as initial guesses are not as readily available. This is a particular problem when one wants to compute many tori, as continuation often requires a significant amount of effort from the researcher.

Another class of methods—which we refer to as frequency methods—are based on single trajectories of the dynamical system. The most popular work within this category is the frequency map method by Laskar [22, 23], which can be used to compute rotation numbers of invariant tori from individual trajectories. With a similar formulation, it was shown that the weighted Birkhoff average [24, 25, 26] can be used to accelerate the computation of C∞C^\infty ergodic averages of length TT trajectories on C∞C^\infty tori with a rate of O(T−M)O(T^{-M}) for all MM. This result has been extended in the analytic case to exponential rates of O(e−rTξ)O(e^{-rT^\xi}) in [27] (see [28] for sharper results). Using an ergodic inverse Fourier transform, the weighted Birkhoff average can then be used to compute a parameterization of an invariant torus in two dimensions [29] (see also § 2). This approximation of the invariant torus can be used to initialize the parameterization method for a higher fidelity result. Here, we will rely upon the Birkhoff reduced rank extrapolation (Birkhoff RRE) method [30], which simultaneously computes many frequencies to high precision rather than the single frequency in frequency map analysis. Birkhoff RRE has been used to accurately compute magnetic flux surfaces in [31] and charged particle orbits in [32].

Frequency methods have the benefit of using a single trajectory, rather than using continuation as is typical for the parameterization method and QFMin. Unfortunately, frequency methods typically require the assumption that the researcher has a priori knowledge that the invariant torus is star shaped to obtain the rotation number. For simple one-dimensional invariant circles, this is not an unreasonable assumption; a naïve average of the trajectory position will often give a good enough guess for a coordinate system. In the case that a 1D trajectory is not star-shaped, the method by Luque and Villanueva [33] can be used to alleviate the problem. However, to our knowledge, there is no general frequency method for higher dimensional tori. In particular, for the rotation vector to be easily expressed via a limit, it is necessary to know a coordinate system where the torus is a graph over angular variables.

In this paper, we present a new frequency method to compute invariant tori that satisfies

  1. The method is dimension- and coordinate-agnostic.

  1. No continuation or initial guesses are required for the torus parameterization or the rotation vector.

  1. The input to the algorithm is a single trajectory on an invariant torus.

  1. Few iterations of the map are required (as compared to weighted Birkhoff averaging).

We emphasize that none of the reviewed methods satisfy all of these requirements. The first and second requirements are the most difficult to perform simultaneously, while the third and fourth are convenient computationally. The fourth point is particularly appealing for many physical systems, as computing long trajectories may be the most costly part of computing tori in practice. Because we satisfy the above requirements, this method allows for more practical computations of higher-dimensional invariant tori within several application areas (code is publicly available in the SymplecticMapTools.jl Julia package [34]).

Our method comprises four steps. First, we accurately compute the trajectory’s most prominent frequencies using Birkhoff RRE. This step has the side benefit of returning a residual that can be used to classify the trajectory as integrable or chaotic. Second, we use those frequencies to infer a valid rotation vector via Bayesian maximum a posteriori (MAP) estimation. Third, we transform the rotation vector so that the invariant torus has a preferred coordinate system. (This aligns with the intuition of a “short way” and “long way” round a two-dimensional torus.) This is made precise via a Korkine-Zolotarev (KZ) lattice basis reduction using an averaged metric on the torus. Fourth, we compute the invariant torus Fourier coefficients from the trajectory and the rotation vector.

Because the final parameterization step is the simplest, we begin our exposition with it in § 2 assuming the rotation vector is already known. This will allow us to explore how the parameterization of higher dimensional tori changes under changes in the homology. Then, in § 3 we explain the first three steps to compute the rotation vector. In both of these sections, we use examples that demonstrate how high dimensionality introduces difficulties not seen for one-dimensional invariant tori. We test the method in § 4 with three applications: a coupled standard map, charged particle dynamics in a stellarator, and non-planar satellite trajectories in cislunar space. Through these tests, we explore the robustness of the method in situations relevant to the modern theory of dynamical systems, plasma physics, and astrodynamics. By one a posteriori measure of success, we show that we successfully parameterize 95% of the initialized tori for the weakly coupled standard map, and we discuss the two main modes of failure that are accentuated in higher dimensions: nearly resonant rotation numbers and filamentary invariant tori. Finally, we conclude in Section 5.

Computing invariant torus Fourier coefficients

Let F:M→MF:\mathcal{M}\to\mathcal{M} be an smooth map on a smooth manifold M\mathcal{M} (here, smooth either means analytic or CMC^{M} for some MM, which we will discuss when relevant). We define a dd-dimensional invariant torus as an smooth mapping S:Td→MS:\mathbb{T}^{d}\to\mathcal{M} where T=R\Z\mathbb{T}=\mathbb{R}\backslash\mathbb{Z} such that the dynamics are conjugate to rotation by a vector ω∈Td\omega\in\mathbb{T}^{d} as

∀θ∈Td,F(S(θ))=S(θ+ω).\forall\theta\in\mathbb{T}^{d},\quad F(S(\theta))=S(\theta+\omega).

We assume that ω\omega obeys a Diophantine condition, where for all k∈Zdk\in\mathbb{Z}^{d}

∣ω⋅k∣T≥c∥k∥ν\lvert\omega\cdot k\rvert_{\mathbb{T}}\geq\frac{c}{\lVert k\rVert^{\nu}}

for some constants c>0c>0 and ν≥d\nu\geq d, where the vector norm ∥⋆∥\lVert\star\rVert is L2L^{2} unless otherwise specified, and ∣⋆∣T:T→R\lvert\star\rvert_{\mathbb{T}}:\mathbb{T}\to\mathbb{R} is the distance of an angle θ∈T\theta\in\mathbb{T} from zero

∣θ∣T=min⁡m∈Z∣θ−m∣.\lvert\theta\rvert_{\mathbb{T}}=\min_{m\in\mathbb{Z}}\lvert\theta-m\rvert.

Note that we regard ω⋅k\omega\cdot k as an element of T\mathbb{T}. The Diophantine condition guarantees the rotation vector ω\omega is far from being resonant (ω\omega is resonant if ω⋅k=0\omega\cdot k=0 for some k∈Zd\{0}k\in\mathbb{Z}^{d}\backslash\{0\}). Non-resonant ω\omega implies ergodic dynamics on the invariant torus. Invariant tori commonly arise in Poincaré maps for Hamiltonian dynamical systems. For this reason, we focus on symplectic maps within this document, as continuous-time tori can be found by simply “extruding” the discrete-time tori via the flow.

An example of a d=2d=2 invariant torus is found in the elliptic restricted three-body problem (ER3BP) [35]. The ER3BP describes the motion of a body of negligible mass forced by the gravity of two massive primary bodies in an elliptic two-body orbit about one another. In our example, we choose the primary body parameters to match Jupiter and the Sun. The frame of reference is chosen to co-rotate and compress with the elliptic orbit, giving the pulsating synodic Cartesian coordinates ξ=(ξ,η)\boldsymbol{\xi}=(\xi,\eta) in the plane of the orbit. In these coordinates, the dynamics of the third body are given by the 2.5-dimensional Hamiltonian dynamical system

ξ˙=−∂H∂p,p˙=∂H∂ξ,H(ξ,p,f)=12(pξ2+pη2+ξ2+η2)+ηpξ−ξpη−ϕ(ξ,f),(1)\dot{\boldsymbol{\xi}}=-\frac{\partial H}{\partial\boldsymbol{p}},\qquad\dot{\boldsymbol{p}}=\frac{\partial H}{\partial\boldsymbol{\xi}},\qquad H(\boldsymbol{\xi},\boldsymbol{p},f)=\frac{1}{2}\left(p_{\xi}^{2}+p_{\eta}^{2}+\xi^{2}+\eta^{2}\right)+\eta p_{\xi}-\xi p_{\eta}-\phi(\boldsymbol{\xi},f), \tag*{(1)}

where p=(pξ,pη)\boldsymbol{p}=(p_{\xi},p_{\eta}) are the momenta corresponding to ξ\boldsymbol{\xi} and the dot represents derivatives with respect to the time-like true anomaly ff — defined as the angle between the periapsis of either of the primary bodies and its current position relative to the common center-of-mass of the system. The potential ϕ\phi is defined by

ϕ=11+ϵcos⁡f[12((1−μ)ρ12+μρ22)+1−μρ1+μρ2],ρ12=(ξ−μ)2+η2,ρ22=(ξ−(μ−1))2+η2.\phi=\frac{1}{1+\epsilon\cos f}\left[\frac{1}{2}\left((1-\mu)\rho_{1}^{2}+\mu\rho_{2}^{2}\right)+\frac{1-\mu}{\rho_{1}}+\frac{\mu}{\rho_{2}}\right],\qquad\rho_{1}^{2}=(\xi-\mu)^{2}+\eta^{2},\qquad\rho_{2}^{2}=(\xi-(\mu-1))^{2}+\eta^{2}.

where ϵ=0.0489\epsilon=0.0489 is the eccentricity of the elliptical orbit of the primary bodies and μ=m2/(m1+m2)=9.54×10−4\mu=m_{2}/(m_{1}+m_{2})=9.54\times10^{-4} is the mass ratio of the primaries. A map is obtained by evolving the ER3BP over an orbit of the two primaries, i.e. F:(ξ(0),p(0))↦(ξ(2π),p(2π))F:(\boldsymbol{\xi}(0),\boldsymbol{p}(0))\mapsto(\boldsymbol{\xi}(2\pi),\boldsymbol{p}(2\pi)). To compute these trajectories, we use the SRK3 symplectic integrator [36] provided by the Julia package GeometricIntegrators.jl [37] with a time step of 2π/10002\pi/1000.

Nearby the stable L4_4 and L5_5 Lagrange points for the unperturbed circular problem, the ER3BP supports invariant tori. Many asteroids — called trojans — are known to orbit along these invariant tori [1]. In Figure 1, we plot multiple projections of a trajectory initialized on an invariant torus at ξ=(1/2,3/2−0.005)\boldsymbol{\xi}=(1/2,\sqrt{3}/2-0.005), p=(0,0)\mathbf{p}=(0,0), nearby the stable L4_4 Lagrange equilibrium point ξ=(1/2,3/2)\boldsymbol{\xi}=(1/2,\sqrt{3}/2) for the unperturbed ϵ=μ=0\epsilon=\mu=0 problem. The plotted trajectory consists of 601 points, corresponding to a physical time of 7,127 years. We note that, due to the high-dimensional nature of the problem, different projections of the invariant torus appear significantly different to the eye. This makes it generally difficult to intuit the high-dimensional geometry of dynamical systems from visuals alone. However, we do make one observation from Figure 1(a) that generalizes well to many other tori: the trojan invariant torus is significantly thinner in some directions than others, a property we generally refer to as “filamentary” or “anisotropic.” We will find anisotropy is one of the main difficulties of computing invariant tori.

A trojan invariant torus for the ER3BP plotted in the $(\xi,\eta)$, $(\dot{\xi},\dot{\eta})$, $(\xi,\dot{\xi})$, and $(\eta,\dot{\eta})$ projections

Figure 1. A trojan invariant torus for the ER3BP plotted in the (ξ,η)(\xi,\eta), (ξ˙,η˙)(\dot{\xi},\dot{\eta}), (ξ,ξ˙)(\xi,\dot{\xi}), and (η,η˙)(\eta,\dot{\eta}) projections. The length 601 trajectory is given in red, while the computed invariant torus with lines that are constant in coordinates are given in gray.

Our goal is to compute an invariant torus SS and its rotation vector ω\boldsymbol{\omega} from a trajectory Ft(x)F^t(x) for 0≤t<T0\leq t<T. To parameterize the invariant torus, we must define an observable function h:M→RD\mathbf{h}:\mathcal{M}\to\mathbb{R}^{D}, D≥2dD\geq2d, from the state space into Euclidean space so that the torus can be represented as

h(S(θ))=∑k∈Zdhke2πiθ⋅k.\mathbf{h}(S(\boldsymbol{\theta}))=\sum_{\mathbf{k}\in\mathbb{Z}^{d}}\mathbf{h}_{\mathbf{k}}e^{2\pi i\boldsymbol{\theta}\cdot\mathbf{k}}.

For the ER3BP, this function is simply the identity h:(ξ,p)↦(ξ,p)\mathbf{h}:(\boldsymbol{\xi},\mathbf{p})\mapsto(\boldsymbol{\xi},\mathbf{p}). However, many other smooth maps could be chosen, such as a different coordinate system or a delay embedding. In the more general case that the underlying state space M\mathcal{M} is not Euclidean, the map h\mathbf{h} allows us to still use Fourier series to represent the geometry. As long as h(S)\mathbf{h}(S) is injective, the map h\mathbf{h} can be pulled back to give an invariant torus on the regular state space.

When the observable is composed with an invariant torus trajectory, we find that

h(Ft(S(0)))=h(S(tω))=∑khkλkt,λk=e2πiω⋅k.(2)\mathbf{h}(F^t(S(0)))=\mathbf{h}(S(t\boldsymbol{\omega}))=\sum_{\mathbf{k}}\mathbf{h}_{\mathbf{k}}\lambda_{\mathbf{k}}^t,\qquad\lambda_{\mathbf{k}}=e^{2\pi i\boldsymbol{\omega}\cdot\mathbf{k}}. \tag*{(2)}

The effect is that spatial wavenumbers k∈Zd\mathbf{k}\in\mathbb{Z}^{d} of the trajectory are transformed to temporal frequencies ω⋅k∈T\boldsymbol{\omega}\cdot\mathbf{k}\in\mathbb{T}, where the Diophantine condition guarantees that ω⋅k1≠ω⋅k2\boldsymbol{\omega}\cdot\mathbf{k}_1\ne\boldsymbol{\omega}\cdot\mathbf{k}_2 for k1≠k2\mathbf{k}_1\ne\mathbf{k}_2. Given this representation, a more refined statement of our goal is how to recover the Fourier coefficients hk\mathbf{h}_{\mathbf{k}} and the rotation vector ω\boldsymbol{\omega} knowing h(Ft(S(0)))\mathbf{h}(F^t(S(0))), for t=0,1,…,Nt=0,1,\ldots,N for some large NN.

The process for recovering the torus will proceed in two stages, where first the rotation vector is found, and then the Fourier coefficients are computed. However, we will explain the process in the opposite order. to motivate the choices we made for computing the rotation vector. So, for the rest of this section, assume that ω\omega is known, and we simply want to find the coefficients hk\mathbf{h}_k from the signal.

Weighted Birkhoff averages vs. least squares

The first of two methods we consider to compute Fourier coefficients is what we refer to as the projection method [29]. It depends on the inverse Fourier transform formula

hk=∫Tdh(S(θ))e−2πik⋅θ dθ.(3)h_k = \int_{\mathbb{T}^d} h(S(\theta))e^{-2\pi i k\cdot\theta}\,\mathrm{d}\theta. \tag*{(3)}

Because we cannot sample SS at will, we connect the quadrature to the data we have, namely a single trajectory.

The connection between quadrature of the form (3) and trajectories is the Birkhoff ergodic theorem, which states that integrals over invariant sets can be related to time averages over trajectories. Let x=S(0)x=S(0) be a point on an invariant torus SS with a non-resonant rotation vector ω\omega, then the rotation operator τω:θ↦θ+ω\tau_\omega:\theta\mapsto\theta+\omega is ergodic on Td\mathbb{T}^d. Thus, the Birkhoff ergodic theorem tells us that the finite-time averages of continuous observables g:M→Rdg:\mathcal{M}\to\mathbb{R}^d given by

BT[g](x)=1T∑t=0T−1g∘Ft(x)=1T∑t=0T−1(g∘S)∘τωt(0)B_T[g](x)=\frac{1}{T}\sum_{t=0}^{T-1}g\circ F^t(x)=\frac{1}{T}\sum_{t=0}^{T-1}(g\circ S)\circ\tau_\omega^t(0)

converge as T→∞T\to\infty to a unique limit, defined by the integral

B[g](x)=lim⁡T→∞BT[g](x)=∫Tdg(S(θ)) dθ,(4)B[g](x)=\lim_{T\to\infty}B_T[g](x)=\int_{\mathbb{T}^d}g(S(\theta))\,\mathrm{d}\theta, \tag*{(4)}

where we have used the fact that the unique invariant measure of non-resonant rotational dynamics on Td\mathbb{T}^d is the uniform measure.

Restricting to the specific case of finding Fourier coefficients, the function we want to average is g(S(θ))=h(S(θ))e−2πik⋅θg(S(\theta))=h(S(\theta))e^{-2\pi i k\cdot\theta}. Substituting this into the ergodic formula, we can approximate the Fourier coefficients by the average

hk≈1T∑t=0T−1λk−th∘Ft(x).(5)h_k\approx\frac{1}{T}\sum_{t=0}^{T-1}\lambda_k^{-t}h\circ F^t(x). \tag*{(5)}

As long as we have access to the observation of the trajectory h∘Ft(x)h\circ F^t(x) and the rotation vector ω\omega (so that λk\lambda_k is known), we can apply the above ergodic formula to approximate the Fourier coefficients.

The rate of convergence of Birkhoff averages depends on the type of underlying trajectory. Assuming xx is on an invariant torus with a Diophantine rotation vector and the observable and dynamics are sufficiently smooth, it is straightforward to show that ∥BT[h](x)−B[h](x)∥=O(T−1)\lVert B_T[h](x)-B[h](x)\rVert=O(T^{-1}). Fortunately, the rate of convergence for invariant tori can be accelerated by appropriately weighting the sum as

WBT[g](x)=∑t=0T−1wtg∘Ft(x),WB_T[g](x)=\sum_{t=0}^{T-1}w_tg\circ F^t(x),

where the weights wtw_t are sampled from a compactly supported function w∈C∞([0,1])w\in C^\infty([0,1]) function via

wt=[∑s=0T−1w(s+1T+1)]−1w(t+1T+1),w(x)=exp⁡(−1x(1−x)).w_t=\left[\sum_{s=0}^{T-1}w\left(\frac{s+1}{T+1}\right)\right]^{-1}w\left(\frac{t+1}{T+1}\right),\qquad w(x)=\exp\left(-\frac{1}{x(1-x)}\right).

This technique is known as a weighted Birkhoff average. The error ∥WBT[g](x)−B[g](x)∥\lVert WB_T[g](x)-B[g](x)\rVert for hh, SS, and M\mathcal{M} in CMC^M converges as O(T−m)O(T^{-m}) provided that M>d+mνM>d+m\nu [24], and the error for the analytic system can converge as O(e−rTξ)O(e^{-rT^\xi}) for some rates r>0r>0 and 0<ξ≤10<\xi\leq1, depending on the dimension and the torus [27].

We note that ergodic averages of chaotic trajectories converge at a slower convergence rate than for invariant tori [25]. The empirical rate is approximately O(T−1/2)O(T^{-1/2}) regardless of the weighting, where the exponent is due to the heuristic that a chaotic average should converge approximately according to a central limit theorem. The discrepancy of rates between chaos and tori allows for the weighted Birkhoff average to efficiently classify trajectories. While sorting trajectories is not the focus of this paper, this is a major motivation for computing invariant tori from trajectories.

We note that the validity of the projection formula (5) relies upon an assumption of orthogonality between Fourier modes. This is a good assumption in the context of spatial averages, as

⟨e2πik⋅⋆,e2πik′⋅⋆⟩=∫Tde2πi(k′−k)⋅θ dθ={1k=k′,0k≠k′.(6)\left\langle e^{2\pi i\mathbf{k}\cdot\star},e^{2\pi i\mathbf{k}'\cdot\star}\right\rangle=\int_{\mathbb{T}^{d}}e^{2\pi i(\mathbf{k}'-\mathbf{k})\cdot\boldsymbol{\theta}}\,\mathrm{d}\boldsymbol{\theta}= \begin{cases} 1 & \mathbf{k}=\mathbf{k}',\\ 0 & \mathbf{k}\ne\mathbf{k}'. \end{cases} \tag*{(6)}

This orthogonality relationship does not exactly hold for the finite-time ergodic average, however, where the approximate integral

⟨e2πik⋅⋆,e2πik′⋅⋆⟩≈∑t=0T−1wtλk−tλk′t\left\langle e^{2\pi i\mathbf{k}\cdot\star},e^{2\pi i\mathbf{k}'\cdot\star}\right\rangle\approx\sum_{t=0}^{T-1}w_t\lambda_{\mathbf{k}}^{-t}\lambda_{\mathbf{k}'}^t

is nonzero for all k≠k′\mathbf{k}\ne\mathbf{k}'. Moreover, this error increases as the difference between frequencies grows, owing to the fact that higher Fourier coefficients are increasingly non-smooth.

Thinking of the weighted Birkhoff average as a quadrature rule on Td\mathbb{T}^{d}, it is informative to compare to the trapezoidal rule. The trapezoidal rule is a Gaussian quadrature rule T\mathbb{T}, meaning its tensor product rule exactly preserves the orthogonality relation (6) for ∥k−k′∥∞<2Ktrap−1\lVert\mathbf{k}-\mathbf{k}'\rVert_{\infty}<2K_{\mathrm{trap}}-1, where KtrapK_{\mathrm{trap}} grid points in each direction [38]. The projection that one obtains from the trapezoidal rule is the orthogonal discrete Fourier transform, which is what allows the continuous projection rule to also be a discrete one. On the other hand, because the weighted Birkhoff average is not orthogonal, the continuous projection formula will only be an approximation to the true discrete projection.

To tackle the non-orthogonality, we use the least-squares approach

min⁡{hkn}∑t=0T−1ct∥(∑n=1Nhknλknt)−h(Ft(x))∥X2=min⁡X∥AX−B∥W2,(7)\min_{\{h_{\mathbf{k}_n}\}}\sum_{t=0}^{T-1}c_t\left\lVert\left(\sum_{n=1}^{N}h_{\mathbf{k}_n}\lambda_{\mathbf{k}_n}^{t}\right)-h(F^t(x))\right\rVert^2_X=\min_X\lVert AX-B\rVert_W^2, \tag*{(7)}

where the weights ctc_t are either ergodic average ct=1/Tc_t=1/T or the weighted average ct=wtc_t=w_t, A∈CT×NA\in\mathbb{C}^{T\times N} is the matrix representing the NN Fourier modes kn∈Zd\mathbf{k}_n\in\mathbb{Z}^{d}

A=(Λk1⋯ΛkN),Λk=(λk0⋮λkT−1),(8)A=\begin{pmatrix}\Lambda_{\mathbf{k}_1}&\cdots&\Lambda_{\mathbf{k}_N}\end{pmatrix},\qquad \Lambda_{\mathbf{k}}=\begin{pmatrix}\lambda_{\mathbf{k}}^0\\ \vdots\\ \lambda_{\mathbf{k}}^{T-1}\end{pmatrix}, \tag*{(8)}

the matrices X∈CN×DX\in\mathbb{C}^{N\times D} and B∈RT×DB\in\mathbb{R}^{T\times D} are the frequency and time representations of the signal

X=(hk1Thk2T⋮hkNT),B=(h(F0(x))Th(F1(x))T⋮h(FT−1(x))T),X=\begin{pmatrix}h_{\mathbf{k}_1}^{\mathsf{T}}\\h_{\mathbf{k}_2}^{\mathsf{T}}\\ \vdots\\h_{\mathbf{k}_N}^{\mathsf{T}}\end{pmatrix},\qquad B=\begin{pmatrix}h(F^0(x))^{\mathsf{T}}\\h(F^1(x))^{\mathsf{T}}\\ \vdots\\h(F^{T-1}(x))^{\mathsf{T}}\end{pmatrix},

and ∥⋆∥W\lVert\star\rVert_W is the weighted norm

∥M∥W2=tr⁡(M∗WM),W=Diag⁡(c0,…,cT−1),\lVert M\rVert_W^2=\operatorname{tr}(M^*WM),\qquad W=\operatorname{Diag}(c_0,\ldots,c_{T-1}),

where M∗M^* is the conjugate transpose of MM. The least-squares system solution can be represented exactly using the normal matrix formula as

X=(A∗WA)−1(A∗WB).X=(A^*WA)^{-1}(A^*WB).

In the formula above, the (weighted) Birkhoff average for the modes kn\mathbf{k}_n is simply the A∗WBA^*WB term. Then, the least-squares solution corrects the non-orthogonality of that approach by inverting the normal matrix A∗WAA^*WA. (In practice, we solve the system by performing a QR factorization QR=W1/2AQR=W^{1/2}A and computing X=R−1Q∗W1/2BX=R^{-1}Q^*W^{1/2}B.)

Now that we have two methods — projection and least-squares — we return to the question of how many modes knk_n to compute from the signal. In 1D, a partial answer to this question was given in [30], where the condition number of the least-squares problem was used to determine the size. However, the anisotropy of the higher-dimensional problem requires resolutions in different directions for the best interpolation, which the condition number argument is insufficient for. This issue compounds the already mentioned issue of a lack of orthogonality, meaning increasing resolution can worsen results.

To demonstrate the issue, we return to our example trajectory in the ER3BP. Using the method of § 3, we find the rotation vector to be ω=(0.00344,0.07921)\boldsymbol{\omega} = (0.00344, 0.07921), where the first and second entries correspond to rotating the “short” and “long” ways around the torus respectively. Using this frequency, we compute Fourier coefficients from the projection and least-squares method, using both the unweighted and the weighted versions. To evaluate the residual, the methods are all trained on the first T=550T = 550 points of the trajectory for wavenumbers ∣kj∣≤Kj\lvert k_j\rvert\le K_j, where we scan different resolutions 0≤K1≤80 \le K_1 \le8 and 0≤K2≤250 \le K_2 \le25. For each method and resolution (K1,K2)(K_1, K_2), we form an approximate invariant torus of the form

h^(θ)≈h∘S(θ)=∑k1=−K1K1∑k2=−K2K2hke2πik⋅θ.\hat{h}(\theta) \approx h \circ S(\theta) = \sum_{k_1=-K_1}^{K_1} \sum_{k_2=-K_2}^{K_2} h_k e^{2\pi i k\cdot\theta}.

This torus is validated by computing the relative error between the predicted dynamics on the next M=51M = 51 points on the trajectory and the real dynamics as

Rh2=1Rh02∑t=T+1T+M∥h(Ft(x))−h^(θ+ωt)∥2,Rh02=∑t=T+1T+M∥h(Ft(x))∥2.(9)R_h^2 = \frac{1}{R_{h_0}^2} \sum_{t=T+1}^{T+M} \left\lVert h(F^t(x)) - \hat{h}(\theta+\boldsymbol{\omega}t) \right\rVert^2,\qquad R_{h_0}^2 = \sum_{t=T+1}^{T+M} \left\lVert h(F^t(x)) \right\rVert^2. \tag*{(9)}

In Figure 2, we plot the validation error as a function of K1K_1 and K2K_2 for each coefficient recovery method. Then, in the first four rows of Table 1, we report the optimal validation error, along with the optimal values of K1K_1 and K2K_2. We find that the least-squares methods for finding Fourier coefficients outperform the projection methods by nine orders of magnitude, with the best performance being the (K1,K2)=(6,18)(K_1, K_2) = (6, 18) unweighted least squares.

Figure 2. The validation error (9) for the (left) projection and (right) least-squares methods, for both the unweighted and weighted versions of each method. The red path on the unweighted least-squares method indicates the path of the adaptive method (see § 2.2).

MethodLLBest Error RhR_hK1K_1K2K_2
ProjectionII2.67×10−22.67 \times10^{-2}02
Weighted ProjectionII1.87×10−21.87 \times10^{-2}024
Least SquaresII1.07×10−111.07 \times10^{-11}618
Weighted Least SquaresII7.86×10−117.86 \times10^{-11}518
Least Squares(1011)\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}1.61×10−61.61 \times10^{-6}88
Least Squares(1021)\begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}9.23×10−69.23 \times10^{-6}145
Least Squares(2111)\begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}3.64×10−53.64 \times10^{-5}510

Table 1. Best validation errors and their resolutions. The first four lines match Figure 2. The final three lines give the unweighted least-squares validation error for three valid rotation vector transformations ω′=Lω\omega' = L\omega.

There are two main takeaways from this numerical experiment. The first takeaway is that for the trajectory length of 550 iterations, the Fourier modes for both the projection and weighted projection methods are far from being orthogonal, leading to the drastic errors. This can be attributed to the small value of ω1=0.00344\omega_1 = 0.00344, as there are only 3 full periods of e2πiω1te^{2\pi i\omega_1t} over the course of the considered trajectory. As the trajectory length increases, the weighted projection would converge much faster than the unweighted projection method, but this is only a limiting result, and cannot necessarily be applied for “short” trajectories. One could fix this problem by running a longer trajectory, but the difference in integration time can easily exceed the difference in computation time between the projection and least-squares methods. Moreover, this trajectory length is sufficient to find the rotation vector to high accuracy, so we do not need more information for that part of the problem.

The second takeaway is that the least-squares method can achieve very accurate results regardless of the weighting, but only if the anisotropy is accounted for. Clearly, if we had only considered projections where K1=K2K_1 = K_2, a validation error on the order of 10−1010^{-10} could never have been achieved, as the high Fourier modes in the θ1\theta_1 direction would overfit while the modes in the θ2\theta_2 direction would underfit.

Adaptivity in the number of Fourier modes

While we have shown that an anisotropic Fourier representation of the invariant torus can achieve good validation error, we have not yet described how to determine the correct resolution. To do so, consider a length TT trajectory of observations h(Ft(x))h(F^t(x)), the rotation vector ω\omega, and a validation fraction 0<γ<10 < \gamma< 1. To address this, we attempt to solve the following problem:

min⁡KRh2[h^],h^(θ)=∑−K⪯k⪯Khke2πik⋅θ,(10)\min_{\mathbf{K}} R_h^2[\hat{h}], \qquad\hat{h}(\theta) = \sum_{-\mathbf{K}\preceq k\preceq\mathbf{K}} h_k e^{2\pi i k\cdot\theta}, \tag*{(10)}

where K=(K1,…,Kd)\mathbf{K} = (K_1,\ldots,K_d) is the Fourier resolution of the approximate torus h^\hat{h}, determined by solving the unweighted least-squares system (7) on the first ⌊(1−γ)T⌋\lfloor(1-\gamma)T\rfloor elements of the trajectory, where ⌊⋆⌋:R→Z\lfloor\star\rfloor:\mathbb{R}\to\mathbb{Z} is the floor function. The objective for each value is computed by Eqs. (9) and (10), computed on the final 1−⌊(1−γ)T⌋1-\lfloor(1-\gamma)T\rfloor points on the trajectory. In this paper, we fix γ=0.05\gamma= 0.05. In essence, the minimization solves for the invariant torus that best predicts the dynamics.

The method of optimization is simple: we perform a discrete descent on the validation error (see Figure 2). For the optimization, there are two hyperparameters: a “hill tolerance” η≥1\eta\ge1 and a maximum number of Fourier coefficients Kmax⁡≤⌈(1−γ)T⌉K_{\max} \le\lceil(1-\gamma)T\rceil. The descent is initialized with a constant interpolant, corresponding to Kj=0K_j = 0 for all 1≤j≤d1 \le j \le d. To determine the next resolution K\mathbf{K}, we increase the resolution in each coordinate and compute the residual R^h(j)=R^h(j)(K+ej)\hat{R}_h^{(j)} = \hat{R}_h^{(j)}(\mathbf{K}+\mathbf{e}_j) for 1≤j≤d1 \le j \le d, where ej∈Zd\mathbf{e}_j \in\mathbb{Z}^d is the unit vector in the jj direction. After computing the residuals, we move in the direction of steepest descent j=arg⁡min⁡jR^h(j)j = \arg\min_j \hat{R}_h^{(j)} (note that residual need not decrease). Along the descent, we keep track of the value of K=K∗\mathbf{K} = \mathbf{K}^* that gives the smallest residual Rh(K∗)R_h(\mathbf{K}^*). We stop the descent when there is no candidate direction such that the residual improves R^h(K+ej)<ηR^h(K∗)\hat{R}_h(\mathbf{K}+\mathbf{e}_j) < \eta\hat{R}_h(\mathbf{K}^*) and the resolution is bounded by K=∏j(2Kj+1)≤Kmax⁡\mathbf{K} = \prod_j(2K_j+1) \le K_{\max}.

In the case that η=1\eta= 1, the descent stops when any increase in resolution would increase the residual. However, we have found that this can stop the descent in local minimum, while the global minimum may have a higher resolution. In these cases, values of η>1\eta> 1 allow the descent algorithm to traverse ridges in the validation error where it could possibly find better minima. There is no guarantee that this algorithm finds the global minimum of the validation error, but choosing η>1\eta> 1 (typically we choose η=10\eta= 10) allows for a better chance.

The primary benefit of this algorithm is that it is practical. A worst-case asymptotic cost of this algorithm is O(dTKmax⁡2)O(dTK_{\max}^{2}), where dd is the dimension of the torus and TT is the length of the trajectory. This cost is dominated by the computation of Rh(K+ej)R_h(\mathbf{K} + \mathbf{e}_j) at each step, where the solutions of the least-squares problems are computed by QR update formulas at each step (see Appendix § 6 for details). However, the asymptotic bound is pessimistic because the stopping condition is often met before the worst-case time. More often, if KK is the resolution of the largest least-squares problem solved and K=∏j(2Kj+1)≤(1−γ)TK = \prod_j (2K_j + 1) \leq(1 - \gamma)T is the width of the least-squares problem, then the cost is given by O(dTK2)O(dTK^2).

Better results could be obtained, e.g., by performing a search over all possible values of KK, but this would be significantly more expensive. This may be practical if FF is very expensive to compute. Otherwise, the value of (10) can be reduced much more simply by computing a longer trajectory. Moreover, the parameterization method [4] can be used to iteratively improve an initial guess of an invariant torus when the found torus needs to be refined (this also gives an avenue to prove the existence of the invariant torus, see [12]).

Non-uniqueness of the rotation vector

We have seen from the ER3BP example that the least-squares method of computing Fourier coefficients can dramatically outperform the weighted Birkhoff average projection method. However, up to now, there is an issue that we have ignored: the parameterization of an invariant torus is not unique.

To investigate the non-uniqueness, consider two parameterizations of the same invariant torus SS and S′S' with non-resonant rotation vectors ω\omega and ω′\omega'. Then, it must be the case that S′=S∘GS' = S \circ G where G:Td→TdG : \mathbb{T}^{d} \to\mathbb{T}^{d} is an automorphism of the torus regarded as a smooth manifold. Automorphisms of the torus can be decomposed as

G=L∘G0,G = L \circ G_0,

where G0G_0 induces the identity on the singular homology H1(Td)≈ZdH_1(\mathbb{T}^{d}) \approx\mathbb{Z}^{d} and L∈GL(d,Z)L \in GL(d,\mathbb{Z}) induces a nontrivial isomorphism on H1(Td)H_1(\mathbb{T}^{d}) when L≠IL \ne I. Here, GL(d,Z)GL(d,\mathbb{Z}) is the group of integer matrices L∈Zd×dL \in\mathbb{Z}^{d \times d} with integer-valued inverses L−1∈Zd×dL^{-1} \in\mathbb{Z}^{d \times d}. The inverse condition is satisfied if and only if det⁡L=±1\det L = \pm1. By requiring that S∘τω=S∘G∘τω′S \circ\tau_\omega= S \circ G \circ\tau_{\omega'}, one finds that ω=Lω′\omega= L\omega' and G0(θ)=θ+ΔG_0(\theta) = \theta+ \Delta for some constant Δ∈Td\Delta\in\mathbb{T}^{d}. This tells us that the non-uniqueness in torus representation can be expressed by two quantities: Δ\Delta for the choice of origin and the LL for the choice of homology generators.

The shift Δ\Delta is easily fixed by requiring h(S(0))=h(x)h(S(0)) = h(x), but the best choice of L∈GL(d,Z)L \in GL(d,\mathbb{Z}) is less intuitive. To see the numerical implications of the choice of LL, we first recognize that Fourier coefficients change under the automorphism as

h(S′(θ′))=∑k′hL−Tk′e−2πik′⋅θ′,h(S'(\theta')) = \sum_{\mathbf{k}'} h_{L^{-\mathsf{T}}\mathbf{k}'} e^{-2\pi i\mathbf{k}'\cdot\theta'},

where k′=L−Tk\mathbf{k}' = L^{-\mathsf{T}}\mathbf{k}. In this way, the choice of LL, and therefore the choice of ω′\omega', can be identified with a choice of the wavenumber ordering.

Within this non-uniqueness lies a problem: a Fourier representation for one parameterization of an invariant torus might lie neatly within a rectangular domain of wavenumbers, while the transformed torus may have a skewed representation. To see this, recall the ER3BP example and let

L1=(1011),L_1 = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix},

(We immediately recognize that L1∈GL(2,Z)L_1 \in GL(2,\mathbb{Z}), as its inverse is in Z2×2\mathbb{Z}^{2 \times2} and it has determinant 1.) In Figure 3, we show how the Fourier coefficients from the original parameterization change under this transformation. We see that what was once a vertical exponentially decaying function is transformed to be diagonal. The upshot is that a resolution of (K1,K2)=(24,18)(K_1,K_2) = (24,18) would be needed to capture all of the same Fourier modes for the sheared torus that are captured in a resolution of (K1,K2)=(6,18)(K_1,K_2) = (6,18) for the original. So, as long as we compute the Fourier coefficients over a rectangle, it is preferable to choose the homology generators with the most compact representation.

Figure 3. A schematic of how the Fourier coefficients for the ER3BP example shear under the transformation L1L_1.

To make this observation precise, in Table 1, we scan over K1K_1 and K2K_2 to find the best validation error (9) for the transformed torus. We perform this scan for the transformation L1L_1, as well as two other matrices

L2=(1021),L3=(2111).L_2 = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}, \qquad L_3 = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}.

In all three cases, the best validation error reduces by 4 orders of magnitude, showing that the choice of homology can significantly change the quality of the computed invariant torus. In Section 3.3, we will return to this detail on parameterization to determine a “best” rotation vector.

Computing the rotation vector

Assuming the rotation vector is known, we have seen that it is possible to obtain an accurate Fourier representation of an invariant torus from a trajectory. Now, we turn our attention to finding the rotation vector itself. Before explaining the details in Secs. 3.1, 3.2, and 3.3, we show an example of why it is more difficult to compute high-dimensional rotation vectors than in one dimension.

For the example, consider the coupled standard map

xt+1=xt+yt+1,yt+1=yt+12πKsmsin⁡(2πxt),Ksm=(0.40.20.20.5),(11)\mathbf{x}_{t+1} = \mathbf{x}_t + \mathbf{y}_{t+1}, \qquad\mathbf{y}_{t+1} = \mathbf{y}_t + \frac{1}{2\pi}K_{\mathrm{sm}}\sin(2\pi\mathbf{x}_t), \qquad K_{\mathrm{sm}} = \begin{pmatrix} 0.4 & 0.2 \\ 0.2 & 0.5 \end{pmatrix}, \tag*{(11)}

where x∈T2\mathbf{x} \in\mathbb{T}^2, y∈R2\mathbf{y} \in\mathbb{R}^2 and the function sin⁡(⋅)\sin(\cdot) is taken elementwise. The symplectic map on the state space T2×R2\mathbb{T}^2 \times\mathbb{R}^2 is defined as F:(xt,yt)↦(xt+1,yt+1)F : (\mathbf{x}_t, \mathbf{y}_t) \mapsto(\mathbf{x}_{t+1}, \mathbf{y}_{t+1}). In Figure 4, we plot four projections of a trajectory starting at x=(0.1,0.1)\mathbf{x} = (0.1, 0.1) and y=(0.1,0.01)\mathbf{y} = (0.1, 0.01). The rotation vector is ω=(0.02487,0.02414)\boldsymbol{\omega} = (0.02487, 0.02414), as is determined through the methods within this section.

Four projections of a trajectory of the coupled standard map (11)

Figure 4. Four projections of a trajectory of the coupled standard map (11).

There are three things that make this torus specifically difficult:

  1. The torus is far from perturbative. If (x1,y1)(x_1, y_1) was uncoupled from (x2,y2)(x_2, y_2) (i.e. KsmK_{\mathrm{sm}} is diagonal), the 2D invariant torus would be a tensor product of two 1D invariant tori. So, when plotted in the (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) planes, we would observe a non-self-intersecting projection. This is not the case we see in Figure 4; it is clear that the dynamics of (x1,y1)(x_1, y_1) is strongly coupled with the dynamics of (x2,y2)(x_2, y_2). This makes the question of continuation to this torus very difficult. It may be possible to continue from a tensor product of 1D tori or even the Ksm=0K_{\mathrm{sm}} = 0 system, but this would require a method that is robust to resonant bifurcations.

2. Winding arguments break down. Consider an invariant torus from the coupled standard map (11) where y∈R2\boldsymbol{y} \in\mathbb{R}^{2} is a graph over x∈T2\boldsymbol{x} \in\mathbb{T}^{2}. In this case, one can take averages of the “momentum” observable hy:(x,y)↦yh_{\boldsymbol{y}} : (\boldsymbol{x}, \boldsymbol{y}) \mapsto\boldsymbol{y} to find the rotation vector:

ω=B[hy](x0,y0).\boldsymbol{\omega} = \mathcal{B}[h_{\boldsymbol{y}}](\boldsymbol{x}_{0}, \boldsymbol{y}_{0}).

However, the example torus in Figure 4 does not have the graph property. In some cases this can be overcome by a simple coordinate transformation. For this example, the complicated high-dimensional geometry of the torus in Figure 4 makes it difficult to intuit or compute such a coordinate transformation.

3. The torus is dominated by high-wavenumber Fourier modes. One seemingly straightforward method to compute rotation numbers is by a discrete Fourier transform (DFT). If the trajectory’s signal is truly of the form (2), then one expects that a DFT will have peaks near the frequencies Ωk=ω⋅k\Omega_{\boldsymbol{k}} = \boldsymbol{\omega} \cdot\boldsymbol{k}. So, in principle, the peaks of that Fourier transform have all of the necessary information.

For a first attempt at a DFT, let h:T2×R2→R4h : \mathbb{T}^{2} \times\mathbb{R}^{2} \to\mathbb{R}^{4} be an observable function defined by

h(x,y)=((y1+R)cos⁡(2πx1)(y1+R)sin⁡(2πx1)(y2+R)cos⁡(2πx2)(y2+R)sin⁡(2πx2)),(12)h(\boldsymbol{x}, \boldsymbol{y}) = \begin{pmatrix} (y_{1} + R)\cos(2\pi x_{1}) \\ (y_{1} + R)\sin(2\pi x_{1}) \\ (y_{2} + R)\cos(2\pi x_{2}) \\ (y_{2} + R)\sin(2\pi x_{2}) \end{pmatrix}, \tag*{(12)}

where R=0.5R = 0.5. Then, we compute a C∞C^{\infty}-windowed fast Fourier transform of a length 10000 trajectory of observables. The results of the DFT are shown in Figure 5, where the spectrum appears to be structured with many peaks. However, this still leaves two questions:

Power spectrum showing the 60 highest peaks and the marked rotation vectors

Figure 5. A C∞C^{\infty}-windowed discrete Fourier transform of a length 10000 trajectory of the 2D standard map (11) shown in Figure 4 with the observable function in Eq. (12). The 60 highest peaks (Ωj,Hj)(\Omega_j, H_j) for 1≤j≤601 \leq j \leq60 are plotted in black dots, cf. Table 2. The only two peaks in the 15 largest that form a valid rotation vector are marked with red stars (j=12,14j = 12, 14). The optimal rotation vector for the anisotropy of the invariant torus is marked in magenta ‘x’s (j=31,60j = 31, 60).

  • (a) Are the DFT frequencies accurate enough?

  • (b) Which peaks correspond to a valid rotation vector?

For Question (a), the answer is no. A length TT trajectory yields a DFT frequency resolution of O(T−1)O(T^{-1}), which is not enough to practically achieve the parameterization accuracies of Sec. 2. In Sec. 3.1, we solve this problem using an extrapolation method — Birkhoff reduced rank extrapolation (Birkhoff RRE) — which has the benefit of computing many frequencies Ωj≈ω⋅kj\Omega_j \approx\boldsymbol{\omega} \cdot\boldsymbol{k}_j simultaneously to high accuracies. We then project the frequency modes back onto the trajectory, giving the coefficients Hj≈hkjH_j \approx h_{\boldsymbol{k}_j} ordered by the magnitudes H1≥H2≥⋯≥HJ∗H_1 \geq H_2 \geq\cdots\geq H_{J^*} where Hj=∥Hj∥H_j = \lVert H_j \rVert. In this way, the invariant torus is represented as

h(Ft(x))=∑j=−J∗J∗Hje2πiΩjt,h(F^t(\boldsymbol{x})) = \sum_{j=-J^*}^{J^*} H_j e^{2\pi i\Omega_j t},

where we use the convention that Ω−j=−Ωj\Omega_{-j} = -\Omega_j and Ω0=0\Omega_0 = 0.

For Question (b), we note that for 1D invariant tori in 2D Euclidean space, the answer is almost always simple: choose the highest peak in the spectrum to be the rotation number (i.e. ω=Ω1\omega= \Omega_1). This works because 1D tori embedded in 2D space cannot self-intersect, meaning that the k=1k = 1 Fourier mode is almost always the most prominent. Because 2D tori in 4D space are not co-dimension 1, they are free to wind around themselves in complicated ways, meaning this reasoning breaks down for higher dimensions. It is still the case that our desired rotation vector corresponds to two peaks, marked by the magenta ‘x’s in Figure 5, but it is not obvious why one would choose those peaks from the power spectrum alone. The best frequencies are far from the most prominent, and essentially resemble the rest of the observed frequencies, a property that is typical of filamentary invariant tori.

In § 3.2, we start by solving the simpler problem of finding a valid rotation vector (Ωj1,Ωj2)(\Omega_{j_1}, \Omega_{j_2}) from the measured frequencies Ωj\Omega_j. However, it is still a nontrivial question as to when two frequencies are a valid rotation vector. To see this, recall from § 2.3 that any valid rotation vector (Ωj1,Ωj2)(\Omega_{j_1}, \Omega_{j_2}) can be represented by a transformation L∈GL(d,Z)L \in GL(d, \mathbb{Z}) to the optimal rotation vector as

(Ωj1Ωj2)=Lω,\begin{pmatrix} \Omega_{j_1} \\ \Omega_{j_2} \end{pmatrix} = L\boldsymbol{\omega},

where det⁡L=±1\det L = \pm1. We know the observed frequencies Ωj=ω⋅kj\Omega_j = \boldsymbol{\omega} \cdot\boldsymbol{k}_j for some wavenumbers kj\boldsymbol{k}_j, so we can identify the matrix LL as

L=(kj1Tkj2T).L = \begin{pmatrix} \boldsymbol{k}_{j_1}^{\mathsf{T}} \\ \boldsymbol{k}_{j_2}^{\mathsf{T}} \end{pmatrix}.

By checking whether det⁡L=±1\det L = \pm1 (and therefore it is in GL(d,Z)GL(d, \mathbb{Z})), this gives us a simple a posteriori test to determine whether a rotation vector is valid.

In Table 2, we report the powers, frequencies, and the (so far undiscovered) wavenumbers of the 15 highest peaks in Figure 5, computed by the methods of § 3.1. We notice that the 8 most prominent frequencies

jjHj=∥Hj∥=∥hkj∥H_j = \lVert\mathbf{H}_j\rVert= \lVert\mathbf{h}_{\mathbf{k}_j}\rVertΩj=ω⋅kj\Omega_j = \boldsymbol{\omega}\cdot\mathbf{k}_j(kj)1(k_j)_1(kj)2(k_j)_2
12.0577e−012.0577\mathrm{e}{-01}0.12068805
22.055901e−012.055901\mathrm{e}{-01}0.07241303
37.535484e−027.535484\mathrm{e}{-02}0.04827502
47.485108e−027.485108\mathrm{e}{-02}0.19310108
54.106522e−024.106522\mathrm{e}{-02}0.14482606
63.691528e−023.691528\mathrm{e}{-02}0.241376010
71.913862e−021.913862\mathrm{e}{-02}0.265514011
81.845954e−021.845954\mathrm{e}{-02}0.16896307
91.747752e−021.747752\mathrm{e}{-02}0.12142414
101.475290e−021.475290\mathrm{e}{-02}0.313789013
111.368350e−021.368350\mathrm{e}{-02}0.1199531-6
121.113079e−021.113079\mathrm{e}{-02}0.07314812
139.119838e−039.119838\mathrm{e}{-03}0.0475401-3
149.043146e−039.043146\mathrm{e}{-03}0.04901111
157.556361e−037.556361\mathrm{e}{-03}0.0716771-4
⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots
311.986039e−031.986039\mathrm{e}{-03}0.02413801
⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots
603.211915e−043.211915\mathrm{e}{-04}0.02487310

Table 2. Locations and magnitudes of the peaks of the Fourier spectrum in Figure 5. In the final two columns, the corresponding wavenumbers of the modes are reported. The redundant complex conjugate peaks are not reported (i.e. we only report k1≥0k_1 \ge0, and k2>0k_2 > 0 if k1=0k_1 = 0)

Ωj\Omega_j for 1≤j≤81 \le j \le8 are all unusable as elements of a valid rotation vector, as LL cannot have a determinant of ±1\pm1 when kjℓ=(0,n)\mathbf{k}_{j\ell} = (0,n) for n≥2n \ge2. In fact, within the 15 highest peaks, there is only a single choice of (j1,j2)=(12,14)(j_1,j_2) = (12,14):

(Ω12Ω14)=(k12Tk14T)ω=(1211)ω.\begin{pmatrix} \Omega_{12}\\ \Omega_{14} \end{pmatrix} = \begin{pmatrix} \mathbf{k}_{12}^{\mathsf{T}}\\ \mathbf{k}_{14}^{\mathsf{T}} \end{pmatrix} \boldsymbol{\omega} = \begin{pmatrix} 1 & 2\\ 1 & 1 \end{pmatrix} \boldsymbol{\omega}.

We can confirm the above matrix has determinant −1-1, meaning (Ω12,Ω14)(\Omega_{12},\Omega_{14}) is a valid rotation vector.

In § 3.2, we use a Bayesian maximum a posteriori (MAP) estimation problem to determine a candidate rotation number and the associated wavenumbers. As input, we use the output data from Birkhoff RRE of Ω=(Ω1,…,ΩJ0)\boldsymbol{\Omega} = (\Omega_1,\ldots,\Omega_{J_0}) and powers H=(H1,…,HJ0)\mathbf{H} = (H_1,\ldots,H_{J_0}) for J0<J∗J_0 < J^*. Then, the MAP estimation problem is

max⁡ω,πP(ω,π∣Ω,H),(13)\max_{\boldsymbol{\omega},\boldsymbol{\pi}} \mathbb{P}(\boldsymbol{\omega},\boldsymbol{\pi}\mid\boldsymbol{\Omega},\mathbf{H}), \tag*{(13)}

where π:j↦kj\boldsymbol{\pi}:j\mapsto\mathbf{k}_j is a candidate wavenumber labeling. The prior of the inference problem will be informed by the assumed smoothness of the invariant torus, which encodes the belief that lower wavenumbers ∥kj∥\lVert\mathbf{k}_j\rVert should be associated with larger coefficients HjH_j.

The third step in § 3.3 is to choose an optimal rotation vector for parameterization. The rough idea of the algorithm is to compute a transformation L∈GL(d,Z)L \in GL(d,\mathbb{Z}) where ω′=Lω\boldsymbol{\omega}' = L\boldsymbol{\omega} has the property that ω1′\omega'_1 points in a shortest direction around the torus, ω2′\omega'_2 points in the second shortest direction, etc. This notion is made precise by Korkine-Zolatarev reduced lattice basis, which can be quickly computed for small dd.

Finally, in § 3.4, we describe how the overall algorithm changes to account for trajectories on island chains.

Overview of Birkhoff RRE

The primary purpose of Birkhoff RRE is to accurately translate the trajectory into frequency information. This translation occurs by way of finding 2J+12J+1 optimal coefficients c=(c−J,…,cJ)∈R2J+1\mathbf{c} = (c_{-J},\ldots,c_J) \in\mathbb{R}^{2J+1} for the

Birkhoff RRE average

BR[h](x):=∑j=−JJcjh(Fj+J(x)).(14)\mathcal{B}R[\mathbf{h}](\mathbf{x}) := \sum_{j=-J}^{J} c_j\mathbf{h}(F^{j+J}(\mathbf{x})). \tag*{(14)}

By considering the constant observable h(x)=1\mathbf{h}(\mathbf{x})=1 and substituting into Eq. (14), it is immediately clear that the sum of the coefficients must satisfy

BR[1](x)=∑j=−JJcj=1.(15)\mathcal{B}R[1](\mathbf{x})=\sum_{j=-J}^{J}c_j=1. \tag*{(15)}

In addition, because dynamics on tori are conservative, we enforce the time-reversible “palindromic” constraint

c−j=cjfor all 1≤j≤J.(16)c_{-j}=c_j \quad\text{for all } 1\leq j\leq J. \tag*{(16)}

There are J+1J+1 independent constraints in Eqs. (15) and (16), leaving JJ unknowns which fully determine c\mathbf{c}. Because the ergodic average is unique on a trajectory, it must be the case that for all t∈Z+t\in\mathbb{Z}^{+}

B[h](Ft+1(x))=B[h](Ft(x)).\mathcal{B}[\mathbf{h}](F^{t+1}(\mathbf{x}))=\mathcal{B}[\mathbf{h}](F^t(\mathbf{x})).

For DT≥JDT\geq J (recall DD is the output dimension of h\mathbf{h}), Birkhoff RRE uses this fact to define a residual

RRRE2=1TCRRE∑t=0T−1∥BR[h](Ft+1(x))−BR[h](Ft(x))∥2,R_{\mathrm{RRE}}^2=\frac{1}{TC_{\mathrm{RRE}}}\sum_{t=0}^{T-1}\left\|\mathcal{B}R[\mathbf{h}](F^{t+1}(\mathbf{x}))-\mathcal{B}R[\mathbf{h}](F^t(\mathbf{x}))\right\|^2,

where the normalization constant CRREC_{\mathrm{RRE}} is

CRRE=∑t=0T+2J−1wt∥h∘Ft+1(x)−h∘Ft(x)∥2=WBT+2J[∥h∘F−h∥2](x).C_{\mathrm{RRE}}=\sum_{t=0}^{T+2J-1}w_t\left\|\mathbf{h}\circ F^{t+1}(\mathbf{x})-\mathbf{h}\circ F^t(\mathbf{x})\right\|^2=\mathcal{W}\mathcal{B}_{T+2J}\left[\|\mathbf{h}\circ F-\mathbf{h}\|^2\right](\mathbf{x}).

The residual RRRER_{\mathrm{RRE}} can be thought of as measuring the consistency of the extrapolated Birkhoff average. By making the average independent of the initial point of the trajectory, it makes it so that BR[h](x)\mathcal{B}R[\mathbf{h}](\mathbf{x}) goes to the true value as JJ increases. Substituting Eq. (14), the residual can be written to explicitly include c\mathbf{c} as

RRRE2=1TCRRE∑t=0T−1∥∑j=−JJcjuj+J+t∥2,CRRE=∑t=02J+T−1wt∥ut∥2,ut=h(Ft+1(x))−h(Ft(x)).R_{\mathrm{RRE}}^2=\frac{1}{TC_{\mathrm{RRE}}}\sum_{t=0}^{T-1}\left\|\sum_{j=-J}^{J}c_j\mathbf{u}_{j+J+t}\right\|^2,\qquad C_{\mathrm{RRE}}=\sum_{t=0}^{2J+T-1}w_t\|\mathbf{u}_t\|^2,\qquad\mathbf{u}_t=\mathbf{h}(F^{t+1}(\mathbf{x}))-\mathbf{h}(F^t(\mathbf{x})).

This explicitly shows that the residual is quadratic in the unknowns, demonstrating that it can be equivalently written in matrix form as

RRRE2=1TCRREcTUTUc,U=(u0⋯u2J⋮⋱⋮uT−1⋯u2J+T−1).R_{\mathrm{RRE}}^2=\frac{1}{TC_{\mathrm{RRE}}}\mathbf{c}^{T}U^{T}U\mathbf{c},\qquad U=\begin{pmatrix} \mathbf{u}_0 & \cdots& \mathbf{u}_{2J}\\ \vdots& \ddots& \vdots\\ \mathbf{u}_{T-1} & \cdots& \mathbf{u}_{2J+T-1} \end{pmatrix}.

So, we find that the requirement that DT≥JDT\geq J is equivalent to the possibility of UU being at least rank JJ. In total, the least-squares problem for the coefficients c\mathbf{c} is

RRRE2=min⁡c1TCRREcTUTUc,(17)R_{\mathrm{RRE}}^2=\min_{\mathbf{c}}\frac{1}{TC_{\mathrm{RRE}}}\mathbf{c}^{T}U^{T}U\mathbf{c}, \tag*{(17)}
s.t.∑j=−JJcj=1,c−j=cjfor all 1≤j≤J.(18)\text{s.t.}\qquad\sum_{j=-J}^{J}c_j=1,\qquad c_{-j}=c_j\quad\text{for all }1\leq j\leq J. \tag*{(18)}

After substituting the constraints into the optimization, this is a least-squares problem for JJ unknowns that can be solved QR factorization (although, one must be careful in order to achieve good floating point behavior, see Appendix § 7). It is simple to observe that RRRER_{\mathrm{RRE}} for an invariant torus must go to zero at least as fast as a weighted Birkhoff average. Moreover, for d=1d = 1, the rate of convergence of the residual was proven to be faster than the best known rate for weighted Birkhoff averages [30]. The convergence theory for higher dimensions has not been investigated, however.

Assuming cJ≠0c_J \ne0, Eq. (14) can interpreted as a linear difference equation to predict the evolution of the observed trajectory as

h(F2J(x))−h0=−1cJ∑j=02J−1cj(h(Fj(x))−h0).(19)h(F^{2J}(x)) - h_0 = -\frac{1}{c_J}\sum_{j=0}^{2J-1}c_j\left(h(F^j(x)) - h_0\right). \tag*{(19)}

This is the origin of the word “extrapolation” in Birkhoff RRE. From the point of view of linear difference equations, it is straightforward to see how to obtain the trajectory’s frequencies once c\mathbf{c} is known. Like linear homogeneous differential equations, linear homogeneous difference equations of the form (19) have 2J2J homogeneous solutions φj:Z→C\varphi_j:\mathbb{Z}\to\mathbb{C} with eigenvalues ψj∈C\psi_j\in\mathbb{C} for 1≤∣j∣≤J1\leq|j|\leq J satisfying

φj(n)=ψjn,∑t=−JJctφj(t)=0.\varphi_j(n)=\psi_j^n,\qquad\sum_{t=-J}^{J}c_t\varphi_j(t)=0.

Because each cjc_j is real and we have enforced the palindromic constraint (16), it must be the case that if ψj∈C\psi_j\in\mathbb{C} is an eigenvalue, its complex conjugate ψ−j=ψj‾\psi_{-j}=\overline{\psi_j}, inverse ψj−1\psi_j^{-1}, and conjugate inverse ψj‾−1\overline{\psi_j}^{-1} are all also eigenvalues (this is the standard eigenvalue symmetry of a Hamiltonian matrix). As a result, most eigenvalues ψj\psi_j of the optimal filter are fixed to the unit circle ∣ψj∣=1|\psi_j|=1, where the inverse and conjugate coincide. Assuming there are J∗J^* of these eigenvalues where 1≤J∗≤J1\leq J^*\leq J, we define the frequencies Ωj∈T\Omega_j\in\mathbb{T} as

Ωj=arg⁡ψj:=12πilog⁡ψj(mod1).\Omega_j=\arg\psi_j:=\frac{1}{2\pi i}\log\psi_j\pmod1.

The eigenvalues are simultaneously computed by a single J×JJ\times J eigenvalue problem in O(J3)O(J^3) time; see [30] for details.

Finally, once the frequencies are known, they can be projected back onto the signal by a single least-squares problem

min⁡{Hj}∑t=0T+2J−1∥h(Ft(x))−∑j=−J∗J∗Hje2πiΩjt∥,\min_{\{H_j\}}\sum_{t=0}^{T+2J-1}\left\|h(F^t(x))-\sum_{j=-J^*}^{J^*}H_j e^{2\pi i\Omega_jt}\right\|,

where we use the convention that Ω0=0\Omega_0=0. This, like the coefficients c\mathbf{c}, is computed by QR factorization in O(TDJ2)O(TDJ^2) time, leading to an overall complexity of O(TDJ2)O(TDJ^2). We denote the squared magnitude of the coefficients as Hj2=∥Hj∥2H_j^2=\|H_j\|^2, and sort the pairs (Ωj,Hj2)(\Omega_j,H_j^2) in order of the magnitudes so that H12≥H22≥⋯≥HJ∗2H_1^2\geq H_2^2\geq\cdots\geq H_{J^*}^2.

There is currently no theory for the convergence of the frequencies Ωj\Omega_j to true values ω⋅kj\boldsymbol{\omega}\cdot\mathbf{k}_j as J→∞J\to\infty. However, as has already been indirectly demonstrated by the quality of validation error in § 2, we find that the frequencies Ωj\Omega_j often converge to near floating point accuracies in practice. This is particularly true for more prominent modes, corresponding to smaller values of jj. As jj increases we find the approximations to Ωj\Omega_j degrade. We conjecture the rate of convergence of individual frequencies of analytic functions is O(e−rJ′/d)O(e^{-rJ'/d}) for some r>0r>0, matching the rate of convergence of Fourier coefficients.

Finding an initial rotation vector

Now, we would like to determine the underlying rotation vector and wavenumbers. The input for this subsection is the output of the previous, namely a frequency vector Ω=(Ω1,…,ΩJ0)\boldsymbol{\Omega}=(\Omega_1,\ldots,\Omega_{J_0}) with corresponding the magnitudes H=(H12,…,HJ02)\mathbf{H}=(H_1^2,\ldots,H_{J_0}^2), where J0J_0 is the number of frequencies that we will use for this step, satisfying 1≤J0≤J∗1\leq J_0\leq J^*. The value of J0J_0 is defined by the user. As J0J_0 increases, so does the cost of finding the rotation vector, so it is practically important for it to be smaller than J∗J^*. For numerical stability, it is also important that J0J_0 not include frequencies where HJ0≪H1H_{J_0}\ll H_1, so always choose J0J_0 so that HJ0/H1≥ϵMAPH_{J_0}/H_1\geq\epsilon_{\mathrm{MAP}} (where the default value is ϵMAP=10−3\epsilon_{\mathrm{MAP}}=10^{-3}). Using the frequencies and magnitudes, we estimate the rotation vector and wavenumbers according to the MAP estimation problem (13), where we maximize the posterior P(ω,π∣Ω,H)\mathbb{P}(\boldsymbol{\omega},\boldsymbol{\pi}\mid\boldsymbol{\Omega},\mathbf{H}) over candidate rotation vectors ω∈Td\boldsymbol{\omega}\in\mathbb{T}^d and wavenumber mappings π:[L]→Zd\pi:[L]\to\mathbb{Z}^d from the index jj to wavenumber kk. The purpose of MAP estimation is to encode our belief for the most likely rotation vector and wavenumbers conditioned on our data. The priors for this estimation will include both a smoothness assumption on the torus coefficients H\mathbf{H} and a basic model for the accuracy of the frequencies Ω\mathbf{\Omega} returned by Birkhoff RRE.

To see why the prior of a smooth torus is necessary for the problem, consider a candidate rotation vector ω\boldsymbol{\omega} with at least one irrational element ω∈ω\omega\in\boldsymbol{\omega}. Because ω\omega is irrational, integer multiples of the frequency are dense in T\mathbb{T}; i.e. for any element of the frequency data Ωj\Omega_j, there exists a sequence of wavenumbers kℓ∈Zk_\ell\in\mathbb{Z} such that ∣ωkℓ−Ωj∣T→0\left|\omega k_\ell-\Omega_j\right|_{\mathbb{T}} \to0 as ℓ→∞\ell\to\infty. This is problematic because any errors in the frequency measurements can be pathologically explained by an unbounded sequence of wavenumbers. The smooth-torus prior is meant to counteract this type of overfitting by appropriately weighting the likelihood of observing a wavenumber by the probability that the associated mode is prominent in the torus. Additionally, the probabilistic framework helps decide between wavenumbers when multiple wavenumbers could explain a frequency due to the problem of small denominators. In this way, while the underlying problem is not fundamentally probabilistic, the MAP formalism gives a straightforward method to analyze the frequency output of the previous step.

We start by defining a prior distribution on the invariant torus of

h(S(θ))=∑khke2πik⋅θ,hk=h‾−k,Re⁡(hk),Im⁡(hk)∼N(0,σ(k)22I).h(S(\theta))=\sum_k h_k e^{2\pi i k\cdot\theta},\qquad h_k=\overline{h}_{-k},\qquad\operatorname{Re}(h_k),\operatorname{Im}(h_k)\sim\mathcal{N}\left(0,\frac{\sigma(k)^2}{2}I\right).

where σ(k)\sigma(k) for k∈Zdk \in\mathbb{Z}^d are wavenumber-dependent hyperparameters and N(μ,Σ)\mathcal{N}(\mu,\Sigma) is a joint-normal distribution with mean μ\mu and covariance Σ\Sigma defined by the probability distribution function (PDF) for x∼N(μ,Σ)x\sim\mathcal{N}(\mu,\Sigma) as

P(x)=12πdet⁡Σexp⁡(−12(x−μ)TΣ−1(x−μ)).\mathbb{P}(x)=\frac{1}{\sqrt{2\pi\det\Sigma}}\exp\left(-\frac{1}{2}(x-\mu)^{\mathsf{T}}\Sigma^{-1}(x-\mu)\right).

The variances are specifically chosen so that hh is analytic by taking

σ(k)=Ce−r∥k∥.\sigma(k)=C e^{-r\lVert k\rVert}.

where C,r>0C,r>0 are hyperparameters (another choice could be σ(k)=C∥k∥−N\sigma(k)=C\lVert k\rVert^{-N} for CNC^N tori, but the analytic case appears to be typical for smooth dynamical systems). To find these parameters, consider the idealized case that HH consist of a sorted list of the exact expected norms Hk2=E[∥hk∥2]=Dσ(k)2H_k^2=\mathbb{E}[\lVert h_k\rVert^2]=D\sigma(k)^2. In such a case, the list is sorted according to increasing wavenumbers in the lattice, which is asymptotically given by ∥π(j)∥∼((j−1)/Vd)1/d\lVert\pi(j)\rVert\sim((j-1)/V_d)^{1/d} where VdV_d is the unit volume of a sphere in dd dimensions. Using this assumption, we heuristically fit a line to the log-norm of the coefficients HH

min⁡C,r∑j=1JC,r∣log⁡∥H∥j2−log⁡(Dσ(((j−1)/Vd)1/d)2)∣2(20)\min_{C,r}\sum_{j=1}^{J_{C,r}}\left|\log\lVert H\rVert_j^2-\log\left(D\sigma\left(((j-1)/V_d)^{1/d}\right)^2\right)\right|^2 \tag*{(20)}

When this problem is expanded, it becomes a simple linear regression for log⁡C\log C and rr, so the hyperparameters can be quickly obtained from data. We choose the number of points JC,rJ_{C,r} to be approximately a third of the total number of available values from the output of the extrapolation step.

Because the observed coefficients are observed in sorted norm, we will use the distribution of the squared magnitude of the coefficients ∥hπ(j)∥2∼χ2(σ(π(j))2,D)\lVert h_{\pi(j)}\rVert^2\sim\chi^2(\sigma(\pi(j))^2,D) with the probability density function

P(∥hk∥2=x2)=1(2σ(k)2)D/2Γ(D/2)xD−2exp⁡(−x22σ(k)2).(21)\mathbb{P}(\lVert h_k\rVert^2=x^2)=\frac{1}{(2\sigma(k)^2)^{D/2}\Gamma(D/2)}x^{D-2}\exp\left(-\frac{x^2}{2\sigma(k)^2}\right). \tag*{(21)}

We assume that this probability is independent of the rotation vector, i.e. P(∥hk∥2∣ω)=P(∥hk∥2)\mathbb{P}(\lVert h_k\rVert^2\mid\omega)=\mathbb{P}(\lVert h_k\rVert^2).

The extrapolation step does not return wavenumbers, so we cannot directly use the probability (21) in our optimization. So, to link these probabilities with the observed data HH, we assume that extrapolation step returns an order statistic π:[J0]→Zd\pi:[J_0]\to\mathbb{Z}^d on the magnitudes Hj2=∥hπ(j)∥2H_j^2=\lVert h_{\pi(j)}\rVert^2 with no measurement error. An order statistic is defined by the requirement that the magnitudes are sorted as H12≥H22≥⋯≥HJ02H_1^2\ge H_2^2\ge\cdots\ge H_{J_0}^2 and ∥hk∥2≤HJ02\lVert h_k\rVert^2\le H_{J_0}^2 for all unobserved k∉π([J0])k\notin\pi([J_0]). We note that order statistics on non-identically independently distributed random variables are expensive to compute, requiring the factorial cost of computing permanents [39]. However, we will find that we only require the joint probabilities P(H,π)\mathbb{P}(\boldsymbol{H},\boldsymbol{\pi}), allowing us to avoid this particular computational complexity.

In particular, the joint probability of observing (H,π)(\boldsymbol{H},\boldsymbol{\pi}) is

P(H,π)=Δπ(∏j=1J0P(Hπ(j)2=Hj2))(∏k∈Zd∖(π([J0])∪{0})P(Hk2≤HJ02)),(22)\mathbb{P}(\boldsymbol{H},\boldsymbol{\pi}) = \Delta_{\boldsymbol{\pi}} \left(\prod_{j=1}^{J_0} \mathbb{P}(H_{\pi(j)}^2 = H_j^2)\right) \left(\prod_{k \in\mathbb{Z}^d \setminus(\boldsymbol{\pi}([J_0]) \cup\{0\})} \mathbb{P}(H_k^2 \le H_{J_0}^2)\right), \tag*{(22)}
∝Δπ∏j=1J0P(Hπ(j)2=Hj2)P(Hπ(j)2≤HJ02),(23)\propto\Delta_{\boldsymbol{\pi}} \prod_{j=1}^{J_0} \frac{\mathbb{P}(H_{\pi(j)}^2 = H_j^2)}{\mathbb{P}(H_{\pi(j)}^2 \le H_{J_0}^2)}, \tag*{(23)}

where

Δπ={1,π(j)≠π(j′)for all 1≤j<j′≤J0,0,else.\Delta_{\boldsymbol{\pi}} = \begin{cases} 1, & \pi(j) \ne\pi(j') \quad\text{for all } 1 \le j < j' \le J_0,\\ 0, & \text{else}. \end{cases}

In words, the formula for the joint probability (22) is the probability that each individual entry of Hj∈HH_j \in\boldsymbol{H} is observed according to the distribution defined by π(j)\pi(j), multiplied against the probability that every other Fourier coefficient has a magnitude less than the final entry of HJ0H_{J_0}. The function Δπ\Delta_{\boldsymbol{\pi}} disallows repeated draws of the same wavenumber. We note that the proportionality constant in (23) only depends on the data, and not on π\boldsymbol{\pi}.

For the rotation vector, we assume a uniform prior on Td\mathbb{T}^d independent of the coefficients ω∼U(Td)\boldsymbol{\omega} \sim\mathcal{U}(\mathbb{T}^d), corresponding to a probability distribution function

P(ω)=1.(24)\mathbb{P}(\boldsymbol{\omega}) = 1. \tag*{(24)}

The measurements of frequencies Ωj\Omega_j are assumed to be sampled from a circular normal with mean ω⋅π(j)\boldsymbol{\omega} \cdot\boldsymbol{\pi}(j) and standard deviation σω\sigma_\omega

P(Ωj∣ω,π)=1Cexp⁡(sin⁡2((Ωj−ω⋅π(j))π)2π2σω2),\mathbb{P}(\Omega_j \mid\boldsymbol{\omega},\boldsymbol{\pi}) = \frac{1}{C} \exp\left(\frac{\sin^2((\Omega_j - \boldsymbol{\omega} \cdot\boldsymbol{\pi}(j))\pi)}{2\pi^2\sigma_\omega^2}\right),

where CC is a normalizing constant. In the limit as σω→0\sigma_\omega\to0, this distribution approaches

P(Ωj∣ω,π)=12πσω2exp⁡(−∣Ωj−ω⋅π(j)∣T22σω2),\mathbb{P}(\Omega_j \mid\boldsymbol{\omega},\boldsymbol{\pi}) = \frac{1}{\sqrt{2\pi\sigma_\omega^2}} \exp\left(-\frac{\lvert\Omega_j - \boldsymbol{\omega} \cdot\boldsymbol{\pi}(j)\rvert_{\mathbb{T}}^2}{2\sigma_\omega^2}\right),

which is what we use in practice. The hyperparameter σω\sigma_\omega is typically chosen to be very small (i.e. O(10−7)\mathcal{O}(10^{-7}) to O(10−11)\mathcal{O}(10^{-11})), and can be adjusted to the convergence of the extrapolation step. In particular, when the map is known to be numerically symplectic — either from an analytic form or a symplectic integrator — the tolerance can be chosen much smaller than if, e.g., the map is obtained via a Runge-Kutta method. We assume that the frequencies Ωj\Omega_j are independent of H\boldsymbol{H} and each other, so that

P(Ω∣ω,π)=P(Ω∣H,ω,π)=∏j=1J0P(Ωj∣ω,π(j))\mathbb{P}(\boldsymbol{\Omega} \mid\boldsymbol{\omega},\boldsymbol{\pi}) = \mathbb{P}(\boldsymbol{\Omega} \mid\boldsymbol{H},\boldsymbol{\omega},\boldsymbol{\pi}) = \prod_{j=1}^{J_0} \mathbb{P}(\Omega_j \mid\boldsymbol{\omega},\boldsymbol{\pi}(j))

Now that we have defined our priors, we return to the Bayesian MAP estimation problem

max⁡ω,πP(ω,π∣Ω,H),\max_{\boldsymbol{\omega},\boldsymbol{\pi}} \mathbb{P}(\boldsymbol{\omega},\boldsymbol{\pi} \mid\boldsymbol{\Omega},\boldsymbol{H}),

where we use the shorthand Ω=(Ω1,…,ΩJ0)\boldsymbol{\Omega} = (\Omega_1,\ldots,\Omega_{J_0}) and H=(H1,…,HJ0)\boldsymbol{H} = (H_1,\ldots,H_{J_0}) for the first J0J_0 frequency and coefficient measurements. Applying Bayes’ rule, we have

P(ω,π∣Ω,H)=P(ω)P(Ω,H)P(Ω,H,π∣ω),\mathbb{P}(\boldsymbol{\omega},\boldsymbol{\pi} \mid\boldsymbol{\Omega},\boldsymbol{H}) = \frac{\mathbb{P}(\boldsymbol{\omega})}{\mathbb{P}(\boldsymbol{\Omega},\boldsymbol{H})} \mathbb{P}(\boldsymbol{\Omega},\boldsymbol{H},\boldsymbol{\pi} \mid\boldsymbol{\omega}),
∝P(Ω,H,π∣ω),\propto\mathbb{P}(\boldsymbol{\Omega},\boldsymbol{H},\boldsymbol{\pi} \mid\boldsymbol{\omega}),

where we used Eq. (24) and the fact that the marginal probability P(Ω,H)\mathbb{P}(\Omega, H) is independent of the optimization variables to put it into the proportionality constant. Because we have assumed that Ω\Omega is independent of HH and that HH is independent of ω\omega, this reduces to

P(ω,π∣Ω,H)∝P(Ω∣ω,π)P(H,π),\mathbb{P}(\omega,\pi\mid\Omega,H) \propto\mathbb{P}(\Omega\mid\omega,\pi)\mathbb{P}(H,\pi),
∝Δπ∏j=1J0αj(Hj,π(j))P(Ωj∣ω,π(j)),αj(Hj,π(j))=P(Hπ(j)2=Hj2)P(Hπ(j)2≤HJ02).(25)\propto\Delta_{\pi}\prod_{j=1}^{J_0}\alpha_j(H_j,\pi(j))\mathbb{P}(\Omega_j \mid\omega,\pi(j)), \qquad\alpha_j(H_j,\pi(j))=\frac{\mathbb{P}(H_{\pi(j)}^2=H_j^2)}{\mathbb{P}(H_{\pi(j)}^2\le H_{J_0}^2)}. \tag*{(25)}

Eq. (25) is the desired outcome of a weighted probability of observing the frequencies Ω\Omega. The frequency probabilities penalize deviations between the candidate rotation vector and the observed frequencies, which is our primary objective. These probabilities are then weighted by the likelihood that the torus coefficient magnitude deviates too much from the analytic smooth-torus assumption. In the case that Δπ=1\Delta_{\pi}=1, the logarithm of the proportional value of the posterior

LMAP=∑j=1J0log⁡αj+log⁡P(Ωj∣ω,π(j))(26)L_{\mathrm{MAP}}=\sum_{j=1}^{J_0}\log\alpha_j+\log\mathbb{P}(\Omega_j \mid\omega,\pi(j)) \tag*{(26)}

can be used as an approximate measure of fit. However, this measure can be unreliable, as we have found that correct rotation vectors can sometimes have large negative values of LMAPL_{\mathrm{MAP}}.

Now, we consider the process of solving the MAP problem (13). Before we describe the method, first note that the problem is discrete in π\pi, indicating an optimization that is potentially very expensive. So, we will not perform a full global optimization

First, instead of optimizing over all possible values of ω\omega, we will restrict to values such that

ω=(Ωj1⋮Ωjd)⊂Ω.\omega=\begin{pmatrix}\Omega_{j_1}\\ \vdots\\ \Omega_{j_d}\end{pmatrix}\subset\Omega.

This assumes that there exists a valid rotation vector comprised of the frequencies that we have observed from the RRE process. From this, we have reduced the optimization problem to

min⁡ω⊂Ωmin⁡πP(ω,π∣Ω,H).\min_{\omega\subset\Omega}\min_{\pi}\mathbb{P}(\omega,\pi\mid\Omega,H).

Then, for the wavenumber mapping π\pi, we first restrict to finite number of wavenumbers in the finite infinity-norm grid

∥π(j)∥∞=max⁡ℓ∈[d]∣(π(j))ℓ∣≤P,1≤j≤J0,\lVert\pi(j)\rVert_{\infty}=\max_{\ell\in[d]}\lvert(\pi(j))_{\ell}\rvert\le P,\qquad1\le j\le J_0,

for some fixed value of P>0P>0. By default, we consider PP to scale as γ(J0)1/d\gamma(J_0)^{1/d}, where γ≈10\gamma\approx10. Then, on that grid, we greedily choose the values π(j)\pi(j) by minimizing

min⁡∥π(j)∥∞≤Pπ(j)∉{π(1),…,π(j−1)}αj(Hj,π(j))P(Ωj∣ω,π(j)).(27)\min_{\substack{\lVert\pi(j)\rVert_{\infty}\le P\\ \pi(j)\notin\{\pi(1),\ldots,\pi(j-1)\}}}\alpha_j(H_j,\pi(j))\mathbb{P}(\Omega_j \mid\omega,\pi(j)). \tag*{(27)}

Note that by excluding the previous wavenumber draws in the minimization, we automatically ensure that Δπ=1\Delta_{\pi}=1. If the result would not change if we allowed for repeated draws, the greedy optimization gives the true optimal posterior conditioned with fixed rotation vector on the allowed grid.

The primary computational cost of the MAP step is in the optimization (27). A direct implementation requires searching over (2P+1)d(2P+1)^d potential matches for all 1≤j≤J01\le j\le J_0, resulting in a total cost that scales as O(J0Pd)O(J_0P^d). To accelerate the optimization, we first sort the allowed wavenumbers A={k∣∥k∥∞≤P}A=\{\boldsymbol{k}\mid\lVert\boldsymbol{k}\rVert_{\infty}\le P\} by the frequencies ω⋅k\omega\cdot\boldsymbol{k}. Because the probability P(Ωj∣ω,π(j))\mathbb{P}(\Omega_j\mid\omega,\pi(j)) is sharply localized about the frequency Ωj\Omega_j, we only have to search for π(j)\pi(j) in the sorted list over a small fixed number of frequencies about Ω\Omega in AA (approximately 5 in each direction). This reduces the cost of computing wavenumbers for fixed ω\omega to O(Pdlog⁡P)O(P^d\log P), the time to sort the list. Iterating over all allowed rotation vectors within Ω\Omega, the total cost is then O((J0)dPdlog⁡P)O((J_0)^dP^d\log P), which scales as O((J0)d+1log⁡J0)O((J_0)^{d+1}\log J_0) when P∝(J0)1/dP\propto(J_0)^{1/d}. We note that there are cases where PP scaling as J0J_0 is inappropriate — e.g. for very thin tori where most of the motion is occurring in a single dimension. In such cases one might consider taking PP larger, or perhaps choosing an anisotropic grid to search over wavenumbers.

Refining the rotation vector

If the MAP estimation succeeded, the output from Sec. 3.2 will be a valid rotation vector. However, while this rotation vector is valid, we have not necessarily addressed the issue of whether the found rotation vector is the best one for Fourier approximation.

To determine a precise notion of “best rotation vector,” we consider a geometric approach. As discussed in 2.3, when we transform our rotation vector, we equivalently transform the homology generators of the torus, meaning we need some metric of what the best homology generators are. To do so, consider S:Td→RDS : \mathbb{T}^{d} \to\mathbb{R}^{D} to be the invariant torus in Euclidean space for a given rotation vector. A loop around the torus SS in the θ1\theta_{1} direction is parameterized by fixing θm\theta_{m} for 1<m≤d1 < m \le d and varying 0≤θ1<10 \le\theta_{1} < 1. Then, the length of that loop is given by

L1(θ2,…,θd)=∫T(∂(h∘S)∂θ1)T(∂(h∘S)∂θ1) dθ1.L_{1}(\theta_{2},\ldots,\theta_{d}) = \int_{\mathbb{T}} \left(\frac{\partial(h \circ S)}{\partial\theta_{1}}\right)^{T}\left(\frac{\partial(h \circ S)}{\partial\theta_{1}}\right)\,\mathrm{d}\theta_{1}.

Our goal is to find the direction θ1\theta_{1} with a shortest average loop that maintains the action-angle conjugacy in the L2L^{2} sense, which is defined for a fixed torus as

L‾1=∫Td(∂(h∘S)∂θ1)T(∂(h∘S)∂θ1) dθ,=e1T[∫Td(∂(h∘S)∂θ)T(∂(h∘S)∂θ) dθ]e1,=e1TGe1.\begin{aligned} \overline{L}_{1} = \int_{\mathbb{T}^{d}} \left(\frac{\partial(h \circ S)}{\partial\theta_{1}}\right)^{T}\left(\frac{\partial(h \circ S)}{\partial\theta_{1}}\right)\,\mathrm{d}\theta, \\ &= e_{1}^{T}\left[\int_{\mathbb{T}^{d}} \left(\frac{\partial(h \circ S)}{\partial\theta}\right)^{T}\left(\frac{\partial(h \circ S)}{\partial\theta}\right)\,\mathrm{d}\theta\right]e_{1}, \\ &= e_{1}^{T}G e_{1}. \end{aligned}

The matrix GG can be interpreted as the averaged metric of the observable embedding of the invariant torus in Rd\mathbb{R}^{d}.

When we consider a transformation of the invariant torus with θ′=Aθ\theta^{\prime} = A\theta for A∈GL(d,Z)A \in GL(d,\mathbb{Z}), the metric changes as

G′=∫Td(∂θ∂θ′)T(∂(h∘S)∂θ)T∂(h∘S)∂θ∂θ∂θ′ dθ,=A−TGA−1.\begin{aligned} G^{\prime} = \int_{\mathbb{T}^{d}} \left(\frac{\partial\theta}{\partial\theta^{\prime}}\right)^{T}\left(\frac{\partial(h \circ S)}{\partial\theta}\right)^{T}\frac{\partial(h \circ S)}{\partial\theta}\frac{\partial\theta}{\partial\theta^{\prime}}\,\mathrm{d}\theta, \\ &= A^{-T}GA^{-1}. \end{aligned}

A shortest average loop direction around the torus is then defined by the optimization

L‾1⋆=min⁡A∈GL(d,Z)e1T(A−TGA−1)e1.\overline{L}_{1}^{\star} = \min_{A\in GL(d,\mathbb{Z})} e_{1}^{T}\left(A^{-T}GA^{-1}\right)e_{1}.

(Note that this minimization does not have a unique minimizer even in the 1D case, as A→−AA \to-A produces the same solution.) Let BB be any matrix square root of the average metric G=BTBG = B^{T}B (e.g. the Cholesky decomposition). We can rewrite the optimization problem as

L‾1⋆=min⁡A∈GL(d,Z)∥BA−1e1∥2.\overline{L}_{1}^{\star} = \min_{A\in GL(d,\mathbb{Z})} \left\lVert BA^{-1}e_{1}\right\rVert^{2}.

When written this way, it becomes apparent that a shortest average loop is equivalent to the Shortest Vector Problem (SVP), which is a well known problem in lattice cryptography [40]. This problem is NP-hard for randomized reductions in the dimension dd [41], meaning the fastest algorithms for computing L‾1⋆\overline{L}_{1}^{\star} are believed to be very expensive as dd grows. In the case of large dimension, a well known approximation algorithm for SVP is the Lenstra-Lenstra-Lovász (LLL) algorithm [42]. However, in the case of the invariant tori we consider, dd is typically very small, meaning the exact problem can be solved quickly.

The shortest vector can always be used as the first column of the transformed matrix B′B^{\prime}. From here, however, there are multiple ways this can generalize to higher dimensions. For this purpose, we choose the Korkine-Zolotarev (KZ) basis [40], which is defined so that the transformed BB has short and nearly orthogonal columns.

To define the KZ basis, let bnb_n be the nnth column of BB. The orthogonal lattice Gram-Schmidt basis is defined by

b^n=bn−∑m=1n−1μmnb^m,μmn=bn⋅b^m∣b^m∣2.\hat{b}_n=b_n-\sum_{m=1}^{n-1}\mu_{mn}\hat{b}_m,\qquad\mu_{mn}=\frac{b_n\cdot\hat{b}_m}{\lvert\hat{b}_m\rvert^2}.

Then, we define the nnth projected lattice Λn\Lambda_n as the set of points

Λn={x∣x=Pn(Bk), k∈Zd},Pn(x)=x−∑m=1n−1x⋅b^m∣b^m∣2b^m.\Lambda_n=\{x\mid x=P_n(B\mathbf{k}),\ \mathbf{k}\in\mathbb{Z}^d\},\qquad P_n(x)=x-\sum_{m=1}^{n-1}\frac{x\cdot\hat{b}_m}{\lvert\hat{b}_m\rvert^2}\hat{b}_m.

Note that Λ1\Lambda_1 is just the original lattice defined by BB. We define a basis BB as KZ reduced if

  • b^n\hat{b}_n is a shortest vector in Λn\Lambda_n, and

  • for all n>mn>m, ∣μmn∣≤1/2\lvert\mu_{mn}\rvert\leq1/2.

In the definition of a KZ basis, the two requirements correspond directly to notions of shortness and orthogonality. The first requirement exactly coincides with b^1\hat{b}_1 being a minimizer of the SVP for the shortest average loop. The following columns are minimizers of SVPs on toroidal coordinates that are orthogonal to the previously computed directions. The second requirement can be recognized as the cosine of the angle between two vectors, implying that the angles between any two basis vectors is greater than π/3\pi/3.

To appreciate the usefulness of the orthogonality requirement to the parameterization, we note that in Fourier space on the torus, the averaged metric becomes

G=∑k∈Zd∥hk∥2kkT.(28)G=\sum_{\mathbf{k}\in\mathbb{Z}^d}\lVert h_{\mathbf{k}}\rVert^2\mathbf{k}\mathbf{k}^{T}. \tag*{(28)}

In this way, GG can be thought of as the second moment of the distribution of Fourier coefficients (because ∥hk∥=∥h−k∥\lVert h_{\mathbf{k}}\rVert=\lVert h_{-\mathbf{k}}\rVert, the first moment must always be zero). So, the requirement of small angles in the basis is equivalent to the requirement that a Gaussian approximation of the Fourier spectrum is well aligned with the coordinate axes: i.e. we select the left hand side of Figure 3.

The equation (28) also gives a method to compute the matrix GG. To estimate this, we use the Fourier labeling π\pi determined in the previous section (possibly for different values of J0J_0 and PP, as this must only be computed once). Using that mapping, we can approximate GG as

G≈∑j=1J0Hj2π(j)π(j)T.G\approx\sum_{j=1}^{J_0}H_j^2\pi(j)\pi(j)^T.

From here, we use an implementation of a KZ reduction algorithm [43] by the LLLplus.jl package. Once we find a KZ reduced basis, we post-process to restrict the non-uniqueness of the solution. In particular, if ω′=Aω\omega'=A\omega is the transformed rotation vector, our final step is to multiply transform AA to ADiag⁡(sgn⁡(ω′))A\operatorname{Diag}(\operatorname{sgn}(\omega')), where the sign function sgn⁡:T→Z\operatorname{sgn}:\mathbb{T}\to\mathbb{Z} is defined by

sgn⁡(ω)={1,0≤ω≤1/2,−1,else.\operatorname{sgn}(\omega)= \begin{cases} 1, & 0\leq\omega\leq1/2,\\ -1, & \text{else}. \end{cases}

The result is that the final rotation vector ω′\omega' is chosen to have entries in [0.0,0.5][0.0,0.5] mod 1.

Algorithm adjustments for islands

While invariant tori are the typical integrable structure of symplectic maps, it is possible that trajectories lie on a periodic sequence of tori that we refer to as an island chain. We define the period of an island chain including xx as the minimal value p∈Z+p\in\mathbb{Z}^+ such that xx is on an invariant torus of FpF^p (in this way, an invariant torus is an island chain with period 1). Then, we define an island chain with period pp as a sequence of tori S(j):Td→MS^{(j)}:\mathbb{T}^d\to\mathcal{M} for 1≤j≤p1\leq j\leq p with rotation vector ω\omega that satisfies

F∘S(j)={S(j+1),1≤j<p,S(1)∘τω,j=p.F\circ S^{(j)}= \begin{cases} S^{(j+1)}, & 1\leq j<p,\\ S^{(1)}\circ\tau_\omega, & j=p. \end{cases}

When transformed to the frequency domain, the signal h∘Fth \circ F^t has the form

h∘Ft(x)=∑j=0p−1∑k∈Zdhjkλjkt,λjk=e2πi(j+ω⋅k)/p.h \circ F^t(x) = \sum_{j=0}^{p-1} \sum_{k \in\mathbb{Z}^d} h_{jk}\lambda_{jk}^t,\qquad\lambda_{jk} = e^{2\pi i(j+\omega\cdot k)/p}.

So, from the perspective of the signal, an island chain can be equivalently be thought of as a dimension d+1d+1 invariant torus with a resonant rotation vector ωisl=(1/p,ω/p)\omega_{\mathrm{isl}} = (1/p,\omega/p). We can use this insight to easily generalize the algorithm above.

To find pp, we use the same method as [30]. Let ϵisl>0\epsilon_{\mathrm{isl}} > 0 be a tolerance and pmax⁡p_{\max} be the maximum value of pp. Then, we identify a trajectory as having a period pp if there is any element of the frequency vector Ωj∈Ω\Omega_j \in\Omega which satisfies

∣Ωj−np∣T<ϵisl,n,p∈Z,1≤p≤pmax⁡.\left|\Omega_j - \frac{n}{p}\right|_{\mathbb{T}} < \epsilon_{\mathrm{isl}}, \qquad n,p \in\mathbb{Z}, \qquad1 \leq p \leq p_{\max}.

Typical values of these constants are pmax⁡=10p_{\max}=10 and ϵada=10−8\epsilon_{\mathrm{ada}}=10^{-8}.

If the torus is recognized as an island, the MAP estimation is essentially the same, except we would like to learn π:[J0]→[p]×Zd\boldsymbol{\pi} : [J_0] \to[p] \times\mathbb{Z}^d, where the first element corresponds to the discrete frequency associated with the rational frequency 1/p1/p. For the prior on hjkh_{jk}, we use

Re⁡hjk,Im⁡hjk∼N(0,σ(k)22I).\operatorname{Re} h_{jk},\operatorname{Im} h_{jk} \sim\mathcal{N}\left(0,\frac{\sigma(k)^2}{2}I\right).

i.e. the frequency jj is not included the prior. Because the period pp is determined before the MAP estimation, it is treated as a known quantity. This means that the prior for ω\omega is not changed.

Finally, for rotation vector refinement, we perform KZ reduction on the averaged metric

Gmn=∑j=1p∫Td∂(h∘S(j))∂θm⋅∂(h∘S(j))∂θn dθ.G_{mn} = \sum_{j=1}^{p} \int_{\mathbb{T}^d} \frac{\partial(h \circ S^{(j)})}{\partial\theta_m} \cdot\frac{\partial(h \circ S^{(j)})}{\partial\theta_n}\,\mathrm{d}\theta.

The diagonal components GmmG_{mm} can be interpreted as the sum-of-squares of the average loop length of each torus in the island chain. When transformed to Fourier space, we represent this matrix as

G=∑k∈Zd(∑j=1p∥hjk∥2)kkT.G = \sum_{k \in\mathbb{Z}^d} \left(\sum_{j=1}^{p} \lVert h_{jk}\rVert^2\right) kk^{T}.

This can be approximated using π\boldsymbol{\pi} from the previous step.

Finally, for the parameterization algorithm in Sec. 2.2, we can find parameterizations for each island in the island chain by working directly with the extended frequency ωisl\omega_{\mathrm{isl}}. The only adjustment beyond this is that refinement in the rational direction never needs to be adjusted. That is, we optimize over a resolution Kisl=(p,K)\boldsymbol{K}_{\mathrm{isl}}=(p,\boldsymbol{K}), where only K\boldsymbol{K} is incremented.

Examples

Now that the method has been introduced, we would like to see how it performs under more extensive testing. We do this in two settings. In the first example (the coupled standard map, § 4.1), we analyze the method’s robustness. We do so by attempting to compute invariant tori for 1000 randomly initialized trajectories and measuring the accuracy of the solutions. To make the test rigorous, accuracy is computed by an a posteriori test of a KAM-like residual, rather than any of the residuals used to compute the torus. In the second example (the cislunar ER3BP, § 4.2), we show that the method generalizes to 3D tori in the out-of-plane ER3BP. The implementation of the algorithm used to perform these examples can be found in the SymplecticMapTools.jl Julia package [34]. All reported timings were performed on an Apple M2 CPU.

The coupled standard map

We return to the standard map (11) with

Ksm=(0.10.050.050.05),K_{\mathrm{sm}} = \begin{pmatrix} 0.1 & 0.05 \\ 0.05 & 0.05 \end{pmatrix},

where we use the same observable (12). The forcing matrix KsmK_{\mathrm{sm}} was chosen to be weak so that there are many invariant tori within the coupled standard map equation. The strong off-diagonal component was chosen to be relatively strong, so that there is significant coupling between the variables. The initial conditions are chosen uniformly at random on the hypercube (x0,y0)∈T2×[0,1]2(\boldsymbol{x}_0,\boldsymbol{y}_0) \in\mathbb{T}^2 \times[0,1]^2.

To compute the tori, we use the parameters below (where we recall their basic uses)

  • (J,T)∈{(1000,2000),(1500,3000),(2000,4000)}(J,T) \in\{(1000,2000),(1500,3000),(2000,4000)\} (except for Figure 6): The dimensions of the Birkhoff RRE least-squares problem. We choose the smallest value of these parameters where RRRE<5×10−14R_{\mathrm{RRE}} < 5 \times10^{-14} (or, if it is satisfied nowhere, (J,T)=(2000,4000)(J,T) = (2000,4000)). The corresponding trajectory length is N=T+2J+1∈{4001,6001,8001}N = T + 2J + 1 \in\{4001,6001,8001\}.

  • J0=30J_0 = 30: The number of frequencies used for finding the rotation vector.

  • σω=10−10\sigma_{\omega} = 10^{-10}: Prior standard deviation of the frequency measurements Ω\boldsymbol{\Omega}.

  • Kmax⁡=2000K_{\max} = 2000: Maximum number of Fourier modes used to parameterize the torus.

  • pmax⁡=10p_{\max} = 10, ϵisl=10−8\epsilon_{\mathrm{isl}} = 10^{-8}: Island identification parameters.

Residuals as a function of trajectory length for the coupled standard map

Figure 6. (Left) The Birkhoff RRE residual (17) as a function of trajectory length NN for the coupled standard map. The classification tolerance of 1×10−121 \times10^{-12} is plotted in magenta. (Right) The Weighted Birkhoff Average residual as a function of trajectory length. The NN scaling is broken so that the left half agrees with the Birkhoff RRE horizontal axis and the right half shows the residual for values of NN up to 2×1052 \times10^{5}.

As a general rule, as JJ, TT, J∗J^*, and Kmax⁡K_{\max} are the most important parameters to adjust, allowing for more accurate computation at increased computational cost. These increases are most important for tori with nearly resonant rotation vectors, high anisotropy, or a wide Fourier spectrum. For smooth tori with good Diophantine constants, increases of these parameters are not important. The parameters above give a reasonable balance between speed and accuracy, where the most expensive tori take approximately a 60 seconds to compute.

There are five quantities that we use to analyze the performance of the algorithm

  • RRRER_{\mathrm{RRE}}: The least-squares residual of the Birkhoff RRE procedure (17). This is an indicator of integrability and a measure of the accuracy of the frequencies Ω\boldsymbol{\Omega}.

  • LMAPL_{\mathrm{MAP}}: A quantity proportional to the log posterior of the rotation vector MAP problem (26). This is a measure of confidence in the rotation vector.

  • RhR_h: The invariant torus validation error (9). This is a (rough) measure of the error of the torus parameterization.

  • RKAMR_{\mathrm{KAM}}: To validate our results, we use an a posteriori residual based on the KAM residual

RKAM=∥h∘F∘S−h∘S∘τω∥L2∥h∘S∥L2,∥f∥L22=∫Td∥f(θ)∥2 dθ,(29)R_{\mathrm{KAM}} = \frac{\lVert h \circ F \circ S - h \circ S \circ\tau_{\omega} \rVert_{L^2}}{\lVert h \circ S \rVert_{L^2}}, \qquad\lVert f \rVert_{L^2}^2 = \int_{\mathbb{T}^d} \lVert f(\theta) \rVert^2 \,\mathrm{d}\theta, \tag*{(29)}

where the L2L^2 norm is discretized by a 25×2525 \times25 trapezoidal quadrature rule. Like RhR_h, this is a measure of the error of the torus parameterization. However, unlike RhR_h, the torus is sampled uniformly rather than along a trajectory.

  • MδM_{\delta}: The resonance order of the rotation vector ω\boldsymbol{\omega} [44]. For a given tolerance δ>0\delta> 0, the resonance order of a rotation vector ω\boldsymbol{\omega} is defined by

Mδ(ω)=min⁡k∈Δ(ω,δ)∥k∥1,Δ(ω,δ)={k∣∣ω⋅k∣T≤δ}M_{\delta}(\boldsymbol{\omega}) = \min_{\boldsymbol{k} \in\Delta(\boldsymbol{\omega},\delta)} \lVert\boldsymbol{k} \rVert_1, \qquad\Delta(\boldsymbol{\omega},\delta) = \{\boldsymbol{k} \mid\lvert\boldsymbol{\omega} \cdot\boldsymbol{k} \rvert_{\mathbb{T}} \le\delta\}

That is, it is a measure of the lowest wavenumber such that the rotation vector is nearly resonant. So, one might expect a small MδM_{\delta} would generally correspond to a poorly approximated invariant torus. We use the value of δ=10−4\delta= 10^{-4}.

Choosing the Trajectory Length For the first test, we investigate the required trajectory length for Birkhoff RRE Convergence. To do this, we scan the filter length JJ from 4 to 2500, choose T=2JT = 2J, and compute RRRER_{\mathrm{RRE}} for each value of JJ chosen. The results are shown in Figure 6 (a), where we find that most trajectories have a residual that falls below 10−1210^{-12} by N=8001N = 8001 (J=2000J = 2000). This cutoff — plotted as a magenta line — is the residual by which we determine a trajectory as integrable. By this test, we classify 851 of the 1000 trajectories as integrable with a length N=8001N = 8001 trajectory.

We can compare this to a relative weighted Birkhoff average residual related to the one defined in [25]. Let NN be an even trajectory length. Then, the residual is defined by

RWBA=∥WBN/2[h](FN/2(x))−WBN/2[h](x)∥∥WBN/2[h](x)∥.R_{\mathrm{WBA}} = \frac{\left\lVert\mathcal{WB}_{N/2}[h](F^{N/2}(x)) - \mathcal{WB}_{N/2}[h](x) \right\rVert}{\left\lVert\mathcal{WB}_{N/2}[h](x) \right\rVert}.

A plot of this residual as a function of NN is shown in Figure 6 (b). The left side of this panel shows the decay of RWBAR_{\mathrm{WBA}} over the same trajectory lengths as RRRER_{\mathrm{RRE}}. We see that for the same trajectory length, weighted Birkhoff averaging gives a visually worse classification than Birkhoff RRE. In the right side of Figure 6 (b), we continue the residual RWBAR_{\mathrm{WBA}} in blue lines for trajectory lengths up to N=2×105N = 2 \times10^{5}. The weighted Birkhoff classification rate approximately matches the Birkhoff RRE classification rate in the right panel, indicating that weighted Birkhoff averaging requires approximately an order of magnitude longer trajectories for classification. This observation helps explain why the parameterization coefficients in § 2 are poorly obtained by weighted Birkhoff averages alone.

In some cases, it may still be preferable to work with weighted Birkhoff averages over Birkhoff RRE for trajectory classification. Because the cost of a weighted Birkhoff averages is linear in the trajectory length, the residual can be computed much more quickly than Birkhoff RRE. This is balanced against the fact that computing the trajectory can be more expensive than performing the RRE least-squares problem (for the J=2000J = 2000 case, the Birkhoff RRE least-squares problem takes approximately 15 seconds).

Invariant Torus Residuals For the 851 trajectories that are classified as tori by the J=2000J = 2000 case, we apply the methods within § 3.2, § 3.3, and § 2.2 to compute the rotation vector and parameterization. From this process, we obtain the values of LMAPL_{\mathrm{MAP}} and RhR_h for each trajectory, and we compute the value of RKAMR_{\mathrm{KAM}} as described.

In Figure 7 (a) and (b), we report distributions of RhR_h and RKAMR_{\mathrm{KAM}} for the trajectories considered. By both metrics, we find that we have accurately computed parameterizations of most of the trajectories; only six

Figure 7. Distribution of the output quantities (a) RhR_h, (b) RKAMR_{\mathrm{KAM}}, and (c) LMAPL_{\mathrm{MAP}} for the 851 classified trajectories. (d) The validation residual RhR_h vs the KAM residual RKAMR_{\mathrm{KAM}}. For LMAP>0L_{\mathrm{MAP}} > 0, the points are colored according to the value of LMAPL_{\mathrm{MAP}}. For LMAP<0L_{\mathrm{MAP}} < 0, all but two points are plotted as red ‘x’s. The final two are plotted as red stars, indicating the corresponding two the two difficult to approximate trajectories plotted in Figure 8.

trajectories have RKAM≥10−3R_{\mathrm{KAM}} \ge10^{-3}. We plot RKAMR_{\mathrm{KAM}} against RhR_h in Figure 7 (d), and find that there is a strong correlation between the two metrics, indicating that the validation error RhR_h can be used as a proxy for the true torus residual in the typical case (two exceptions are plotted as red stars, see the discussion of Figure 8 below).

Four-panel plots of invariant tori, parameterization error, and rotation vectors

Figure 8. (a-b) Two examples of poorly approximated invariant tori projected onto the (h1+h2,h3+h4)(h_1 + h_2, h_3 + h_4) plane, where the length N=8001N = 8001 trajectories are in red and the computed invariant tori are in gray. (c) A scatter plot of the parameterization error “surprise” RKAM/RhR_{\mathrm{KAM}}/R_h against the resonance order MδM_\delta for each trajectory. (d) A scatter plot of the computed rotation vectors ω\boldsymbol{\omega} over the resonance lines θ⋅k=0 mod 1\boldsymbol{\theta} \cdot\boldsymbol{k} = 0 \bmod1 for ∥k∥≤6\lVert\boldsymbol{k}\rVert\le6, colored by the logarithm of the KAM residual.

The distribution of LMAPL_{\mathrm{MAP}} is given in Figure 7 (c). We see that most trajectories have LMAP>0L_{\mathrm{MAP}} > 0, while there are a few values the negative tail. A rough interpretation of this is that, for most trajectories, the assumed Bayesian model well explains the observed data. We note, however, the connection between this observation and the more fundamental question of whether we determined the correct rotation vector is more complicated. Typically, the rotation vector is still correct even when LMAPL_{\mathrm{MAP}} is negative. One main reason for this is that islands tend to have negative values of LMAPL_{\mathrm{MAP}}. In this case, the posterior could likely be improved by directly working with the map FpF^p, where pp is the period of the island, as this reduces the problem to the invariant torus case. A second reason is that anisotropic tori can have values of kk that are not explained by the value of PP chosen in § 3.2. Of course, this can be improved by choosing PP larger. The final reason is that very smooth tori actually have smaller values of LMAPL_{\mathrm{MAP}} in general.

To expand on this final reason, we turn back to Figure 7 (d). The points where LMAP>0L_{\mathrm{MAP}} > 0 are colored according to their values, while values of LMAP<0L_{\mathrm{MAP}} < 0 are plotted in red. Perhaps against intuition, we find that LMAPL_{\mathrm{MAP}} decreases as the torus parameterization becomes more accurate. The reason is that the more accurately parameterized tori tend to be the smoother ones, and the error in the Birkhoff RRE frequency computation decreases as Fourier modes become more prominent. For an extreme example of why this might happen, consider a 1D torus of the form h∘S(θ)=(cos⁡θ,sin⁡θ)\boldsymbol{h} \circ S(\theta) = (\cos\theta, \sin\theta). Because only the k=1k = 1 wavenumber appears in the signal, one can show that a correctly chosen J=1J = 1 filter gives a residual RRRE=0R_{\mathrm{RRE}} = 0, regardless of the rotation number. When JJ increases beyond this, nothing remains in the signal that could reveal the rest of the frequencies, so the rest of Ω\boldsymbol{\Omega} would be random. This means that there is more uncertainty in Ω\boldsymbol{\Omega} for invariant tori that are well described by few Fourier modes, leading to lower values of LMAPL_{\mathrm{MAP}}. Hence, we find that RhR_h and RKAMR_{\mathrm{KAM}} are much more useful than LMAPL_{\mathrm{MAP}} to assess the quality of the final torus.

Poorly Approximated Tori and Small Denominators We have observed that RhR_h tends to be a good proxy for RKAMR_{\mathrm{KAM}}, but there were two outlier invariant tori (in red stars in Figure 7 (d)). This is difficult to reconcile, as small RhR_h indicates the torus is predictive of the trajectory, but clearly RKAMR_{\mathrm{KAM}} is a more honest measure of the torus. To investigate the mode of failure for the outliers, in Figure 8 (a-b) we plot projections of the trajectories in red and the computed invariant tori in black. We observe that there are two primary ways in which RKAMR_{\mathrm{KAM}} loses accuracy. For the example Figure 8 (a), the loss of accuracy is due to a nearly resonant rotation vector of ω=[0.39219678,0.23531362]\boldsymbol{\omega} = [0.39219678, 0.23531362], as ω⋅[3,−5]=2.225×10−5 mod 1\boldsymbol{\omega} \cdot[3,-5] = 2.225 \times10^{-5} \bmod1. The qualitative effect is that the trajectory is slow to explore the surface of the torus, leading to a high condition number for the least-squares parameterization. For the example in Figure 8 (b), the loss of accuracy is due to a misidentification of the rotation vector as a consequence of the extreme anisotropy of the torus. The computed rotation vector is ω=[0.04995223,0.48501443]\boldsymbol{\omega} = [0.04995223, 0.48501443] has a near resonance at ω⋅[3,10]=1.015×10−6 mod 1\boldsymbol{\omega} \cdot[3,10] = 1.015 \times10^{-6} \bmod1, which may indicate that only rotation in the “long” direction is being accounted for. Visually, the trajectory appears as almost periodic.

In both cases, the trajectories could be better approximated by increasing the resolution in the relevant parameters. For nearly resonant rotation vectors, simply using a longer trajectory for interpolation is sufficient. For a quicker computation, this trajectory could be subsampled (i.e. use the map FnF^n for some integer n>1n > 1), as that trajectory would more uniformly explore the torus without increasing the cost of downstream computations. For highly anisotropic tori, one can increase JJ, TT, and J0J_0. The use of larger J0J_0 gives the algorithm the opportunity to find two rotation vectors that form a valid basis, so that the trajectory can be correctly interpolated. We note that the higher frequencies are lower accuracy, however, and so there may be a limitation on the current algorithm without also increasing the floating point precision. As such, the higher anisotropy likely requires further algorithmic improvements for reliable practical computations.

To investigate the issue of near-resonance in a more systematic way, in Figure 8 (c), we plot the “surprise” RKAM/RhR_{\mathrm{KAM}}/R_h against the resonance order MδM_\delta. We find that small values of MδM_\delta are correlated with a mismatch between the validation residual and the KAM residual. Again, the intuition is likely due to nearly resonant rotation vectors corresponding to worse condition numbers for the parameterization. In Figure 8 (d), we plot the rotation vector ω\boldsymbol{\omega} of each torus, colored by log⁡10(RKAM)\log_{10}(R_{\mathrm{KAM}}). Behind the rotation vectors, we plot the resonance lines θ⋅k=0 mod 1\boldsymbol{\theta} \cdot\boldsymbol{k} = 0 \bmod1 for ∣k∣≤6\lvert\boldsymbol{k} \rvert\le6. We observe that torus appearing in Figure 8 (a) lies on the [5,3][5,3]

resonance line. More generally, we find that the KAM residual is typically better within the bulk, while the residual is worse near ω1=0\omega_1=0. This is likely due to the trend that anisotropic tori and island chains have small ω1\omega_1, due to them being near bifurcation points. Anisotropic tori are hard to approximate because the more complicated Fourier parameterization, while islands chains are complicated because the points per island is divided by the island period.

Islands We plot two successful parameterizations of island chains in Figure 9 for the coupled standard map. Figure 9 (a) is a period p=3p=3 island and (b) is a period p=2p=2 island. The island structure in (a) resembles a cut donut, while in (b) the islands are significantly more anisotropic.

Projections of two successfully computed island trajectories into the $(h_1+h_2,h_3+h_4)$ plane

Figure 9. Projections of two successfully computed island trajectories into the (h1+h2,h3+h4)(h_1+h_2,h_3+h_4) plane.

The Earth-Moon restricted three body problem

To test our method on 3D invariant tori, we consider the ER3BP with out-of-plane motion. The differential equations are the same as those presented in Eq. (1) but with the addition of a third out-of-plane coordinate ζ\zeta so that ξ=(ξ,η,ζ)\xi=(\xi,\eta,\zeta), p=(pξ,pη,pζ)\boldsymbol{p}=(p_\xi,p_\eta,p_\zeta). Accompanying modifications to the Hamiltonian are made accordingly [45]

H(ξ,p,f)=12(∥ξ∥2+∥p∥2)+ηpξ−ξpη−ϕ(ξ,f)ρ12=(ξ−μ)2+η2+ζ2,ρ22=(ξ−(μ−1))2+η2+ζ2.H(\boldsymbol{\xi},\boldsymbol{p},f)=\frac{1}{2}\left(\lVert\boldsymbol{\xi}\rVert^2+\lVert\boldsymbol{p}\rVert^2\right)+\eta p_\xi-\xi p_\eta-\phi(\boldsymbol{\xi},f) \qquad\rho_1^2=(\xi-\mu)^2+\eta^2+\zeta^2,\qquad\rho_2^2=(\xi-(\mu-1))^2+\eta^2+\zeta^2.

As before, the map FF is obtained by integrating the ODEs with the SRK3 integrator with 1000 symplectic time steps per lunar orbit. The observable hh is chosen to be the identity. We choose the parameters to match the earth-moon orbit with μ=1.2151×10−2\mu=1.2151\times10^{-2} and ϵ=0.0549\epsilon=0.0549. Because of the increased dimension,

the system now supports invariant tori with coupled out-of-plane motion. We initialize three tori at the locations

[ξL4,ξ˙L4]=[(0.488850.8680250.05),(−0.0020.0020.05)],[ξWLP,ξ˙WLP]=[(1.0425400.001),(00.431170.001)],[\boldsymbol{\xi}_{L_4},\dot{\boldsymbol{\xi}}_{L_4}] = \left[\begin{pmatrix}0.48885\\0.868025\\0.05\end{pmatrix},\begin{pmatrix}-0.002\\0.002\\0.05\end{pmatrix}\right],\quad[\boldsymbol{\xi}_{\mathrm{WLP}},\dot{\boldsymbol{\xi}}_{\mathrm{WLP}}] = \left[\begin{pmatrix}1.04254\\0\\0.001\end{pmatrix},\begin{pmatrix}0\\0.43117\\0.001\end{pmatrix}\right],
[ξDR,ξ˙DR]=[(0.955610.0010.001),(0.0010.640880.001)].[\boldsymbol{\xi}_{\mathrm{DR}},\dot{\boldsymbol{\xi}}_{\mathrm{DR}}] = \left[\begin{pmatrix}0.95561\\0.001\\0.001\end{pmatrix},\begin{pmatrix}0.001\\0.64088\\0.001\end{pmatrix}\right].

where ξ˙\dot{\boldsymbol{\xi}} is the pulsating rotating frame velocity related to the momenta by

p=ξ˙+(−η,ξ,0)T.\mathbf{p} = \dot{\boldsymbol{\xi}} + (-\eta,\xi,0)^{T}.

The out-of-plane initial data are perturbations on a L4L_4 librational orbit (similar to § 2), a western low prograde orbit, and a distant retrograde orbit [46, 47]. The initial points were chosen by perturbing orbits catalogued in the NASA JPL Solar System Group Horizons Three-Body Periodic Orbit tool [48].

To parameterize the algorithm, we use (cf. § 4.1)

  • L4L_4 librational: J=2500J = 2500, T=3334T = 3334, N=8335N = 8335, J0=20J_0 = 20,

  • Western low prograde: J=1000J = 1000, T=1334T = 1334, N=3335N = 3335, J0=18J_0 = 18,

  • Distant retrograde: J=1000J = 1000, T=1334T = 1334, N=3335N = 3335, J0=8J_0 = 8,

and otherwise we keep the same values as the previous section. The reported values of J0J_0 for western low prograde and distant retrograde were the minimum values such that HJ0>10−3H1H_{J_0} > 10^{-3}H_1, as described in § 3.2. The output quantities of interest are:

  • L4L_4 librational: ω=(0.04701,0.00018,0.30039)\boldsymbol{\omega} = (0.04701, 0.00018, 0.30039), K=(15,7,19)\mathbf{K} = (15, 7, 19), RRRE=6.28×10−11R_{\mathrm{RRE}} = 6.28 \times10^{-11}, LMAP=938L_{\mathrm{MAP}} = 938, Rh=1.44×10−6R_h = 1.44 \times10^{-6}, RKAM=3.63×10−6R_{\mathrm{KAM}} = 3.63 \times10^{-6},

  • Western low prograde: ω=(0.03310,0.47110,0.11892)\boldsymbol{\omega} = (0.03310, 0.47110, 0.11892), K=(7,11,25)\mathbf{K} = (7, 11, 25), RRRE=8.94×10−14R_{\mathrm{RRE}} = 8.94 \times10^{-14}, LMAP=838L_{\mathrm{MAP}} = 838, Rh=5.25×10−8R_h = 5.25 \times10^{-8}, RKAM=5.70×10−6R_{\mathrm{KAM}} = 5.70 \times10^{-6},

  • Distant retrograde: ω=(0.36620,0.16519,0.40482)\boldsymbol{\omega} = (0.36620, 0.16519, 0.40482), K=(7,13,21)\mathbf{K} = (7, 13, 21), RRRE=7.23×10−15R_{\mathrm{RRE}} = 7.23 \times10^{-15}, LMAP=382L_{\mathrm{MAP}} = 382, Rh=1.12×10−7R_h = 1.12 \times10^{-7}, RKAM=1.63×10−5R_{\mathrm{KAM}} = 1.63 \times10^{-5}.

The value of NN in the distant retrograde example was chosen to be larger than was necessary to classify the torus, as ω\boldsymbol{\omega} for appears to be nearly resonant for this trajectory (an issue that we expect becomes worse with dimension).

Each invariant torus is plotted in a row of Figure 10. The tori are visualized by plotting “slices” of the 3D torus, defined by fixing one of the coordinates θj\theta_j for θj=2πn/4\theta_j = 2\pi n/4 for 0≤n<70 \le n < 7. Each column of Figure 10, the slicing coordinate is changed. We see that the third column, slicing in θ3\theta_3, aligns with the intuitive notion of the ”long way” around the torus, as we might expect from the KZ reduced basis. However, this is only a rough intuition, as the loops are actually computed in the full six dimensional space. This is observed through the θ1\theta_1 and θ2\theta_2 directions, where the shortest way around the torus is more difficult to intuit.

Visualizations of three $d = 3$ invariant tori of the earth-moon ER3BP

Figure 10. Visualizations of three d=3d = 3 invariant tori of the earth-moon ER3BP. In each column, the three-dimensional torus is “sliced” in each of the three angular coordinates. For instance, in the first column, the tori slices (h∘S)(1,j)(θ2,θ3)=(h∘S)(πj/4,θ2,θ3)(h \circ S)^{(1,j)}(\theta_2,\theta_3) = (h \circ S)(\pi j/4,\theta_2,\theta_3) for 0≤j≤70 \leq j \leq7.

In Table 3, we show the wall clock time for each of the steps to compute the tori for each example. In each case, the time to compute the trajectory was the primary cost. Second to this, the Birkhoff RRE least-squares problem (computing cc) and eigenvalue problem (computing Ω\mathbf{\Omega} and HH) scale the worst with the trajectory length, as both use full dense linear algebra with dimensions proportional to the trajectory length. The parameterization least-squares problem also scales with trajectory length, but the fixed value of Kmax⁡K_{\max} improves the performance. Finally, because J0J_0 is uncoupled to the trajectory length, the Bayesian MAP problem can dominate the cost at low trajectory length, while being relatively cheap for long trajectories. In sum, each part of the algorithm can potentially be rate limiting, depending on the context.

OrbitNNTraj.RRE LSRRE e-valMAP and KZParam.
L4L_4 Librational8335178.731.835.39.529.0
Western low prograde3335128.91.42.48.06.8
Distant retrograde3335142.31.22.30.43.7

Table 3. Timings of each step of computing 3D tori in the earth-moon ER3BP. ‘Traj.’ is the time to compute the trajectory of length NN, ‘RRE LS’ is the time for the least-squares problem (17), ‘RRE e-val’ is the time for the eigenvalue problem to obtain frequencies from the RRE filter, ‘MAP and KZ’ is the combined time of the MAP estimation and KZ step (dominated by the MAP step), and ‘Param.’ is the time to compute the adaptive parameterization from Sec. 2.2. All times are in seconds.

Conclusion

In this paper, we introduced a method that efficiently computes invariant tori from single trajectory of a symplectic map. The first step is Birkhoff RRE (17), which is an extrapolation method that both classifies the torus as integrable or not, and in the case of integrability returns the frequencies and magnitudes of the most prominent Fourier modes. This frequency content is used by the Bayesian MAP problem (25) to compute the valid rotation vector of the invariant torus. Then, the valid rotation vector is transformed to an optimal one via a KZ basis reduction. Finally, using the optimal rotation vector, we perform the optimization 10 for a parameterization of the invariant torus.

Through the standard map example, we demonstrated that this method can be used to compute large numbers of accurate invariant tori from trajectories of length less than 10000. Most trajectories were computed to a KAM parameterization residual of less than 10−410^{-4}. This may be enough accuracy for many applications, and if it isn’t, the tori could be used to initialize a Newton iteration for a more accurate torus. We found that the rare tori that fail to be approximated are either highly filamentary or they have nearly resonant rotation vectors.

Looking forward, there are many ways the presented algorithm could be improved. From a performance perspective, the four limiting steps are (i) the Birkhoff RRE least-squares problem, (ii) the Birkhoff RRE eigenvalue problem, (iii) the MAP estimation, and (iv) the parameterization optimization. Steps (i), (ii), and (iv) could all be improved by applying more efficient numerical linear algebra techniques tailored to the problem structure. The matrix for (i) is Hankel, so an iterative least-squares algorithm could be performed with a FFT based algorithm for a worst-case cost of O(N2log⁡N)O(N^2 \log N). However, initial tests indicate iterative methods would likely need to be preconditioned to achieve the accuracies necessary for computing the rotation vector. For (ii), we currently solve the full eigenvalue problem for every root of the filter polynomial, but it is possible that a more efficient algorithm would only compute the few most important frequencies for determining the rotation vector. For (iv), speedups could potentially be obtained by taking advantage of the discrete Fourier transform-like structure of the linear algebra. Improvements in step (iii) would need to have a more discrete character, but could potentially be used to find rotation vectors with fewer frequencies of the signal.

From the perspective of theory, a proof of the convergence of the Birkhoff RRE roots to the frequencies ω⋅k\omega\cdot k is still an open question. However, the accuracy of the computed parameterizations in this paper supports the conjecture that the roots do converge. A convergence theorem would also likely require an estimate for the rate of convergence of the roots, which could be incorporated into the MAP problem, and could potentially be pushed all the way through to an error estimate of the final computed torus.

Acknowledgments. This material is based on work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, as a part of the Mathematical Multifaceted Integrated Capability Centers program, under Award No. DE-SC0023164.

We also thank Amelia Chambliss and Elizabeth Paul.

QR Updates for Adaptively Computing Fourier Coefficients

To improve the efficiency of the adaptive least-squares algorithm in § 2.2, we use QR factorization updates [49] on the least-squares system (7) at each step. In particular, in each step of the adaptive algorithm, we need to solve a least-squares problem Aj(K)X=BA_j(\mathcal{K})X=B in each candidate direction jj, where the matrix Aj(K)A_j(\mathcal{K}) consists of columns Λk\Lambda_k for −K−ej≤k≤K+ej-\mathcal{K}-e_j\leq k\leq\mathcal{K}+e_j (see Eq. (8)). As such, we want to avoid recomputing the QR decomposition Aj(K)=Qj(K)Rj(K)A_j(\mathcal{K})=Q_j(\mathcal{K})R_j(\mathcal{K}) as K\mathcal{K} increases.

To do so, consider we take a step in the j′j' direction, having already computed the decompositions Aj(K)=Qj(K)Rj(K)A_j(\mathcal{K})=Q_j(\mathcal{K})R_j(\mathcal{K}) for each jj. For the next step, we need to compute the QR decomposition of Aj(K+ej′)=Qj(K+ej′)Rj(K+ej′)A_j(\mathcal{K}+e_{j'})=Q_j(\mathcal{K}+e_{j'})R_j(\mathcal{K}+e_{j'}). To do this, we notice that the columns of Aj(K)A_j(\mathcal{K}) are all contained within Aj(K+ej′)A_j(\mathbf{K}+\mathbf{e}_{j'}), so we can write

Aj(K+ej′)=(Aj(K)Aj(j′)(K))=(Qj(K)Qj(j′)(K))(Rj(K)Rj(1j′)(K)0Rj(2j′)(K)),\begin{aligned} A_j(\mathbf{K}+\mathbf{e}_{j'}) = \left( \begin{array}{cc} A_j(\mathbf{K}) & A_j^{(j')}(\mathbf{K}) \end{array} \right) \\ &= \left( \begin{array}{cc} Q_j(\mathbf{K}) & Q_j^{(j')}(\mathbf{K}) \end{array} \right) \left( \begin{array}{cc} R_j(\mathbf{K}) & R_j^{(1j')}(\mathbf{K}) \\ 0 & R_j^{(2j')}(\mathbf{K}) \end{array} \right), \end{aligned}

where Aj(j′)(K)A_j^{(j')}(\mathbf{K}) contains the columns in Aj(K+ej′)A_j(\mathbf{K}+\mathbf{e}_{j'}) but not in Aj(K)A_j(\mathbf{K}), namely Λk\Lambda_k for kk satisfying −(K+ej+ej′)⪯k⪯K+ej+ej′-(\mathbf{K}+\mathbf{e}_j+\mathbf{e}_{j'})\preceq k\preceq\mathbf{K}+\mathbf{e}_j+\mathbf{e}_{j'} and ∣kj′∣=(K+ej)j′+1|k_{j'}|=(K+\mathbf{e}_j)_{j'}+1. Then, the unknown QR factors can be computed by the update formulas

Rj(1j′)=Qj∗Aj(j′),R_j^{(1j')}=Q_j^*A_j^{(j')},
Qj(j′)Rj(2j′)=Aj(j′)−QjRj(1j′),Q_j^{(j')}R_j^{(2j')}=A_j^{(j')}-Q_jR_j^{(1j')},

where we suppressed the argument of K\mathbf{K} for all matrices and the second line is computed by a standard QR factorization. We note that the asymptotic cost to compute a QR factorization by updates is equal to the cost of the QR factorization, leading to the complexity estimates in § 2.2.

Solving the RRE Least-Squares System

In order to solve the constrained least-square system (17), we perform a minor update on the original method [30]. The main idea is for the palindromic and sum-to-one constraints to be satisfied to near machine precision, one must perform an orthogonal transformation to obtain a solution. Define the discrete cosine transform matrix (ignoring the constant mode)

Q=(q1⋯qJ),(qk)j=22J+1cos⁡(2πkj2J+1),−J≤j≤J.Q=\left(\begin{array}{ccc} q_1 & \cdots& q_J \end{array}\right),\qquad (q_k)_j=\sqrt{\frac{2}{2J+1}}\cos\left(2\pi k\frac{j}{2J+1}\right),\qquad-J\leq j\leq J.

If we let c=(2J+1)−11+Qc′\mathbf{c}=(2J+1)^{-1}\mathbf{1}+Q\mathbf{c}' where 1\mathbf{1} is the vector of all ones, the fact that (qk)−j=(qk)j(q_k)_{-j}=(q_k)_j clearly implies that c\mathbf{c} is palindromic. Moreover, the orthogonality of the discrete cosine transform (i.e. 1⋅qk=0\mathbf{1}\cdot q_k=0) implies the sum-to-one constraint is satisfied. So, we can substitute this representation into the least-squares problem to find

RRRE2=min⁡c′∈RJ1T∥UQc′+12J+1U1∥2.R_{\mathrm{RRE}}^2=\min_{\mathbf{c}'\in\mathbb{R}^J}\frac{1}{T}\left\|UQ\mathbf{c}'+\frac{1}{2J+1}U\mathbf{1}\right\|^2.

We solve this by a direct QR factorization on UQUQ.

References

  1. [1]Carl D. Murray and Stanley F. Dermott. Solar System Dynamics. Cambridge University Press, Cambridge, 2000.
  2. [2]R. D. Hazeltine and J. D. Meiss. Plasma confinement. Dover Publications, Mineola, N.Y, 2003.
  3. [3]Lise-Marie Imbert-Gerard, Elizabeth Paul, and Adelle Wright. An Introduction to Stellarators: From Magnetic Fields to Symmetries and Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2024.
  4. [4]Alex Haro, Marta Canadell, Jordi-Lluis Figueras, Alejandro Luque, and Josep Maria Mondelo. The Parameterization Method for Invariant Manifolds: From Rigorous Results to Effective Computations, volume 195 of Applied Mathematical Sciences. Springer International Publishing, Cham, 2016.
  5. [5]A. Haro and R. de la Llave. A parameterization method for the computation of invariant tori and their whiskers in quasi-periodic maps: Rigorous results. Journal of Differential Equations, 228(2):530–579, September 2006.DOI
  6. [6]Alex Haro and Rafael de la Llave. A parameterization method for the computation of invariant tori and their whiskers in quasi-periodic maps: Numerical algorithms. Discrete and Continuous Dynamical Systems - B, 6(6):1261–1300, August 2006.
  7. [7]A. Haro and R. de la Llave. A Parameterization Method for the Computation of Invariant Tori and Their Whiskers in Quasi-Periodic Maps: Explorations and Mechanisms for the Breakdown of Hyperbolicity. SIAM Journal on Applied Dynamical Systems, 6(1):142–207, January 2007.DOI
  8. [8]Rafael de la LLave. A tutorial on KAM theory. American Mathematical Society; Oxford University Press, Providence, R.I., Oxford, 2004.
  9. [9]Andrey Nikolaevich Kolmogorov. On conservation of conditionally periodic motions for a small change in Hamilton’s function. In Dokl. akad. nauk Sssr, volume 98, pages 527–530, 1954.
  10. [10]Vladimir I Arnold. Proof of a theorem of AN Kolmogorov on the invariance of quasi-periodic motions under small perturbations of the Hamiltonian. Collected Works: Representations of Functions, Celestial Mechanics and KAM Theory, 1957–1965, pages 267–294, 2009.
  11. [11]Jurgen M¨oser. On invariant curves of area-preserving mappings of an annulus. Nachr. Akad. Wiss. G¨ottingen, II, pages 1–20, 1962.
  12. [12]J.-Ll. Figueras, A. Haro, and A. Luque. Rigorous Computer-Assisted Application of KAM Theory: A Modern Approach. Foundations of Computational Mathematics, 17(5):1123–1193, October 2017.arxiv.org/abs/1601.00084
  13. [13]Nicola Baresi, Zubin P. Olikara, and Daniel J. Scheeres. Fully Numerical Methods for Continuing Families of Quasi-Periodic Invariant Tori in Astrodynamics. The Journal of the Astronautical Sciences, 65(2):157–182, June 2018.DOI
  14. [14]Egemen Kolemen, N. Jeremy Kasdin, and Pini Gurfil. Multiple Poincaré sections method for finding the quasiperiodic orbits of the restricted three body problem. Celestial Mechanics and Dynamical Astronomy, 112(1):47–74, January 2012.DOI
  15. [15]Angel Jorba and Estrella Olmedo. On the computation of reducible invariant tori on a parallel computer. SIAM Journal on Applied Dynamical Systems, 8(4):1382–1404, 2009.DOI
  16. [16]Brian P McCarthy and Kathleen C Howell. Leveraging quasi-periodic orbits for trajectory design in cislunar space. Astrodynamics, 5(2):139–165, 2021.DOI
  17. [17]R. L. Dewar and J. D. Meiss. Flux-minimizing curves for reversible area-preserving maps. Physica D: Nonlinear Phenomena, 57(3):476–506, August 1992.DOI
  18. [18]R. L. Dewar, S. R. Hudson, and P. F. Price. Almost invariant manifolds for divergence-free fields. Physics Letters A, 194(1):49–56, October 1994.DOI
  19. [19]S. R. Hudson and R. L. Dewar. Almost-invariant surfaces for magnetic field-line flows. Journal of Plasma Physics, 56(2):361–382, October 1996.DOI
  20. [20]S. R. Hudson, D. A. Monticello, and A. H. Reiman. Reduction of islands in full-pressure stellarator equilibria. Physics of Plasmas, 8(7):3377–3381, July 2001.
  21. [21]Andrew Giuliani, Florian Wechsung, Georg Stadler, Antoine Cerfon, and Matt Landreman. Direct computation of magnetic surfaces in Boozer coordinates and coil optimization for quasisymmetry. Journal of Plasma Physics, 88(4):905880401, August 2022.DOI
  22. [22]Jacques Laskar. Introduction to Frequency Map Analysis. In Carles Simó, editor, Hamiltonian Systems with Three or More Degrees of Freedom, pages 134–150. Springer Netherlands, Dordrecht, 1999.DOI
  23. [23]J. Laskar. The chaotic motion of the solar system: A numerical estimate of the size of the chaotic zones. Icarus, 88(2):266–291, December 1990.DOI
  24. [24]Suddhasattwa Das, Yoshitaka Saiki, Evelyn Sander, and James A Yorke. Quantitative quasiperiodicity. Nonlinearity, 30(11):4111–4140, November 2017.DOI
  25. [25]E. Sander and J.D. Meiss. Birkhoff averages and rotational invariant circles for area-preserving maps. Physica D: Nonlinear Phenomena, 411:132569, October 2020.DOI
  26. [26]J. D. Meiss and E. Sander. Resonance and weak chaos in quasiperiodically-forced circle maps. Communications in Nonlinear Science and Numerical Simulation, 142:108562, March 2025.DOI
  27. [27]Zhicheng Tong and Yong Li. Exponential convergence of the weighted Birkhoff average. Journal de Mathématiques Pures et Appliquées, 188:470–492, August 2024.DOI
  28. [28]Zhicheng Tong and Yong Li. Quantitative uniform exponential acceleration of averages along decaying waves, September 2024. arXiv:2408.09398 [math].DOI
  29. [29]David Blessing and J. D. Mireles James. Weighted Birkhoff Averages and the Parameterization Method. SIAM Journal on Applied Dynamical Systems, 23(3):1766–1804, September 2024.arxiv.org/abs/2306.16597
  30. [30]M. Ruth and D. Bindel. Finding Birkhoff averages via adaptive filtering. Chaos: An Interdisciplinary Journal of Nonlinear Science, 34(12):123109, December 2024.arxiv.org/abs/2403.19003
  31. [31]Maximilian Ruth, Rogerio Jorge, and David Bindel. The High-Order Magnetic Near-Axis Expansion: Ill-Posedness and Regularization, March 2025. arXiv:2411.04352 [physics].arxiv.org/abs/2411.04352
  32. [32]J. W. Burby, I. A. Maldonado, M. Ruth, D. A. Messenger, and L. Carbajal. Nonperturbative Guiding Center Model for Magnetized Plasmas. Physical Review Letters, 134(17):175101, April 2025.DOI
  33. [33]Alejandro Luque and Jordi Villanueva. Numerical computation of rotation numbers of quasi-periodic planar curves. Physica D: Nonlinear Phenomena, 238(20):2025–2044, October 2009.DOI
  34. [34]Maximilian Ruth. SymplecticMapTools.jl. https://github.com/maxeruth/SymplecticMapTools.jl, 2025.
  35. [35]Victor Szebehely and Giorgio E. O. Giacaglia. On the elliptic restricted problem of three bodies. The Astronomical Journal, 69:230, April 1964.
  36. [36]Shan Zhao and G. W. Wei. A unified discontinuous Galerkin framework for time integration. Mathematical Methods in the Applied Sciences, 37(7):1042–1071, 2014.pubmed.ncbi.nlm.nih.gov/25382889
  37. [37]Michael Kraus. Geometricintegrators.jl: Geometric numerical integration in julia. https://github.com/JuliaGN1/GeometricIntegrators.jl, 2020.
  38. [38]Lloyd N. Trefethen and J. A. C. Weideman. The Exponentially Convergent Trapezoidal Rule. SIAM Review, 56(3):385–458, January 2014.DOI
  39. [39]H. A. David and H. N. Nagaraja. Order statistics. John Wiley, Hoboken, N.J, 3rd ed edition, 2003.
  40. [40]Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems. Springer US, Boston, MA, 2002.
  41. [41]M. Ajtai. Generating hard instances of lattice problems (extended abstract). In Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing, STOC ’96, pages 99–108, New York, NY, USA, July 1996. Association for Computing Machinery.DOI
  42. [42]A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, December 1982.
  43. [43]Wen Zhang, Sanzheng Qiao, and Yimin Wei. HKZ and Minkowski Reduction Algorithms for Lattice Reduction-Aided MIMO Detection. IEEE Transactions on Signal Processing, 60(11):5963–5976, November 2012.DOI
  44. [44]J. D. Meiss and E. Sander. Birkhoff averages and the breakdown of invariant tori in volume-preserving maps. Physica D: Nonlinear Phenomena, 428:133048, December 2021.DOI
  45. [45]Wang Sang Koon, Martin W Lo, Jerrold E Marsden, and Shane D Ross. Dynamical systems, the three-body problem and space mission design. In Equadiff 99: (In 2 Volumes), pages 1167–1181. World Scientific, 2000.DOI
  46. [46]Michel Hénon. Numerical exploration of the restricted problem, v. Astronomy and Astrophysics, 1:223–238, 1969.
  47. [47]Xu Ming and Xu Shijie. Exploration of distant retrograde orbits around moon. Acta Astronautica, 65(5-6):853–860, 2009.DOI
  48. [48]Three-body periodic orbits. https://ssd.jpl.nasa.gov/tools/periodic_orbits.html. Jet Propulsion Laboratory Solar System Dynamics.
  49. [49]Gene H. Golub and Charles F. Van Loan. Matrix computations. Johns Hopkins studies in the mathematical sciences. The Johns Hopkins University Press, Baltimore, fourth edition, 2013.

Paper details

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

views · 2

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