Abstract
In these lectures we review two procedures for constructing finite difference numerical schemes that preserve symmetries of differential equations. The first approach is based on Lie’s infinitesimal symmetry generators, while the second method uses the novel theory of equivariant moving frames. The advantages of both techniques are discussed and illustrated with the Schwarzian differential equation, the Korteweg–de Vries equation and Burgers’ equation. Numerical simulations are presented and innovative techniques for obtaining better invariant numerical schemes are introduced. New research directions and open problems are indicated at the end of these notes.
Access provided by CONRICYT-eBooks. Download chapter PDF
Similar content being viewed by others
1 Introduction
The aim of geometric numerical integration is to develop numerical integrators that preserve geometric properties of the system of differential equations under investigation. Classical examples include symplectic integrators [36, 51], energy preserving methods [77], and schemes that preserve a Lie–Poisson structure [88]. The motivation behind geometric numerical integration is that, as a rule of thumb, such integrators will typically give better global or long term numerical results than standard methods since they incorporate qualitative properties of the system under consideration.
In mathematical physics, most fundamental differential equations are invariant under a certain collection of symmetry transformations. These symmetries can be point transformations, contact transformations, or generalized transformations [68]. In all cases, the symmetries of a differential equation encapsulate important properties of the equation and its solutions. Furthermore, Lie group techniques are amongst the most effective methods for obtaining explicit solutions and conservation laws of nonlinear differential equations [11, 68, 76].
When discretizing differential equations invariant under a certain symmetry group, there are different incentives for preserving the symmetries of these equations. From a physical standpoint, discrete spacetime models should preserve the symmetries of their continuous counterparts. Mathematically, Lie group techniques could then be used to find explicit solutions and compute conservation laws of the discrete models. From a more practical point of view, symmetry-preserving discretizations should share some exact solutions with the original differential equations, or at least provide better approximations than noninvariant numerical schemes.
In the last 30 years, the application of Lie group techniques to finite difference equations has become a very active field of research. To the best of our knowledge, Yanenko and Shokin were the first to use group theoretical methods to study finite difference schemes by introducing first differential approximations of difference equations [82, 87]. The application of Lie group methods to finite difference equations, as we know it today, was first introduced by Dorodnitsyn in 1989 [23]. Early on, one of the main focuses in the field was to construct Lie point symmetry-preserving finite difference approximations of differential equations. Beside Dorodnitsyn, early contributors include Bakirova, Kozlov, Levi, and Winternitz who constructed symmetry-preserving schemes for heat transfer equations [2, 3, 26], variable coefficient Korteweg–de Vries equations [27], Burgers’ equation [37], the nonlinear Schrödinger equation [17], and second-order ordinary differential equations [28]. Symmetry-preserving approximation of Euler–Lagrange equations and their corresponding Lagrangian have also been considered in [29, 30], and the application of Noether’s theorem to compute conservation laws has been extensively studied in the discrete setting [24, 44, 45]. The applications of Lie point symmetries to finite difference equations have also been extended to generalized symmetries [54, 55], λ-symmetries [53, 59], and contact transformations [62].
In recent years, more systematic efforts have been directed towards investigating the numerical performance of symmetry-preserving schemes. For ordinary differential equations, symmetry-preserving schemes have proven to be very promising. For solutions exhibiting sharp variations or singularities, symmetry-preserving schemes systematically appear to outperform standard numerical schemes [13, 14, 18, 50]. For partial differential equations, the improvement of symmetry-preserving schemes versus traditional integrators is not as clear [9, 49, 61, 78]. On one hand, it was shown in [85] that symmetry-preserving schemes do much better in tracking sharp interfaces in Hamilton–Jacobi equations. On the other hand, invariant numerical schemes for evolution equations generally require the use of time-evolving meshes which can lead to mesh tangling and thereby severely limit the use of symmetry-preserving schemes. In this case, special techniques have to be developed to avoid mesh singularities. For example, new ideas relying on r-adaptivity have been implemented to improve the performance of invariant integrators [7]. Also, in [5, 6] an invariant evolution–projection strategy was introduced and invariant meshless discretization schemes were considered in [4].
The preceding references only provide a short bibliographical overview of the field. Many papers had to be omitted. More references on the subject can be found in the survey papers [56, 86], and the books [25, 44].
Given a differential equation with symmetry group G, the first step in constructing a symmetry-preserving numerical scheme is to compute difference invariants of the product action of G on a chosen stencil. There are mainly two approaches for constructing those invariants. Most of the references cited above use the infinitesimal symmetry generators of the group action and Lie’s infinitesimal invariance criterion to construct difference invariants. Alternatively, the difference invariants can be constructed using the novel method of equivariant moving frames mainly developed by Olver, which was done in [4, 21, 50, 70, 78, 79]. Given sufficiently many difference invariants, an invariant numerical scheme is, in general, obtained by finding a suitable combination of these invariants that converges to the original differential equation in the continuous limit. When using Lie’s infinitesimal generator approach, a suitable combination is found by taking the Taylor expansion of the difference invariants and combining them in such a way to obtained the desired invariant scheme. With the method of moving frames, a suitable combination is found more systematically by invariantizing a noninvariant numerical scheme. Since the symmetry group of a differential equation will, in general, act on both the independent and dependent variables, a symmetry-preserving numerical scheme will usually not be defined on a uniform orthogonal mesh.
The application of Lie groups to finite difference equations is a vast and very dynamic field of study. While preparing these lecture notes we had to omit many interesting applications and important results. The focus of these notes will be on the theoretical construction of invariant numerical schemes and their numerical implementation. At the heart of all our considerations are differential equations, finite difference equations, symmetry groups, and invariants. These familiar notions are all reviewed in Sects. 2, 3, and 4. As outlined above, there are two different approaches for computing invariants of a Lie group action. The infinitesimal approach based on Lie’s symmetry generators is introduced in Sect. 4.1, while the equivariant moving frame approach is explained in Sect. 4.2. Section 5 is devoted to weakly invariant equations, which can play an important role in the construction of symmetry-preserving schemes. The construction of symmetry-preserving numerical schemes is carefully explained in Sect. 6. To illustrate the implementation, we consider the Schwarzian differential equation and the Korteweg–de Vries (KdV) equation. In Sect. 7 we carry out numerical simulations for the Schwarzian equation, the KdV equation and Burgers’ equation. For partial differential equations, the invariance of a numerical scheme does not, in general, guarantee better numerical results. We will show that symmetry-preserving schemes can lead to mesh tangling, which limit their practical scope. To circumvent this shortcoming, we discuss new invariant numerical strategies. For the Korteweg–de Vries equation, we introduce invariant evolution–projection schemes and invariant adaptive numerical schemes. Unlike the KdV equation, solutions to Burgers’ equation can exhibit shocks. For these shock solutions we propose a new invariant finite volume type scheme. Finally, in Sect. 8 we identify some open problems and challenges in the field of symmetry-preserving numerical integrators.
2 Differential and Difference Equations
In this section we review the definitions of differential equations and finite difference equations. We take this opportunity to introduce some of the notation used throughout these notes.
2.1 Differential Equations
Let M be an m-dimensional manifold. For 0 ≤ ℓ ≤ ∞, let \(\mathop{\mathrm{J}}\nolimits ^{(\ell)} =\mathop{ \mathrm{J}}\nolimits ^{(\ell)}(M,p)\) denote the extended ℓth order jet space of 1 ≤ p < m dimensional submanifolds S ⊂ M defined as the space of equivalence classes of submanifolds under the equivalence relation of ℓth order contact at a point [68]. Local coordinates on \(\mathop{\mathrm{J}}\nolimits ^{(\ell)}\) are given by the ℓ-jet
where x = (x 1, …, x p) correspond to the independent variables and u (ℓ) denotes the derivatives
In the above notation, J = (j 1, …, j p ) is an ordered p-tuple of nonnegative integers, with entries j i ≥ 0 indicating the number of derivatives taken in the variable x i. The order of the multi-index, denoted by \(\mathop{\mathrm{\#}}\nolimits J = k\), indicates how many derivatives are being taken.
Example 2.1
In the case where p = 2 and q = 1, we have two independent variables (x 1, x 2) = (t, x) and one dependent variable u 1 = u. Then, the second order jet space is parametrized by
Definition 2.2
A differential equation of order n is the zero locus of a differential map \(\varDelta: \mathop{\mathrm{J}}\nolimits ^{(\ell)} \rightarrow \mathbb{R}\). That is,
For later use, we introduce two regularity requirements on differential equations.
Definition 2.3
A differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\) is said to be regular if the rank of its differential
is constant on the domain of definition of \(\varDelta: \mathop{\mathrm{J}}\nolimits ^{(\ell)} \rightarrow \mathbb{R}\).
Example 2.4
Any evolutionary partial differential equation
is regular since the rank of dΔ = du t − df is one.
Definition 2.5
A differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\) is locally solvable at a point \({\bigl (x_{0},u_{0}^{(\ell)}\bigr )}\) if there exists a smooth solution u = f(x), defined in the neighborhood of x 0, such that u 0 (ℓ) = f (ℓ)(x 0). A differential equation which is both regular and locally solvable is said to be fully regular.
The above description assumes that a submanifold S ⊂ M is locally represented as the graph of a function \(S ={\bigl \{{\bigl ( x,f(x)\bigr )}\bigr \}}\). Alternatively, when no distinction between independent and dependent variables is made, a submanifold S ⊂ M is locally parameterized by p variables \(s = (s^{1},\ldots,s^{p}) \in \mathbb{R}^{p}\) such that
In numerical analysis, the independent variables s = (s 1, …, s p) are called computational variables [39]. These are the variables that are discretized when finite difference equations are introduced in Sect. 2.2. We let \(\mathcal{J}^{(\ell)}\) denote the ℓth order jet space of submanifolds S ⊂ M parametrized by computational variables. Local coordinates on \(\mathcal{J}^{(\ell)}\) are given by
with 1 ≤ i ≤ p, 1 ≤ α ≤ q, and \(0 \leq \mathop{\mathrm{\#}}\nolimits A \leq \ell\).
Remark 2.6
We hope that the jet notations \({\bigl (x,u^{(\ell)}\bigr )}\) and \({\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )}\) will not confuse the reader. The independent variable, that is x and s, respectively, indicates with respect to which variables the dependent variables u (and x in the second case) are differentiated in u (ℓ).
Example 2.7
In the case where p = 2 and m = 3, let (s 1, s 2) = (τ, s) denote the two computational variables and let (t, x, u) be a local parametrization of M. Then the second order jet space \(\mathcal{J}^{(2)}\) is parametrized by
The transition between the jet coordinates (1) and (3) is given by the chain rule. Provided
the implicit total derivative operators
are well-defined, and successive application of those operators to the dependent variables u α will give the coordinate expressions for the x-derivatives of u in terms of the s-derivatives of x and u:
We note that the nondegeneracy constraint (4) implies that the change of variables x = x(s) is invertible.
Example 2.8
Combining Examples 2.1 and 2.7, assume that x = x(τ, s) and t = t(τ, s) are functions of the computational variables (τ, s). Provided
the implicit derivative operators
are well-defined. It follows that
Relations for the higher order derivatives are obtained by applying (7) to (8).
Given a differential equation (2), the chain rule (5) can be used to re-express (2) in terms of x i = x i(s), u α = u α(s) and their computational derivatives \(x_{s^{A}}^{i}\), \(u_{s^{A}}^{\alpha }\):
Recall that \({\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} = (s,\mathop{\ldots }x_{s^{A}}^{i}\mathop{\ldots }u_{s^{A}}^{\alpha }\mathop{\ldots }) \in \mathcal{J}^{(\ell)}\) for \(\bar{\varDelta }= 0\) in (9a) while \({\bigl (x,u^{(\ell)}\bigr )} = (x,\mathop{\ldots }u_{x^{J}}^{\alpha }\mathop{\ldots }) \in \mathop{\mathrm{J}}\nolimits ^{(\ell)}\) in Δ = 0. Equation (9a) can be supplemented by companion equations [64],
The latter are introduced to impose restrictions on the change of variables x = x(s). The system of differential equations (9) is called an extended system of the differential equation (2). For the extended system of differential equations (9) to share the same solution space as the original equation (2), the companion equations (9b) cannot introduce differential constraints on the derivatives \(u_{s^{A}}^{\alpha }\).
Definition 2.5 is readily adapted to the computational variable framework.
Definition 2.9
A differential equation \(\bar{\varDelta }{\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} = 0\) (or system of differential equations) is regular if the rank of its differential
is constant on the domain of definition. The equation (or system of equations) is locally solvable at a point (s 0, x 0 (ℓ), u 0 (ℓ)) if there exists a smooth solution x = f(s), u = g(s), defined in the neighborhood of s 0, such that x 0 (ℓ) = f (ℓ)(s 0) and u 0 (ℓ) = g (ℓ)(s 0). The differential equation (or system of differential equations) is said to be fully regular if it is both regular and locally solvable.
Example 2.10
As one of our main examples in these notes, we consider the Korteweg–de Vries (KdV) equation
We introduce the computational variables (τ, t) so that x = x(τ, s), t = t(τ, s). Then the implicit total derivative operators are given by (7). Before proceeding any further, we assume that
In other words,
where k ≠ 0 and t 0 are constants. The reasons for imposing the constraints (11) are explained in Example 3.10. The operators of implicit differentiation (7) then simplify to
Therefore,
and the KdV equation (10) becomes
together with the companion equations (11). The differential equation (13) is reminiscent of the equation one obtains when writing the KdV equation in Lagrangian form [9]. In the classical Lagrangian framework, the differential constraint
is also imposed. The KdV equation then reduces to
together with the companion equations (11), (14). In particular, when k = 1 in (12), we obtain the system of differential equations
2.2 Finite Difference Equations
We now move on to the discrete setting, which is the main focus of these lecture notes. In the previous section, we introduced two different jets spaces, namely \(\mathop{\mathrm{J}}\nolimits ^{(\ell)}\) and \(\mathcal{J}^{(\ell)}\). The motivation for introducing computational variables and the corresponding jet space \(\mathcal{J}^{(\ell)}\) stems from the fact that the discrete framework is more closely related to \(\mathcal{J}^{(\ell)}\) than \(\mathop{\mathrm{J}}\nolimits ^{(\ell)}\).
Let \(N = (n^{1},\ldots,n^{p}) \in \mathbb{Z}^{p}\) denote an integer-valued multi-index. Thinking of the multi-index N as sampling the computational variables \(s = (s^{1},\ldots,s^{p}) \in \mathbb{R}^{p}\) at integer values, the discrete notation (x N , u N ) should be understood as sampling the submanifold \(S ={\bigl \{{\bigl ( x(s),u(s)\bigr )}\bigr \}} \subset M\) at the integer-valued points \(s = N \in \mathbb{Z}^{p} \subset \mathbb{R}^{p}\). In other words \((x_{N},u_{N}) ={\bigl ( x(N),u(N)\bigr )}\). To approximate the ℓ-jet \({\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} \in \mathcal{J}^{(\ell)}\) at s = N, we consider a finite collection of points
where \(K \in \mathbb{Z}^{p}\). We require that the point (x N , u N ) is always included and that
so that no two discrete independent variables are the same. We refer to (16) as the ℓth order discrete jet at N. In numerical analysis, a point in (16) is also called a stencil. For theoretical purposes, one can assume that the multi-index \(K \in (\mathbb{Z}^{\geq 0})^{p}\) only takes nonnegative values and that \(0 \leq \mathop{\mathrm{\#}}\nolimits K = k^{1} +\ldots +k^{p} \leq \ell\). The latter provides the minimal number of points required to approximate the ℓ-jet \({\bigl (x,u^{(\ell)}\bigr )}\) (or \({\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )}\)) by first order forward differences. In applications, especially when constructing numerical schemes, it is generally preferable to consider points centered around (x N , u N ) and to include more than the minimum number of points in \({\bigl (N,x_{N}^{[\ell]},u_{N}^{[\ell]}\bigr )}\) required to approximate \({\bigl (x,u^{(\ell)}\bigr )}\) for better numerical accuracy and stability. From now on, we will assume that a certain stencil (16) has been chosen. We denote by
the union over all the stencils and call \(\mathcal{J}^{[\ell]}\) the ℓth order discrete jet space as \(\mathcal{J}^{[\ell]}\) provides an approximation of \(\mathcal{J}^{(\ell)}\). Since the jet coordinates of \(\mathop{\mathrm{J}}\nolimits ^{(\ell)}\) can be expressed in terms of the jet coordinates of \(\mathcal{J}^{(\ell)}\) using (5), it follows that the points in \(\mathcal{J}^{[\ell]}\) can be used to approximate \(\mathop{\mathrm{J}}\nolimits ^{(\ell)}\).
Example 2.11
Consider the case where p = 2 and the dimension of the manifold M is dimM = m = 3. Let (t, x, u) be local coordinates on M. In the continuous case, see Example 2.7, we introduced the computational variables (τ, s). In the discrete case, let \(N = (n,i) \in \mathbb{Z}^{2}\), which can be thought of as evaluating the computational variables (τ, s) at integer values. To make the multi-index notation more compact, we let
Working with forward differences, the simplest first order discrete jet is parametrized by
First order approximations of the first order derivatives (t τ , x τ , u τ ) and (t s , x s , u s ) on a grid with unit spacing are then given by
Referring to (8) for the expressions of the t and x derivatives of u in terms of the computational variable derivatives, and using (17) we have that
The latter expressions are first order forward approximations of the first order partial derivatives u x and u t on any mesh that satisfies
the latter being a discrete version of the nondegeneracy condition (6). The procedure can be repeated to obtain approximations of higher order derivatives on arbitrary meshes. For example, applying the implicit derivative operators (7) to the first order derivative expressions (8) one obtains formulas for the second order derivatives u xx , u xt , and u tt expressed in terms of the computational derivatives. Substituting the approximations (17) and the second order derivative approximations
into the formulas obtained yields discrete approximations for u xx , u xt , and u tt in the computational variables on an orthogonal grid with unit spacing.
Definition 2.12
A finite difference equation is the zero locus of a discrete map \(E: \mathcal{J}^{[\ell]} \rightarrow \mathbb{R}\). That is,
Definition 2.13
A finite difference equation \(E: \mathcal{J}^{[\ell]} \rightarrow \mathbb{R}\) is said to be regular if the rank of the differential
is constant for all N in the domain of definition of the equation.
Finite difference equations can be studied as mathematical objects of interest in their own [31, 44, 63]. In the following we are interested in finite difference equations that approximate differential equations.
Definition 2.14
A finite difference equation E(N, x N [ℓ], u N [ℓ]) = 0 is said to be consistent with the differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\) (or \(\bar{\varDelta }{\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} = 0)\) if in the continuous limit (x N+K , u N+K ) → (x N , u N ),
Remark 2.15
The process of taking continuous limits is discussed in more details in Sect. 6.
Definition 2.16
Let \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\) be a differential equation with extended system \(\{\bar{\varDelta }{\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} = 0,\,\tilde{\varDelta }{\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} = 0\}\). A numerical scheme is a system of finite difference equations
where \(\overline{E}(N,x_{N}^{[\ell]},u_{N}^{[\ell]}) = 0\) approximates the differential equation
and the equations \(\widetilde{E}(N,x_{N}^{[\ell]},u_{N}^{[\ell]}) = 0\) provide an approximation of the companion equations
Intuitively, the difference equations \(\widetilde{E}(N,x_{N}^{[\ell]},u_{N}^{[\ell]}) = 0\) provide constraints on the mesh used to approximate the differential equation Δ = 0. The latter should not yield any restrictions on the discrete dependent variables u N [ℓ].
Example 2.17
To illustrate Definition 2.16, let us consider the KdV equation (10). Assume the equation is to be discretized on the orthogonal mesh
where k, h > 0, \((n,i) \in \mathbb{Z}^{2}\), and t 0, x 0 are arbitrary constants. The mesh (19) can be encapsulated in a system of finite difference equations in different ways. For example, it is not difficult to see that (19) is the solution to the system of equations
The mesh (19) is also a solution to
The difference between the two systems of mesh equations is that in (20) the time step k and the spatial step h are fixed by the system whereas in (21) those steps corresponds to constants of integration. In both cases, the KdV equation can be approximated by
The systems of equations (20)– (22) or (21)– (22) provide two examples of Definition 2.16. They also illustrate the fact that, in general, the equations \(\widetilde{E} = 0\) specifying the mesh are not unique.
3 Lie Symmetries
Let G be an r-dimensional Lie group, and let \(\mathcal{M}\) be a d-dimensional manifold with local coordinates z = (z 1, …, z d). In the following, the manifold \(\mathcal{M}\) can represent the submanifold jet spaces \(\mathop{\mathrm{J}}\nolimits ^{(\ell)}\) or \(\mathcal{J}^{(\ell)}\) or the discrete jet space \(\mathcal{J}^{[\ell]}\). In the latter case, \(\mathcal{M}\) should in fact be called a lattifold or lattice variety, that is a manifold-like structure modeled on \(\mathbb{Z}^{p}\) [65, 67].
Definition 3.1
A transformation group acting on a manifold \(\mathcal{M}\) is given by a Lie group G and a smooth map \(\varPhi: G \times \mathcal{M}\rightarrow \mathcal{M}\), such that Φ(g, z) = g ⋅ z, which satisfies the following two properties
and where e ∈ G denotes the identity element.
It follows from (23) that the inverse of the transformation defined by the group element g is given by the inverse group element g −1. Therefore g induces a diffeomorphism from \(\mathcal{M}\) to itself.
Remark 3.2
Definition 3.1 assumes that the group action is global, meaning that g ⋅ z is defined for every g ∈ G and every \(z \in \mathcal{M}\). In practice, group actions may only be defined locally, meaning that for a given \(z \in \mathcal{M}\), the transformation g ⋅ z is only defined for group elements g sufficiently near the identity. For a local transformation group, the map Φ is defined on an open subset \(\mathcal{B}\) with \(\{e\} \times \mathcal{M}\subset \mathcal{B}\subset G \times \mathcal{M}\), and the conditions (23) of Definition 23 are imposed wherever they are defined.
In the following, we use capital letters to denote the image of a point under a group transformation. For example,
At the infinitesimal level, let \(\mathfrak{g}\) denote the Lie algebra of vector fields corresponding to the infinitesimal generators of the group action. A vector field
will be in \(\mathfrak{g}\) if it is tangent to the orbits of a one-parameter subgroup of transformations of G. The flow through the point \(z \in \mathcal{M}\) generated by a vector field \(\mathbf{v} \in \mathfrak{g}\), is found by solving the initial value problem
The maximal integral curve is denoted exp[ε v] ⋅ z, and is called the exponentiation of the infinitesimal generator v.
Definition 3.3
Let G be a local Lie group of transformations acting on \(\mathcal{M}\). The Lie group G is a (local) symmetry group of the (fully) regular equationFootnote 1 F(z) = 0 if and only if
for all g ∈ G such that the local action is defined. Infinitesimally, a connected Lie group of transformations G acting on \(\mathcal{M}\) is a local symmetry group of F(z) = 0 if and only if
Remark 3.4
Definition 3.3 extends to systems of equations and more general local groups of transformations by including discrete transformations as well [10, 40, 42, 43]. In the following we restrict all our considerations to Lie point symmetries and omit the interesting case of discrete symmetries.
3.1 Symmetries of Differential Equations
Symmetries of differential equations are covered extensively in many excellent textbooks such as [11, 12, 43, 68, 71, 76]. We refer to these references for a more detailed exposition.
If \(\mathcal{M} =\mathop{ \mathrm{J}}\nolimits ^{(\ell)}\), then the local group action is given by the prolonged action \((X,U^{(\ell)}) = g \cdot {\bigl ( x,u^{(\ell)}\bigr )}\) on the submanifold ℓ-jet \({\bigl (x,u^{(\ell)}\bigr )}\). Let
denote the local group action of G on the manifold M locally coordinatized by (x, u). To compute the prolonged action, we introduce the implicit differentiation operators [33],
denotes the entries of the inverse Jacobian matrix and
is the total differentiation operator with respect to the independent variable x j. In the above formula, \(e_{j} = (0,\ldots,0,1,0,\ldots,0) \in \mathbb{R}^{p}\) denotes the unit vector with zeros everywhere except in the jth component. We note that the operators (26) mutually commute
Successively applying the implicit differentiation operators (26) to U α = g ⋅ u α yields the expressions for the prolonged action
At the infinitesimal level, let
denote an infinitesimal generator of the group action (25). The prolongation of (27) to \(\mathop{\mathrm{J}}\nolimits ^{(\ell)}\) is given by
where the prolonged vector field coefficients are defined recursively by the standard prolongation formula
Given a differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\), the Lie point symmetries of the equation are found from the infinitesimal invariance criterion
The latter yields a differential equation in x, u and the derivatives of u with respect to x, as well as ξ i(x, u) and ϕ α(x, u) and their partial derivatives with respect to x and u. After eliminating any dependencies among the derivatives of the us due to the equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\), one can equate the coefficients of the remaining unconstrained partial derivatives of u to zero. This yields a system of linear partial differential equations for the coefficients ξ i and ϕ α, called the determining equations of the (maximal) Lie symmetry algebra. The procedure for obtaining and solving the determining equations has been implemented in all major computer algebra systems such as Macsyma, Maple, Mathematica, MuMath and Reduce. An extensive list of references on the subject can be found in [19].
Example 3.5
To illustrate the algorithm outlined above, we compute the infinitesimal generators of the KdV equation (10). Let v = ξ(t, x, u)∂ x + η(t, x, u)∂ t + ϕ(t, x, u)∂ u denote a general vector field on \(\mathbb{R}^{3}\). The third order prolongation of v is
where
Applying the infinitesimal invariance criterion (24) to the KdV equation (10) we obtain
where u satisfies (10). Substituting the expressions (29) into (30) and replacing u t by − uu x − u xxx , we obtain the determining equations of the Lie symmetry algebra, which we now solve. Firstly, the coefficient of u xxt is D x η = η x + u x η u which implies that η x = η u = 0. In other words, η = η(t) is a function of t onlyFootnote 2. Secondly, the coefficient of u xx 2 yields ξ u = 0 and thus ξ = ξ(t, x), implying that the admitted Lie symmetries are projectable. Next, the coefficient of u xxx gives η t − 3ξ x = 0. Integrating the latter with respect to x, we find that \(\xi = \frac{1} {3}x\,\eta _{t} +\chi (t)\). The coefficient of u xx implies that ϕ uu = ϕ xu = 0 so that ϕ = σ(t)u + φ(t, x). Next the coefficient in u x yields the equation
Substituting the expressions for ξ and ϕ, we find
Finally, the term with no derivatives of u gives ϕ t + ϕ xxx + u ϕ x = 0, which after substitution yields
Since η = η(t) and χ = χ(t) are functions of t, the latter equation holds for all (t, x, u) provided that η tt = χ tt = 0. Therefore,
and the maximal Lie symmetry algebra is spanned by the four vector fields
Exercise 3.6
Show that the symmetry group of the ordinary differential equation u xx = 0 is eight-dimensional, and generated by
Show that the corresponding group of local transformations is the projective group \(SL(3, \mathbb{R})\) acting via fractional linear transformations
where \(\epsilon _{1},\ldots,\epsilon _{9} \in \mathbb{R}\) are group parameters.
Exercise 3.7
Consider the Schwarzian differential equation
where F(x) is an arbitrary function.
-
1.
Find the determining equations for the vector fields spanning the maximal Lie symmetry algebra and show that a basis is given by
$$\displaystyle{ \mathbf{v}_{1} = \frac{\partial } {\partial u}\;,\quad \mathbf{v}_{2} = u \frac{\partial } {\partial u}\;,\quad \mathbf{v}_{3} = u^{2} \frac{\partial } {\partial u}\;. }$$(34) -
2.
Show that the corresponding local Lie group of transformations is
$$\displaystyle{ X = x\;,\qquad U = \frac{au + b} {cu + d}\;,\quad \mbox{ with $ad - bc = 1$}\;. }$$(35) -
3.
When F(x) ≡ 0 is identically zero, show that the maximal Lie symmetry algebra is four-dimensional and determine a basis. Also find the corresponding finite group transformations.
Exercise 3.8
Show that the maximal Lie symmetry algebra of Burgers’ equation
where ν > 0 denotes the viscosity, is spanned by the vector fields
In the computational variable framework, the local transformation group G acting on the manifold M is trivially extended to the computational variables. That is,
The prolongation of an infinitesimal generator (27) to \(\mathcal{J}^{(\ell)}\) is then simply given by
where \(D_{s}^{J} = (D_{s^{1}})^{j_{1}}\cdots (D_{s^{p }})^{j_{p}}\) denotes the total differentiation operator in the computational variables s = (s 1, …, s p) with
Definition 3.9
Let G be a symmetry group of the differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\). The extended system of differential equations
is said to be G-compatible if G is a symmetry group of (38). That is,
and where the prolonged action is defined. At the infinitesimal level,
for all infinitesimal generators \(\mathbf{v} \in \mathfrak{g}\).
Example 3.10
Recall from Example 3.5 that the KdV equation (10) is invariant under a four-dimensional maximal Lie symmetry group whose associated algebra of infinitesimal generators is spanned by the vector fields (31). In the computational variables (τ, s) introduced in Example 2.10, the first prolongation of the infinitesimal generators (31) is given by
By direct computation, it is not hard to verify that for the differential equation (15)
Therefore, Eq. (15) is invariant under the symmetry group of the KdV equation. Also,
whenever
Therefore, the companion equations (11), (14) are invariant under the symmetry group of the KdV equation. The extended system of differential equations (11), (14), (15) is therefore G-compatible with the symmetry group of the KdV equation.
3.2 Symmetries of Finite Difference Equations
As in Sect. 3.1, let G be a local Lie group of transformations acting smoothly on the manifold M. The induced action on the discrete n-jet (N, x N [ℓ], u N [ℓ]) is given by the product action
where each point (x N+K , u N+K ) is transformed by the same group transformation g. At the infinitesimal level, given the vector field
where ξ N i = ξ i(x N , u N ) and ϕ N α = ϕ α(x N , u N ), the prolonged vector field is given by
which is obtained by adding copies of v evaluated at the different points in the discrete jet (N, x N [ℓ], u N [ℓ]).
Remark 3.11
The above considerations can be generalized by allowing the group action (39) or the infinitesimal generator (40) to depend on the multi-index N. For example, in (40), the vector field coefficients could be functions of N so that ξ N i = ξ i(N, x N , u N ) and ϕ N α = ϕ α(N, x N , u N ). When constructing symmetry-preserving schemes, this more general case does not occur as the transformation group that one considers is the group of point symmetries of the differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\), which only contains point transformations in the x, u variables.
Using the infinitesimal invariance criterion
the symmetries of finite difference equations can be computed in a manner similar to the differential case. Equation (41) yields a finite difference equation for the vector field coefficients ξ N i and ϕ N α. Since the invariance condition (41) only has to hold on the solution of the difference equation, one must eliminate any dependencies among (x N , u N ) and their shifts due to the equation E(N, x N [ℓ], u N [ℓ]) = 0. Differentiating the resulting equation with respect to the remaining variables sufficiently many times, one obtains a system of differential equations for the vector field coefficients. Once the differential equations are solved, one will, in general, have to substitute the solution into the original difference equation for the vector field coefficients, or an intermediate equation obtained along the way, and solve the resulting equation to obtain the symmetry generators.
Example 3.12
As a first example, let us compute the admitted infinitesimal generators of the ordinary difference equation
Let
be a vector field, where we allow ϕ i = ϕ(i, u i ) to depend on the discrete index \(i \in \mathbb{Z}\). Applying the infinitesimal invariance criterion (41) we obtain the equation
where we replaced u i+2 by the right-hand side of (42). Applying the differential operator \({\bigl (1/b(i)\bigr )}\partial _{u_{i}} -{\bigl ( 1/a(i)\bigr )}\partial _{u_{i+1}}\) to (43) we obtain the differential–difference equation
where the prime notation means differentiation with respect to the second entry of the function. Differentiating (44) with respect to u i we obtain
Integrating this equation once, we find that
for some arbitrary function α(i). Substituting (45) in (44) yields α(i + 1) = α(i). Thus, α(i) = c is constant. Integrating (45), we obtain that
Substituting (46) in (43) we conclude that β(i) must be a solution of the equation β i+2 = a(i)β i+1 + b(i)β i . Thus, the Lie algebra of infinitesimal symmetry generators is spanned by
Example 3.13
As a second example, we consider the autonomous discrete potential Korteweg–de Vries equation (dpKdV)
which can be found in the work of Hirota [38]. Let
be a vector field. Implementing the infinitesimal invariance criterion (41), we obtain the equation
Applying the operator \(\partial _{u_{i+1}^{n}} + \partial _{u_{i}^{n+1}}\) yields
Differentiating with respect to u i+1 n gives
Substituting ϕ i n in (49) we obtain the difference equation
which implies that α(i, n) = γ(i + n). Substituting ϕ i n in (48) yields the constraints
which imply that
where c 1, c 2, . c 3 are arbitrary constants. We conclude that the Lie algebra of infinitesimal symmetry generators is spanned by
These vector fields satisfy the commutation relations
which are isomorphic to the commutation relations of the pseudo-Euclidean Lie algebra \(\mathfrak{e}(1,1)\) [83].
4 Invariants
Intuitively, an invariant is a quantity that remains unchanged under the action of a group of local transformations. In this section, we review two methods for constructing invariants. The first approach is based on Lie’s infinitesimal invariance criterion which leads to systems of first order partial differential equations that can be solved using the method of characteristics. The second approach uses the novel theory of equivariant moving frames. In this framework, invariants are obtained by solving a system of nonlinear algebraic equations. Remarkably, the latter can be solved for a wide variety of group actions.
4.1 Lie’s Infinitesimal Approach
As in Sect. 3, we consider the differential and finite difference cases simultaneously by considering an r-parameter local Lie group G acting on \(\mathcal{M}\), which can represent either \(\mathop{\mathrm{J}}\nolimits ^{(\ell)}\), \(\mathcal{J}^{(\ell)}\) or \(\mathcal{J}^{[\ell]}\).
Definition 4.1
A function \(I: \mathcal{M}\rightarrow \mathbb{R}\) is said to be a G-invariant if
where the action is defined. At the infinitesimal level, \(I: \mathcal{M}\rightarrow \mathbb{R}\) is an invariant if
Remark 4.2
The notion of an invariant is more restrictive than that of an invariant equation. The invariance of an equation only has to hold on its solution space whereas the invariance of a function must hold on its domain of definition.
Finding invariants from the group invariance condition (50) can be difficult as the group action is generally nonlinear. One of the key insights of Sophus Lie was to work with the infinitesimal invariance condition (51) as the latter is a linearized version of the nonlinear problem. Let
be a basis of the Lie algebra \(\mathfrak{g}\) of infinitesimal generators of the Lie group action G. To find the functions \(I: \mathcal{M}\rightarrow \mathbb{R}\) invariant under the group action G, we require that the infinitesimal invariance criterion (51) holds for each basis element (52). This yields the system of first order linear partial differential equations
The latter is solved using the method of characteristics. The corresponding characteristic system of ordinary differential equations is
and, in the generic case, the system of equations (54) yields a complete set of \(\dim \mathcal{M}- r\) functionally independent invariants
Definition 4.3
A set of invariants I c = {…, I ν(z), …} is said to be complete if any invariant function \(I: \mathcal{M}\rightarrow \mathbb{R}\) can be expressed in terms of those invariants. That is,
Most textbooks on symmetries and differential equations cover Lie’s infinitesimal method of computing differential invariants [11, 12, 43, 68, 71, 76]. Differential invariants are fundamental objects in mathematics and have many applications. They occur in geometry as the curvature of curves, surfaces, and submanifolds [35], they are used in differential equations to reduce the order of ordinary differential equations and find invariant solution of partial differential equations [11, 12, 43, 68, 76], their signature manifold is used to solve local equivalence problems [34, 47, 71, 84], geometric flows of differential invariants are closely related to completely integrable equations [66], and have applications in computer vision [48], climate and turbulence modeling [8], and much more.
In the finite difference situation, since the Lie group G acts trivially on the multi-index N, the components of N will always provide p invariants. Solving the infinitesimal invariance criterion
where κ = 1, …, r, will, in the generic case, produce \(\dim \mathcal{J}^{[\ell]} - p - r\) difference invariants I ν(x N [ℓ], u N [ℓ]) independent of the multi-index N.
Example 4.4
To illustrate the application of the infinitesimal invariance criterion (55), we consider the special linear group \(SL(2, \mathbb{R})\) acting on \(M = \mathbb{R}^{2} =\{ (x,u)\}\) by the fractional linear action (35) with infinitesimal generators (34). For future reference, we consider the order three discrete jet space \(\mathcal{J}^{[3]}\) with coordinates
To compute a complete set of finite difference invariants on \(\mathcal{J}^{[3]}\), we prolong the infinitesimal generators (34) to \(\mathcal{J}^{[3]}\):
Omitting the trivial invariant given by the index i, we expect \((\dim \mathcal{J}^{[3]} - 1) -\dim \mathfrak{g} = 8 - 3 = 5\) functionally independent invariants. Clearly, four of them are given by
To find the remaining functionally independent invariant I = I(u i−1, u i , u i+1, u i+2), we first solve the differential equation
using the method of characteristics. The corresponding characteristic system of ordinary differential equations is given by
The three functionally independent solutions are
The functions (59) form a complete set of difference invariants for the infinitesimal generator v 1. To proceed further, we notice that any function \(I: \mathcal{J}^{[3]} \rightarrow \mathbb{R}\) invariant under all three infinitesimal generators (57) must necessarily be a function of the invariants (59), that is I = I(I i−1, I i , I i+1). Thus to find the functions that are simultaneously invariant under v 1 [3] and v 2 [3], we must now restrict the vector field v 2 [3] to the variables (59). The result is
Thus, the characteristic system associated with the differential equation
is
The two functionally independent solutions are
Therefore, any invariant function I must be expressible in terms of (60). That it, I = I(J i , J i+1). The restriction of the vector field v 3 [3] to the variables (60) yields
Thus, the equation v 3 [3](I) = 0 becomes
Solving the characteristic system
we find that the cross-ratio
is an invariant of the \(\mathop{\mathrm{SL}}\nolimits (2, \mathbb{R})\) product action on \(\mathcal{J}^{[3]}\).
Exercise 4.5
Continuing Exercise 3.8, introduce the discrete points (t i n, x i n, u i n), where \((n,i) \in \mathbb{Z}^{2}\).
-
1.
Verify that the equation
$$\displaystyle{ t_{i+1}^{n} - t_{ i}^{n} = 0\;, }$$(62)is invariant. Therefore, Burgers’ equation can be invariantly discretized on a mesh with horizontal time layers, the discrete time t n being only a function of \(n \in \mathbb{Z}\).
-
2.
Compute a complete set of difference invariants on the lattice
using Lie’s infinitesimal method.
4.2 Moving Frame Approach
The method of equivariant moving frames is a new theoretical formulation of Cartan’s method of moving frames [16, 34, 47, 71]. In this novel framework, moving frames are no longer constrained by frame bundles or connections and can thereby be extended to discrete geometry. The theory of equivariant moving frames for local Lie group actions was first presented in [33] and then extended to infinite-dimensional Lie pseudo-group actions in [73, 74]. For a comprehensive introduction we refer the reader to the textbook [64]. In the discrete setting, the theoretical foundations have been expounded in [67, 70].
As in the previous sections, our starting point is an r-dimensional local Lie group of transformations G acting on the d-dimensional manifold \(\mathcal{M}\).
Definition 4.6
A right moving frame is a G-equivariant map \(\rho: \mathcal{M}\rightarrow G\). The G-equivariance means that
Remark 4.7
It is also possible to consider left moving frames. Given a right moving frame \(\rho: \mathcal{M}\rightarrow G\), a left moving frame \(\bar{\rho }: \mathcal{M}\rightarrow G\) is simply given by group inversion, \(\bar{\rho }=\rho ^{-1}\). Thus, a left moving frame \(\bar{\rho }\) is a G-equivariant map satisfying \(\bar{\rho }(g \cdot z) = g\bar{\rho }(z)\).
To guarantee the existence of a moving frame, the group action must satisfy certain regularity assumptions.
Definition 4.8
A Lie group G is said to act freely at z if the isotropy group
is trivial, i.e. G z = {e}. The group action is locally free at z if the isotropy group is discrete. The action is (locally) free on \(\mathcal{M}\) if it is (locally) free at all \(z \in \mathcal{M}\).
When the action is (locally) free, the dimension of the group orbits is constant and equal to r = dim G.
Definition 4.9
A Lie group action is said to be regular if the orbits form a regular foliation.
The main existence theorem for moving frames is given by the following proposition.
Proposition 4.10
If the action of G on \(\mathcal{M}\) is locally free and regular, then a moving frame locally exists on \(\mathcal{M}\).
Remark 4.11
Let \(\mathcal{V}\) be a connected open submanifold of \(\mathcal{M}\) where a moving frame exists. By restricting \(\mathcal{M}\) to \(\mathcal{V}\), we can always assume that a moving frame is globally defined on \(\mathcal{M}\).
In practice, the construction of a moving frame is based on the choice of a cross-section \(\mathcal{K}\) to the group orbits. For simplicity, we assume that \(\mathcal{K}\) is a coordinate cross-section, which means that it is specified by fixing some of the coordinates of \(z \in \mathcal{M}\) to constant values:
When the action is free and regular, the right moving frame at z is the unique group element ρ(z) sending z onto the cross-section \(\mathcal{K}\), that is \(\rho (z) \cdot z \in \mathcal{K}\). The expressions for the right moving frame are obtained by solving the normalization equations
for the group parameters g = ρ(z). Given a right moving frame, there is a systematic mechanism for constructing invariants known as the invariantization procedure.
Definition 4.12
The invariantization of a function F(z) is the invariant
The fact that (65) is an invariant follows from the G-equivariance of the right moving frame:
Geometrically, ι(F) is the unique invariant that agrees with F on the cross-section \(\mathcal{K}\). In particular, the invariantization of an invariant I is the invariant itself, ι(I) = I. Therefore, the invariantization map ι defines a canonical projection (depending upon the moving frame) from the space of functions to the space of invariants.
The invariantization of the components of z is of particular interest. The invariants ι(z a) = ρ(z) ⋅ z a, a = 1, …, d, are called normalized invariants. By the moving frame construction, the invariantization of the component functions defining the cross-section (63) yields constant invariants, \(\iota (z^{a_{\kappa }}) = c^{\kappa }\). These are called phantom invariants. The following proposition explains why the normalized invariants are important.
Proposition 4.13
The normalized invariants ι(z a), a = 1, …, d, form a complete set of invariants on \(\mathcal{M}\).
Proposition 4.13 follows from the replacement principle. If I = I(z) is an invariant, since ι(I) = I, it follows that
In other words, the invariant I(z) can be expressed as a function of the normalized invariants by replacing z with the invariants ι(z).
For an arbitrary manifold \(\mathcal{M}\), the group action of G on \(\mathcal{M}\), does not have to be free. On the other hand, when \(\mathcal{M}\) is either \(\mathop{\mathrm{J}}\nolimits ^{[\ell]}\), \(\mathcal{J}^{(\ell)}\) or \(\mathcal{J}^{[\ell]}\), it is always possible, under some mild assumptions, to choose ℓ large enough so that the prolonged action becomes (locally) free. To state the result precisely, we need the following technical definitions.
Definition 4.14
Let G be a local Lie group of transformations acting on the manifold M. The isotropy subgroup of a subset S of M is the subgroup
The global isotropy subgroup of a subset S of M is the subgroup
Definition 4.15
A local Lie group of transformations G is said to act effectively on subsets if, for any open subset U ⊂ M, G U ⋆ = {e}. The local Lie group acts locally effectively on subsets if, for any open subset U ⊂ M, G U ⋆ is a discrete subgroup of G.
In the differential case, the following theorem due to Ovsiannikov [76], and corrected by Olver [69], states that if a group acts (locally) effectively on subsets, then its prolonged action will eventually become free.
Proposition 4.16
If a local Lie group of transformations G acts (locally ) effectively on subsets of M, then there exists ℓ 0 such that for all ℓ ≥ ℓ 0 , the prolonged action of G acts locally freely on an open dense subset \(\mathrm{V}^{(\ell)} \subset \mathop{\mathrm{J}}\nolimits ^{(\ell)}\) (or \(\mathcal{V}^{(\ell)} \subset \mathcal{J}^{(\ell)}\) ).
The discrete version of Proposition 4.16 was proved in [15].
Example 4.17
We now implement the moving frame construction for the projective action (35) on the order three submanifold jet space
We must therefore compute the prolonged action up to the third derivative. Since the independent variable x is an invariant of the action (35), the implicit derivative operator (26) is
and the prolonged action, up to order 3, is
Assuming u x ≠ 0, we construct a moving frame by choosing the cross-section
Solving the normalization equations
for the group parameters and using the unitary constraint ad − bc = 1, we obtain the right moving frame
Invariantizing εu xxx , we obtain the Schwarzian derivative
Exercise 4.18
Referring to Exercise 4.5:
-
1.
Find the one-parameter group action induced by each of the infinitesimal generators (37).
-
2.
Construct a moving frame on \(\mathop{\mathrm{J}}\nolimits ^{(1)} =\{ (t,x,u,u_{t},u_{x})\}\).
-
3.
Compute the normalized invariant ι(u xx ).
Example 4.19
We now reconsider Example 4.4 using the method of moving frames. The product action on \(\mathcal{J}^{[3]}\) is
In the following, we let
Then, a cross-section to the group orbits is given by
where we let u i tend to infinity. Solving the normalization equations
we obtain the right moving frame
where
Invariantizing ε i u i+2 we obtain the same difference invariant as in (61):
The latter could also be derived from the replacement principle. Invariantizing (61) we find that
5 Weakly Invariant Equations
As observed in Remark 4.2, the notion of an invariant function is more restrictive than that of an invariant equation. This brings us to distinguish two types of invariant equations.
Definition 5.1
An equation F(z) = 0 is said to be weakly invariant if it is invariant only on its solution space. That is
and the action is defined. An equation F(z) = 0 is said to be strongly invariant if the function \(F: \mathcal{M}\rightarrow \mathbb{R}\) is G-invariant. That is,
where the action is defined.
Remark 5.2
We note that a weakly invariant equation can, sometimes, be made strongly invariant by appropriately multiplying the equation by a certain relative invariant. We recall that a relative invariant of weight μ is a function R(z) which satisfies R(g ⋅ z) = μ(g, z)R(z). Indeed, if a weakly invariant equation F(z) = 0 is such that F(g ⋅ z) = μ(g, z)F(z), with μ(g, z) ≠ 0, then multiplying the equation by a relative invariant R(z) ≠ 0 of weight 1∕μ yields the strongly invariant equation R(z)F(z) = 0.
As a simple example, let \(\mathcal{M} = \mathcal{J}^{[1]} =\{ (i,x_{i},x_{i+1},u_{i},u_{i+1})\}\), and consider the product action
where λ > 0 and \(a,b \in \mathbb{R}\). Then the equation
is weakly invariant as g ⋅ u i+1 − g ⋅ u i = λ(u i+1 − u i ). Dividing Eq. (69) by the relative invariant h i = x i+1 − x i , one obtains the equivalent strongly invariant equation
We now explain how to systematically search for weakly invariant equations. As always, we assume that G is an r-dimensional Lie group acting locally on a d-dimensional manifold \(\mathcal{M}\).
5.1 Lie’s Infinitesimal Approach
A weakly invariant equation is found by searching for a submanifold \(\mathcal{S}\subset \mathcal{M}\), defined as the zero locus of an equation W(z) = 0, where the isotropy group is nontrivial. To find such a submanifold we consider a basis of infinitesimal generators (52) and introduce the corresponding Lie matrix.
Definition 5.3
The Lie matrix is the r × d matrix whose components are given by the coefficients of the infinitesimal generators (52):
Proposition 5.4
The dimension of the group orbit through \(z \in \mathcal{M}\) is equal to the rank of the Lie matrix L(z).
Proposition 5.5
Let 0 ≤ k ≤ r. The set of points
is invariant under the action of G. The number of functionally independent invariants on \(\mathcal{S}_{k}\) is given by the formula
The sets of points \(\mathcal{S}_{k}\) where the rank of the Lie matrix L is not maximal, i.e. rank L < r, are described by equations of the form W(z) = 0. By Proposition 5.5, these equations are weakly invariant. Therefore, weakly invariant equations are found by searching for submanifolds where the rank of the Lie matrix is not maximal.
Example 5.6
To illustrate the above considerations, we consider the Lie algebra of vector fields
and search for weakly invariant equations on the discrete jet space
The prolongation of the infinitesimal generators (71) to \(\mathcal{J}^{[2]}\) is given by
and the corresponding Lie matrix is
Assuming that h i = x i+1 − x i ≠ 0 and h i−1 = x i − x i−1 ≠ 0, the Lie matrix can be row reduced to
where W = h i−1(u i+1 − u i ) − h i (u i − u i−1). Therefore, when
the rank of the Lie matrix is not maximal and (73) yields a weakly invariant equation.
5.2 Moving Frame Approach
As explained in Sect. 4.2, a moving frame \(\rho: \mathcal{M}\rightarrow G\) exists provided the group action is free. In terms of the Lie matrix (70), this occurs where the rank of L(z) = r = dimG is maximal. Therefore, submanifolds where the rank of the Lie matrix is not maximal occur where a moving frame does not exist. In those situations it is still possible to construct partial moving frames [72, 75, 84]. Intuitively, a partial moving frame is the G-equivariant map that one obtains when some of the group parameters cannot be normalized during the normalization procedure. Given a partial moving frame, the invariantization map is still defined as in (65), and a complete set of normalized difference invariants can still be constructed.
In applications, partial moving frames naturally occur as one attempts to solve the normalizing equations (64). The solution to the normalization equations will, in general, require some nondegeneracy conditions to hold and submanifolds where those constraints are not satisfied will determine weakly invariant equations.
Example 5.7
We now reconsider Example 5.6 using the equivariant moving frame method. The group of transformations induced by the infinitesimal generators is given by
where λ > 0, α > 0, and \(a,b,\beta \in \mathbb{R}\). The product action on the discrete jet space (72) is
Starting the normalization process, we first set X i = 0 and U i = 0. Solving the normalization equations
we obtain
Introducing the notation
the substitution of the group normalizations (75) into the product action (74) yields
At this stage, assuming that h i−1 > 0 (and similarly h i > 0) we can set X i−1 = −1, which leads to the group normalization
Substituting (77) into (76) yields the difference invariant
To normalize the remaining group parameters α and β in
it is necessary for the coefficient matrix to be invertible. On the other hand, if the matrix is not invertible, that is, if
one can only construct a partial moving frame and (78) is a weakly invariant equation, which is identical to (73). When (78) holds, we can normalize either U i+1 or U i−1. Let U i−1 = 0, then
and one obtains the partial moving frame
Finally, we note that
by virtue of (78).
6 Symmetry-Preserving Numerical Schemes
At this point, given a Lie group of local transformations G acting on \(\mathcal{M}\), we have everything needed to construct G-invariant equations. As introduced in Sect. 5, a G-invariant equation F(z) = 0 will either be weakly invariant or strongly invariant. To obtain strongly invariant equations, the first step consists of computing a complete set of invariants I c using either Lie’s infinitesimal approach or the moving frame method. Once a complete set of invariants I c has been computed, a strongly invariant equation \(0 = F(z) =\widetilde{ F}(\mathbf{I}_{c})\) is simply obtained by combining invariants from I c . To obtain weakly invariant equations, one simply has to use one of the two procedures outlined in Sect. 5.
When \(\mathcal{M} =\mathop{ \mathrm{J}}\nolimits ^{(\ell)}\), the above procedure will produce all the differential equations \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\) admitting G as a symmetry group. Similarly, when \(\mathcal{M} = \mathcal{J}^{(\ell)}\), one obtains all the differential equations \(\bar{\varDelta }{\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} = 0\) invariant under the prolonged action of G. Obtaining these differential equations is referred to as the inverse problem of group classification. Given a G-invariant differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\), the procedure can also be used to construct an extended system of equations \(\{\bar{\varDelta }{\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} = 0,\tilde{\varDelta }{\bigl (s,x^{(\ell)},u^{(\ell)}\bigr )} = 0\}\) that is G-compatible with \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\).
In the following, we are mainly interested in the case when \(\mathcal{M} = \mathcal{J}^{[\ell]}\). Given a differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\) with symmetry group G, we want to construct a system of finite difference equations that approximates the differential equation, specifies constraints on the mesh, and preserves the symmetry group G. This is now obviously done by finding an appropriate collection of strongly invariant and weakly invariant difference equations, which, in the continuous limit, converge to the differential equation. To find an approximation of the differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\), the first step consists of computing a complete set of difference invariants using either Lie’s infinitesimal approach or the moving frame method and to consider their Taylor expansion. Then one searches for a combination of these Taylor expansions that will, in the continuous limit, converge to the differential equation, and thereby provide a finite difference approximation of the equation. This step will not always work. It is possible that the difference invariants cannot be combined in such a way to converge to the differential equation in the continuous limit. When this is the case, one should search for a weakly invariant equation W(x N [ℓ], u N [ℓ]) = 0 that converges to Δ = 0. If the later fails, one can try to add more points in the lattice. It is not clear yet if all invariant differential equations admit at least one symmetry-preserving scheme. Differential equations with infinite-dimensional symmetry groups are particularly challenging. To this day, no one has been able to systematically construct symmetry-preserving schemes for such equations.
In parallel, one also searches for a set of strongly and/or weakly invariant difference equations that will constrain the mesh on which the differential equation is approximated. Mesh equations do not always have to be included. If they are avoided, this leads to invariant meshless discretization schemes [4], which tend to be more complicated numerical schemes as they can operate on an arbitrary collection of nodes where the solution is sought numerically. When, included, the mesh equations will influence how the continuous limit should be taken in the above paragraph. The number of equations specifying the mesh is not a priori fixed. The only requirements are that those equations should not impose any constraints on the dependent variables u N [ℓ], that they should be compatible, and have the appropriate continuous limit. The latter can mean different things depending on the point of view used. For example, in [13, 14, 18, 28–30, 56, 61], the discrete indices N + K are assumed to be fixed and in the continuous limit, the points (x N+K , u N+K ) converge to (x N , u N ) for all \(K \in \mathbb{Z}^{p}\). With this perspective, the mesh equations will converge, in the continuous limit, to identities such as 0 = 0. Alternatively, if one regards the discrete index N = (n 1, …, n p) as sampling the computational variables s = (s 1, …, s p), one can take the limit in the index variables [67, 78, 79]. To this end, we introduce the variation parameters ε = (ε 1, …, ε p) ∈ [0, 1]p. One can then write the multi-index N + K as
Letting ε → 0+, one has that
By introducing the variation parameters ε = (ε 1, …, ε p) in the mesh equations and letting ε → 0+, the latter will now converge to the companion equations (9b).
We now illustrate the above procedure for constructing symmetry-preserving numerical schemes by considering three examples.
Example 6.1
As our first example, we construct a symmetry-preserving scheme for the Schwarzian differential equation (33), whose symmetry group is given by the fractional linear action (35). The difference invariants on the lattice (56) are given by the index i, the discrete x-variables (58), and the cross-ratio (61). These invariants are sufficient to construct a symmetry-preserving scheme of the Schwarzian equation. We begin by specifying the mesh equation, as this step is the easiest. Clearly, we can set
where h > 0 is a positive constant. From the mesh equation, it follows that
Therefore, the Taylor expansions of u i−1, u i+1, and u i+2 centered at x i are
where the function u and its derivatives are evaluated at x i . Substituting the Taylor expansions (79) in the difference invariant (61), we obtain
Therefore,
and an invariant approximation of the Schwarzian equation (33) is given by
Example 6.2
As a second example, we consider the second order ordinary differential equation
As seen in Exercise 3.6, the infinitesimal symmetry algebra is spanned by the vector fields (32). In the following, we construct a symmetry-preserving scheme of the differential equation (81) invariant under the five-dimensional symmetry subgroup generated by (71) on the discrete jet space \(\mathcal{J}^{[2]} =\{ (i,x_{i-1},x_{i},x_{i+1},u_{i-1},u_{i},u_{i+1})\}.\) Since \(\dim \mathcal{J}^{[2]} -\dim \mathfrak{g} = 7 - 5 = 2\), other than the index i, we expect one more difference invariant. Solving the system of first order partial differential equations
we obtain the invariant
Note that this invariant was also found in our construction of a partial moving frame in Example 5.7. Clearly, it is not possible to approximate (81) using only the invariant (82). We therefore search for weakly invariant equations. In Example 5.6 (and Example 5.7) we found that W = h i−1(u i+1 − u i ) − h i (u i − u i−1) = 0 is a weakly invariant equation. Since the product of a weakly invariant equation W(x i [2], u i [2]) = 0 by a nonzero difference function F(i, x i [2], u i [2]) ≠ 0 remains weakly invariant,
is weakly invariant equation, and happens to approximate the differential equation u xx = 0. As for the mesh equation, we set H i = f(i), with f(i) > 0 for all i, and obtain
Exercise 6.3 (This Exercise Was Taken from [81])
The first-order ordinary differential equation
is invariant under the infinitesimal symmetry generators
Working on the discrete jet space
-
1.
Show that, other than the index i, the only two invariants are x i and x i+1.
-
2.
Find a weakly invariant difference equation.
-
3.
Write down a symmetry-preserving scheme for (83).
Example 6.4
The standard discretization of the KdV equation on an orthogonal mesh given in (22) is not invariant under the Galilean boosts
Indeed, under this transformation, the second term in (22) is transformed to
while the other two terms remain unchanged. Thus, the discretization (22) does not preserve all the symmetries of the equation. It is not difficult to see that the discretization (22) is only invariant under shifts and dilations.
We now proceed to the construction of a symmetry-preserving scheme for the KdV equation. Introducing the multi-index N = (n, i), let
as in Example 2.17. Recall that the symmetry generators of the KdV equation were found in (31). Clearly, the ratios
are invariant under space and time translations, Galilean boosts, and scalings. Therefore, we can use these two invariants to fix invariant constraints on the discretization of the time variable t by setting \(\frac{t_{i+1}^{n}-t_{ i}^{n}} {t_{i}^{n+1}-t_{i}^{n}} = 0\) and \(\frac{t_{i}^{n+1}-t_{ i}^{n}} {t_{i}^{n}-t_{i}^{n-1}} = 1\). These two equations are equivalent to
The latter imply that a symmetry-preserving scheme for the KdV equation can be formulated on a mesh with flat, equally spaced time layers:
From here on, we assume that (84) hold. The prolongation of the vector fields (31) to the points in the stencil depicted in Fig. 1 is given by
Stencil for the KdV equation
To simplify the notation, we introduce
for the spacings and elementary first order discrete x-derivatives. Applying the infinitesimal invariance criterion (53) and solving the corresponding system of first order partial differential equations, we obtain the following 18 functionally independent invariants
Introducing the invariant quantity
an invariant numerical scheme for the KdV equation (together with the mesh equations (84)) is given by
Introducing the third order discrete x-derivative
the explicit expression of the invariant scheme (88) is
A more appropriate invariant numerical scheme can be realized on the entire ten point lattice. The latter is given by
Explicitly,
To use the scheme (90) or (91), the grid velocity
must be specified in an invariant manner to preserve the symmetries of the KdV equation. One possibility is to set
Together, the Eqs. (84), (90) (or (91)), and (92) provide a numerical approximation of the extended system of differential equations (11), (14), (15) for the KdV equation. The latter scheme can perform poorly as there is no built-in mechanism preventing the clustering of grid points as the numerical integration proceeds. Alternatives to using (92) to obtain the position of the grid points at the next time level will be presented in Sect. 7. Using adaptive moving mesh methods, we will construct more reliable invariant numerical schemes.
We conclude this example by discussing the continuous limit of the numerical scheme (90) with mesh equations (84), (92). Let us introduce the variation parameters (ε, δ) so that
In the numerical scheme (90), (84), (92), let
with ε = 1 and δ = 1, and similarly for the differences in t and x. Then, as ε → 0 and δ → 0,
and the numerical scheme (90), (84), (92), converges to (15), (11), and (14), respectively.
Alternatively, if one lets t i+j n+l → t i n, x i+j n+l → x i n, u i+j n+l → u i n, without introducing the variation parameters (ε, δ), then after multiplying equation (92) by k, the mesh equations (84), (92) converge to the identity 0 = 0, while (90) converges to the original KdV equation (10).
Exercise 6.5
Using the difference invariants computed in Exercise 4.5 part 2, construct a symmetry-preserving scheme for Burgers’ equation (36).
When using the method of equivariant moving frames to construct symmetry-preserving numerical schemes, it is possible to avoid the step where one has to search for a combination of the difference invariants that will approximate the differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\). In general, for this to be the case, some care needs to be taken when constructing the discrete moving frame \(\rho ^{[\ell]}: \mathcal{J}^{[\ell]} \rightarrow G\). The latter has to be compatible with a continuous moving frame \(\rho ^{(\ell)}: \mathop{\mathrm{J}}\nolimits ^{(\ell)} \rightarrow G\). By this, we mean that the discrete moving frame ρ [ℓ] must converge, in the continuous limit, to the moving frame ρ (ℓ). If \(\mathcal{K}^{[\ell]}\) is the cross-section used to define ρ [ℓ] and \(\mathcal{K}^{(\ell)}\) is the cross-section defining ρ (ℓ), then the moving frame ρ [ℓ] will be compatible with ρ (ℓ) if, in the coalescing limit, \(\mathcal{K}^{[\ell]}\) converges to \(\mathcal{K}^{(\ell)}\). As shown in [67], discrete compatible moving frames can be constructed by using the Lagrange interpolation coordinates on \(\mathcal{J}^{[\ell]}\), although in applications these can lead to complicated expressions that may limit the scope of the method. It is frequently preferable to fix invariant constraints on the mesh, and then consider finite difference approximations of the derivatives compatible with the mesh. On a nonuniform mesh, these expressions can be obtained by following the procedure of Example 2.11.
Given a compatible moving frame ρ [ℓ] an invariant approximation of the differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\) is simply obtained by invariantizing any finite difference approximation E(N, x N [ℓ], u N [ℓ]) = 0, compatible with the mesh. In particular, the equation E(N, x N [ℓ], u N [ℓ]) = 0 does not have to be invariant.
We now illustrate the construction of symmetry-preserving numerical schemes using the method of moving frames.
Example 6.6
As our first example, we revisit Example 6.1 using the moving frame machinery. In Example 4.19, we constructed a discrete moving frame for the symmetry group of the Schwarzian differential equation. This moving frame was constructed using the cross-section (68), which is not compatible with the cross-section (66) used to define a moving frame in the differential case. Indeed, in (66) we have u = 0, while in the discrete case we let u i → ∞. Therefore, one should not expect that the invariantization of the standard scheme
will provide an invariant approximation of the Schwarzian equation (33). Indeed, the invariantization of (93), yields the inconsistent equation
In this case one has to combine the normalized invariants x i−1, x i , x i+1, x i+2, and the cross-ratio ε i ι(u i+2) = R i as in Example 6.1 to obtain the invariant numerical scheme (80).
For the invariantization of (93) to give a meaningful invariant discretization, we need to construct a discrete moving frame compatible with (67). Working on the uniform mesh
we introduce the finite difference derivatives
To obtain a compatible discrete moving frame, we consider a finite difference approximation of the cross-section (66) used in the differential case. Namely, let
The latter is equivalent to
Solving the normalization equations
and using the unitary constraint ad − bc = 1, we obtain the moving frame
where
We note that the right-hand side of the last equality is nonnegative by definition of ε i . Invariantizing the noninvariant scheme (93), we obtain the invariant discretization
The latter can be written using cross-ratios in a form similar to the invariant scheme (80). After some simplifications, the invariant scheme (94) is equivalent to
where
Example 6.7
As our final example, we consider the invariant discretization of the KdV equation. The group action induced by the infinitesimal generators (31) is given by
where \(a,b,v \in \mathbb{R}\) and \(\lambda \in \mathbb{R}^{+}\). As in Example 6.4, to simplify the computations, we assume that (84) holds. When this is the case, it follows from (18) that
where we use the notation that was introduced in (86). For better numerical accuracy, we let
Also, recalling formula (89), we let
Implementing the discrete moving frame construction, we choose the cross-section
which is compatible with the cross-section {x = 0, t = 0, u = 0, u x = 1} that one could use to construct a moving frame in the continuous case. Solving the normalization equations
for the group parameters a, b, v, λ, we obtain the right moving frame
To obtain an invariant scheme, we approximate the KdV equation using (96) and (97),
and invariantize the resulting scheme. Since the latter is already invariant, the scheme remains the same. We note that the scheme (99) is the same as (90).
Exercise 6.8
Referring to Exercise 4.5:
-
1.
Construct a discrete moving frame on the stencil
$$\displaystyle{\bigl\{\bigr(n,i,t^{n},t^{n+1},x_{ i-1}^{n},x_{ i}^{n},x_{ i+1}^{n},x_{ i-1}^{n+1},x_{ i}^{n+1},x_{ i+1}^{n+1},u_{ i-1}^{n},u_{ i}^{n},u_{ i+1}^{n},u_{ i-1}^{n+1},u_{ i}^{n+1},u_{ i+1}^{n+1}\bigr)\bigr\}}$$compatible with the differential moving frame found in Exercise 4.18 part 2.
-
2.
Invariantize the discrete approximation
$$\displaystyle{u_{xx} \approx D^{2}u_{ i}^{n} = \frac{2} {h_{i}^{n} + h_{i-1}^{n}}[Du_{i}^{n} - Du_{ i-1}^{n}].}$$ -
3.
Write a symmetry-preserving scheme for Burgers’ equation (36).
7 Numerical Simulations
In this section we present some numerical simulations using the invariant numerical schemes derived in Sect. 6.
7.1 Schwarzian ODE
indexSchwarz’ equationWe begin with the Schwarzian ODE (33) with F(x) = 2. In other words, we consider the differential equation
By the Schwarz’ Theorem [64], the general solution of (100) is
Choosing a = d = 1 and b = c = 0, we obtain the particular solution u(x) = tanx. We now aim to obtain this particular solution numerically using the invariant scheme (80) and a standard noninvariant scheme, and compare the results. For the standard method, we choose the explicit fourth order adaptive Runge–Kutta solver ode45 as provided by Matlab. On the surface, this appears to be an unfair comparison since the invariant scheme (80) is only first order accurate. However, preserving geometric properties can give a numerical scheme a distinct advantage, even if it is only of relatively low order. This is verified in Fig. 2.
Numerical integration of the Schwarzian ODE (33) with F(x) = 2. Blue: Non-invariant fourth order adaptive RK method. Red: Invariant first order method. Black: Exact solution
The relative error tolerance controlling the step size in the (noninvariant) adaptive Runge–Kutta method was set to 10−12. Despite this extremely small tolerance, the numerical solution diverges at the point x = π∕2 where the solution has a vertical asymptote. On the other hand, the invariant method, with a step size of h = 0. 01, is able to integrate beyond this singularity and follows the exact solution u(x) = tanx very closely. For the conceptually related case where F(x) = sinx in (33), see [13].
7.2 Korteweg–de Vries Equation
As reviewed in the previous sections, the earliest examples of invariant numerical schemes for evolution equations almost exclusively rested on the discretization of their associated Lagrangian form. However, the use of fully Lagrangian techniques for discretizing differential equations is not common due to their tendency to cluster grid points in certain areas of the computational domain and to poorly resolve the remaining parts of the domain. Even more problematic, Lagrangian numerical methods regularly lead to mesh tangling, especially in the case of several space dimensions.
For the KdV equation this basic problem is readily demonstrated using the invariant Lagrangian scheme given by (91) and (92). To do so, we numerically implement this scheme using as initial condition a double soliton solution of the form
where \(c_{1},c_{2} \in \mathbb{R}\) are the phase velocities of the individual solitons and \(a_{1},a_{2} \in \mathbb{R}\) are the initial displacements. In our numerical simulations, we set a 1 = 20, a 2 = 5, c 1 = 1, c 2 = 0. 5, and restricted the computational domain to the interval [−30, 30] discretized with a total of N = 128 spatial grid points. The time step k was chosen to be proportional to h 3, k ∝ h 3, and the final integration time for the Lagrangian experiment was t = 0. 75. The result of the computation is presented in Fig. 3.
It is visible from the evolution of the mesh points in Fig. 3 (right) that mesh tangling (here: crossing of mesh lines) is about to occur. This leads to numerical instability that is visible as high wavenumber oscillations between the two solitons, which sets in almost immediately after the start of the numerical integration. In other words, the invariant Lagrangian scheme is unsuitable for practical applications in virtually all relevant numerical situations, since no inherent control over the evolution of the mesh points is build into the scheme.
It is striking to observe that, despite the well-known shortcomings of Lagrangian numerical schemes, the latter have played a prominent role in the field of symmetry-preserving discretization. This can be explained by the fact that for most papers on the subject, invariant numerical schemes were constructed more as an example highlighting the possibility of deriving symmetry-preserving schemes of differential equations rather than as a tool for practical numerical experiments. Indeed, it is fair to say that even now, the numerical analysis of invariant discretization schemes is still lacking rigor.
In order to make the invariant numerical scheme (91) practical, a different invariant grid equation has to be derived. Possible strategies include the use of invariant evolution–projection schemes and invariant adaptive numerical schemes.
The invariant evolution–projection scheme conceptually builds upon the invariant Lagrangian scheme. The main idea of this approach is to use the invariant numerical scheme and the invariant mesh equations only over a single time step, and use an interpolation scheme to project the solution of the differential equation defined at the new spatial grid points back to the initial (typically uniform) spatial grid. The entire procedure is invariant if the interpolation scheme used is invariant [5]. The main appeal of this method is that it enables the use of invariant numerical schemes on rectangular meshes.
It is readily verified that classical interpolation methods such as linear, quadratic, cubic or spline interpolations are all invariant under the maximal symmetry group of the KdV equation. The main reason is that all these schemes are polynomials in terms like (x i+1 n+1 − x i n+1) or \((\hat{x}^{n+1} - x_{i}^{n+1})/(x_{i+1}^{n+1} - x_{i}^{n+1})\), where \(\hat{x}^{n+1}\) is the interpolation point, which are invariant under spatial and temporal shifts and Galilean boosts. The invariance under scaling transformations follows from the consistency of the interpolation scheme. For example, consider the linear interpolation given by
Then, under the action of the KdV symmetry group given by (95), the linear interpolation formula remains invariant. In other words, it follows that
For more details and examples, see [5, 6].
In Fig. 4 we present the numerical results for the scheme (91), (92) using the double soliton (101) as initial condition on the interval [−30, 30]. As opposed to the previous simulation, we now introduce a cubic spline interpolation at each time integration to project the solution back to the original space grid. The number of discrete spatial points is as before, that is N = 128, and the final integration time is t = 40. As it can be seen, the two solitons interact with each other and remain unchanged after their collision, which is properly captured by the invariant evolution–projection scheme. We point out though that the scheme is rather dissipative, with the amplitudes of the solitons slowly decreasing over time. While in the present example dissipation can be seen as a disadvantage, this dissipation can be essential in hyperbolic problems that involve shock solutions. For these shock solutions, numerical simulations usually require schemes, such as upwind or Lax–Friedrich and Lax–Wendroff methods, which exhibit artificial dissipation.
A second possibility for completing the invariant numerical scheme (91) without using Lagrangian methods rests on moving mesh methods. Without going into great details, we present here an invariant r-adaptive scheme for the KdV equation (for more information, see [9]). In r-adaptive numerical schemes a fixed number of grid points is redistributed so that points automatically move to regions where higher resolution is required, for example near shocks. Therefore, r-adaptive numerical methods are particularly important for hyperbolic problems. We refer to [39] for a comprehensive review of such methods.
For one-dimensional problems, r-adaptive moving meshes on the interval [a, b] are uniquely determined through the equidistribution principle, which in differential form reads
with boundary conditions x(t, 0) = a and x(t, 1) = b. In (102), the function δ is called the mesh density function or monitor function. Its role is to control the areas where grid points should concentrate or de-concentrate. It is typically linked to the solution of the physical differential equation. For example, the arc-length type mesh density function is
where \(\alpha \in \mathbb{R}\) is a constant adaptation parameter.
To complete the invariant scheme for the KdV equation, we discretize (102) and (103) using the difference invariants given in (87) or using the invariantization map induced by the discrete moving frame (98). In particular, it turns out that the straightforward discretization
is invariant under the maximal Lie symmetry group of the KdV equation.
In Fig. 5 we present the numerical solution for the KdV equation using the invariant adaptive scheme (91) with (104) and the same double soliton initial condition (101) as in the previous simulation. The final integration time was again chosen to be t = 40 and the adaptation parameter was set to α = 10.
It is readily seen from Fig. 5 that the invariant adaptive scheme (91), (104) again does not suffer from the shortcomings observed for the Lagrangian scheme (91), (92). In particular, no mesh tangling occurs. The associated adaptive mesh suitably tracks the position of the solitons and remains almost uniform away from the two waves, although the adaptation is relatively weak since the solution does not exhibiting overly steep gradients. An advantage of the invariant r-adaptive scheme over the invariant evolution–projection scheme is that the amplitudes of the solitons are not damped during the adaptation strategy.
In general, using invariant adaptive schemes has the merit of combining a geometric numerical method with a well-proven numerical strategy for dynamically redistributing the points in a mesh. In particular, this technique works for all evolution equations that are invariant under the Galilean group, which are virtually all equations of classical hydrodynamics, including the shallow-water equations, the Euler equations and the Navier–Stokes equations. Since shock waves are physically important solutions in these models, invariant adaptive schemes are of high practical relevance in this field.
7.3 Burgers’ Equation
In this section we construct a new numerical scheme for Burgers’ equation (36) invariant under the four-parameter symmetry group
generated by the vector fields v 1, v 2, v 3, v 4 given in (37). We exclude the one-parameter group of transformations generated by v 5 since in numerical simulations the evolution of the time variable t should always be strictly increasing, and allowing the inversion transformations generated by v 5 would enable one to reverse the time direction, which is not desirable from a numerical standpoint.
Remark 7.1
As an exercise, the reader is invited to adapt the constructions below by including the inversion transformations generated by v 5. This has never been attempted and could potentially lead to interesting new results!
Due to the similarities between the symmetry subgroup action (105) and the KdV symmetry group (31), the underlying symmetry-preserving schemes for Burgers’ equation are conceptually similar to the invariant schemes constructed before for the KdV equation. Though, one important differences between the two equations is that solutions to Burgers’ equation can develop very steep gradients (although remaining smooth for all times provided that ν ≠ 0). This is particularly the case if ν approaches zero. Hence, grid adaptation is of practical relevance for this equation.
In [49], an invariantization for the Crank–Nicolson scheme for Burgers’ equation was proposed. However, we note that the Crank–Nicolson scheme is implicit and thus in the case where ν is small it might not be the most efficient way of solving Burgers’ equation since an explicit scheme should then suffice. In the following, we propose a new scheme which draws some ideas from high-resolution finite volume methods [52]. It is well-known that high order schemes, such as the Lax–Wendroff method, lead to oscillations in the numerical solution near shocks, whereas low order schemes, such as the upwind method, develop no such oscillations but exhibit an excessive amount of numerical viscosity. The idea in the high-resolution method is thus to use a high order method away from the shock and a low resolution method near the shock. The transition between the two regions is accomplished through the use of flux /slope limiters.
To formulate an indexinvariant finite volume schemeinvariant finite volume type method for Burgers’ equation, we rewrite (36) in the form
We now discretize (106) on a moving mesh, which, as we have previously seen, is enough to guarantee invariance under Galilean transformations. As in Examples 2.8 and 2.10, we introduce the computational variables (τ, s) and let t = t(τ) = kτ + t 0 and x = x(τ, s). Then, a suitable conservative form of Burgers’ equation in the computational variables (τ, s) is given by
see also [39]. We then discretize the flux f in two different ways, once using the second order centered difference method (high resolution) and once using the first order upwind method (low resolution). In doing so, we observe, as in [9], that the invariance under Galilean transformations requires us to discretize (107) in such a way that all spatial derivatives are evaluated using the same finite difference discretizations. With that said, the high order discretization of (107) is Δ τ (x s u)high + k Δ s f high = 0, with
On the other hand, the low order discretization of (107) is Δ τ (x s u)low + k Δ s f low = 0, where
and
with
The invariant high-resolution method is obtained by dynamically selecting the regions of the domain where the high order and low order methods are used. For this purpose, we introduce the ratio
and I = i − 1 if u i n ≥ 0 and I = i + 1 if u i n < 0. Geometrically, the quantity θ i n measures the smoothness of the solution over the interval [x i−1, x i ]. This ratio is, by its definition, invariant under the symmetry subgroup (105), and therefore so is any function of θ i n.
We proceed to discretize (107) by considering
with
and where, for the flux limiter function Φ(θ i n), we choose the so-called minmod-limiter, Φ(θ i n) = max{0, min(1, θ i n)}. For further discussions on flux limiters, see [52]. To complete the invariant finite volume type scheme for Burgers’ equation, we use the same grid adaptation strategy as for the KdV equation to obtain the spatial step size σ i n = x i n+1 − x i n as time evolves.
As a numerical example, we carry out an experiment similar to the one given in [49] for the exact solution
where \(c \in \mathbb{R}\). We discretize the spatial domain [−0. 5, 0. 5] with N = 128 grid points using Dirichlet boundary conditions, and choose the time step k to be proportional to h 2, k ∝ h 2. The final integration time is t = 0. 5 and for numerical purposes c = 0. 25 and the viscosity was set to ν = 0. 001. The adaptation parameter α in the arc-length type mesh density function in (104) was set to α = 0. 5. The respective numerical results are depicted in Fig. 6.
Unlike in the numerical simulations for the KdV equation presented in Sect. 7.2, Fig. 6 clearly demonstrates the need for an adaptive moving mesh. While this is implied from the structure of the numerical solution, it is remarkable that the requirement for a moving mesh is already encoded in the structure of the symmetry group of Burgers’ equation. Hence, numerically preserving symmetries can be seen as a geometrical justification for using r-adaptive numerical methods. Moreover, due to the use of a high-resolution finite volume type scheme, no unphysical oscillations around the shock is observed.
8 Conclusion
To recapitulate, let us summarize the algorithm for constructing symmetry-preserving finite difference schemes. Given a differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\):
-
1.
Use the infinitesimal invariance criterion (28) to determine a basis of infinitesimal symmetry generators.
-
2.
Choose a lattice on which the differential equation is to be discretized.
-
3.
When possible, in particular when discretizing a partial differential equation, impose obvious invariant constraints on the mesh. This step is not necessary but if implemented it can, in general, simplify the implementation of the remaining steps.
-
4.
Use either Lie’s infinitesimal approach or the moving frame method to compute a complete set of difference invariants, and, if necessary, to find weakly invariant difference equations. When using the moving frame method, one has to exponentiate the infinitesimal generators found in Step 1 to obtain the connected component of the group of local symmetry transformations.
-
5.
Combine the difference invariants and the weakly invariant equations in such a way to obtain an approximation of the differential equation \(\varDelta {\bigl (x,u^{(\ell)}\bigr )} = 0\) and (possibly) constraints on the mesh. If using the moving frame method, invariantize a finite difference approximation of the differential equation compatible with the mesh to obtain an invariant approximation of the differential equation.
The basic algorithm for constructing symmetry-preserving numerical schemes is now fairly well-understood. Below are some open problems and comments for the interested reader.
-
Many important differential equations in mathematical physics admit an infinite-dimensional symmetry group. Such equations include the Davey–Stewartson equations [20], Liouville’s equation, the Kadomtsev–Petviashvili equation [22], the Infeld–Rowland equation [32], the Euler equations [68], and many other equations from fluid dynamics [46]. Implementing the above algorithm for infinite-dimensional symmetry groups remains a challenge. One particularity of these groups is that as new points are added to the stencil, new group parameters appear, which does not occur in the finite-dimensional case. To avoid this difficulty, one possibility is to consider finite-dimensional subgroups of the infinite-dimensional symmetry group and implement the algorithm above [60, 61]. Another possibility, which preserves the infinite-dimensional nature of the group action, is to discretize the Lie pseudo-group action [79].
-
In the last 25 years, a great deal of efforts has been devoted to constructing symmetry-preserving finite difference numerical schemes. With the emergence of finite element methods [80], and discrete exterior calculus [1], it would be interesting to extend the above symmetry-preserving algorithm to these settings as well. Further extensions to finite volume and spectral methods should also be considered.
-
As with any geometric integrator, one of the motivations for developing symmetry-preserving schemes is to obtain better long term numerical results. As we saw in Sect. 7, and as observed in the literature [13, 14, 18, 50], symmetry-preserving schemes for ordinary differential equations perform extremely well, particularly near singularities. For first order ordinary differential equation, it is even possible to construct symmetry-preserving schemes that will approximate exactly the solution of the original equation [81]. On the other hand, the numerical improvements for partial differential equations are not as clear [4, 9, 21, 49, 61, 78, 79]. In many cases, they tend to be comparable to standard schemes. Now that the theoretical foundations are on firm grounds, one of the main challenges in the field of symmetry-preserving schemes is to investigate the numerical properties of invariant schemes and understand why and when these schemes give better numerical results.
-
Most partial differential equations invariantly discretized to date have been evolutionary equations (such as the KdV and Burgers’ equations). Much more work, especially from the numerical side, has to be devoted to the invariant discretization of other types of partial differential equations, such as the wave equation, Laplace’s equation, and the sine-Gordon equation. In particular, constructing symmetry-preserving schemes compatible with given boundary conditions is an important avenue of research.
-
Symmetries are usually not the only geometric properties that a differential equation admits. Other, equally important properties such as a Hamiltonian structure or conservation laws might be present as well. Developing geometric integrators that will preserve more than just one geometric property at the time is an important research direction to pursue.
9 Answers to Selected Exercises
-
Exercise 4.5 , part 2: A complete set of difference invariants is given by the nine invariants
$$\displaystyle\begin{array}{rcl} & I_{1} = \frac{h_{i}^{n}} {h_{i-1}^{n}}\;,\quad I_{2} = \frac{h_{i}^{n+1}} {h_{i-1}^{n+1}} \;,\quad I_{3} = \frac{h_{i}^{n}h_{ i}^{n+1}} {k^{n}} \;,\quad I_{4} = h_{i}^{n}h_{i-1}^{n}(Du_{i}^{n} - Du_{i-1}^{n})\;,& {}\\ & I_{5} = h_{i}^{n+1}h_{i-1}^{n+1}(Du_{i}^{n+1} - Du_{i-1}^{n+1})\;,\quad I_{6} = h_{i}^{n}{\biggl ( \frac{\sigma _{i}^{n}} {k^{n}} - u_{i}^{n}\biggr )}\;, & {}\\ & I_{7} = h_{i}^{n+1}{\biggl ( \frac{\sigma _{i}^{n}} {k^{n}} - u_{i}^{n+1}\biggr )}\;,\quad I_{8} = (h_{i}^{n})^{2}{\biggl (Du_{i}^{n} + \frac{1} {k^{n}}\biggr )}\;, & {}\\ & I_{9} = (h_{i}^{n+1})^{2}{\biggl (Du_{i}^{n+1} - \frac{1} {k^{n}}\biggr )}\;, & {}\\ \end{array}$$where
$$\displaystyle{h_{i}^{n} = x_{ i+1}^{n} - x_{ i}^{n}\;,\quad k^{n} = t^{n+1} - t^{n},\qquad \sigma _{ i}^{n} = x_{ i}^{n+1} - x_{ i}^{n}\;,\quad Du_{ i}^{n} = \frac{u_{i+1}^{n} - u_{ i}^{n}} {h_{i}^{n}} \;.}$$ -
Exercise 4.18 , part 1: The one-parameter group actions are
$$\displaystyle\begin{array}{rcl} \exp [\epsilon _{1}\mathbf{v}_{1}] \cdot (t,x,u)& =& (x +\epsilon _{1},t,u), {}\\ \exp [\epsilon _{2}\mathbf{v}_{2}] \cdot (t,x,u)& =& (x,t +\epsilon _{2},u), {}\\ \exp [\epsilon _{3}\mathbf{v}_{3}] \cdot (t,x,u)& =& (x +\epsilon _{3}t,t,u +\epsilon _{3}), {}\\ \exp [\epsilon _{4}\mathbf{v}_{4}] \cdot (t,x,u)& =& (e^{\epsilon _{4}}x,e^{2\epsilon _{4}}t,e^{-\epsilon _{4}}u), {}\\ \exp [\epsilon _{5}\mathbf{v}_{5}] \cdot (t,x,u)& =& {\biggl ( \frac{x} {1 -\epsilon _{5}t}, \frac{t} {1 -\epsilon _{5}t},(1 -\epsilon _{5}t)u +\epsilon _{5}x\biggr )}. {}\\ \end{array}$$ -
Exercise 4.18 , part 2: Working on the open dense set \(\mathcal{V}^{(1)} =\{ (t,x,u,u_{t},u_{x}) \in \mathop{\mathrm{J}}\nolimits ^{(1)}\mid uu_{x} + u_{t}\neq 0\}\), the right moving frame corresponding to the cross-section
$$\displaystyle{\mathcal{K} =\{ t = 0,x = 0,u = 0,u_{x} = 0,u_{t} = 1\}}$$is
$$\displaystyle{\epsilon _{1} = -x\;,\quad \epsilon _{2} = -t\;,\quad \epsilon _{3} = -u\;,\quad e^{\epsilon _{4}} = (uu_{x} + u_{t})^{1/3}\;,\quad \epsilon _{5} = -u_{x}\;.}$$ -
Exercise 4.18 , part 3: The invariantization of u xx yields the differential invariant
$$\displaystyle{\iota (u_{xx}) = \frac{u_{xx}} {uu_{x} + u_{t}}\;.}$$ -
Exercise 6.3 , part 2: A weakly invariant equation is given by
$$\displaystyle{u_{i+1}\mathrm{e}^{-A(x_{i+1})} - u_{ i}\mathrm{e}^{-A(x_{i})} - B(x_{ i+1}) + B(x_{i}) = 0\;.}$$ -
Exercise 6.5 : Along with the equations (62), we can add the mesh equation I 6 = 0 (refer to the solution of Exercise 4.5, part 2). On this mesh, the differential equation can be approximated by
$$\displaystyle{-I_{7}I_{3} = \frac{2\nu I_{4}I_{1}I_{2}} {1 + I_{1}} \;.}$$Explicitly,
$$\displaystyle{\frac{h_{i}^{n+1}h_{i-1}^{n+1}} {h_{i}^{n}h_{i-1}^{n}} \cdot \frac{u_{i}^{n+1} - u_{i}^{n}} {k^{n}} =\nu D^{2}u_{ i}^{n}\;.}$$Using the mesh equation σ i n = k n u i n, we obtain the explicit scheme
$$\displaystyle{(1 + k^{n}Du_{ i}^{n})(1 + k^{n}Du_{ i-1}^{n}){\biggl (\frac{u_{i}^{n+1} - u_{ i}^{n}} {k^{n}} \biggr )} =\nu D^{2}u_{ i}^{n}}$$with t i+1 n = t i n and σ i n = k n u i n.
-
Exercise 6.8 , part 1: A compatible discrete cross-section is given by
$$\displaystyle{\mathcal{K} ={\biggl \{ t^{n} = 0,x_{ i}^{n} = 0,u_{ i}^{n} = 0, \frac{u_{i+1}^{n}} {x_{i+1}^{n}} + \frac{u_{i-1}^{n}} {x_{i-1}^{n}} = 0,u_{i}^{n+1} = t^{n+1}\biggr \}}\;.}$$The corresponding discrete moving frame is
$$\displaystyle\begin{array}{rcl} & \epsilon _{1} = -x_{i}^{n}\;,\quad \epsilon _{2} = -t^{n}\;,\quad \epsilon _{3} = -u_{i}^{n}\;, & {}\\ & \mathrm{e}^{\epsilon _{4}} = [(1 + k^{n}\varDelta _{x}u_{i}^{n})(\varDelta _{t}u_{i}^{n} + u_{i}^{n+1}\varDelta _{x}u_{i}^{n})]^{1/3}\;,\quad \epsilon _{5} = -\varDelta _{x}u_{i}^{n}\;,& {}\\ \end{array}$$where
$$\displaystyle{\varDelta _{x}u_{i}^{n} = \frac{Du_{i}^{n} + Du_{ i-1}^{n}} {2} \quad \text{and}\quad \varDelta _{t}u_{i}^{n} = \frac{u_{i}^{n+1} - u_{ i}^{n}} {k^{n}} - \frac{\sigma _{i}^{n}} {k^{n}} \cdot \varDelta _{x}u_{i}^{n}\;.}$$ -
Exercise 6.8 , part 2: The invariantization yields the finite difference invariant
$$\displaystyle{\iota (D^{2}u_{ i}^{n}) = \frac{D^{2}u_{ i}^{n}} {(1 + k^{n}\varDelta _{x}u_{i}^{n})(\varDelta _{t}u_{i}^{n} + u_{i}^{n+1}\varDelta _{x}u_{i}^{n})}\;.}$$ -
Exercise 6.8 , part 3: Invariantizing Δ t u i n + u i n Δ x u i n = νD 2 u i n we obtain the invariant scheme
$$\displaystyle{(1 + k^{n}\varDelta _{ x}u_{i}^{n})(\varDelta _{ t}u_{i}^{n} + u_{ i}^{n+1}\varDelta _{ x}u_{i}^{n}) =\nu D^{2}u_{ i}^{n}\;.}$$
References
D.N. Arnold, R.S. Falk, R. Winther, Finite element exterior calculus: from Hodge theory to numerical stability. Bull. Am. Math. Soc. (N.S.) 47(2), 281–354 (2010)
M.I. Bakirova, V.A. Dorodnitsyn, An invariant difference model for the equation u t = u xx + δulnu. Differ. Equ. 30(10), 1565–1570 (1994)
M.I. Bakirova, V.A. Dorodnitsyn, R.V. Kozlov, Symmetry-preserving difference schemes for some heat transfer equations. J. Phys. A 30(23), 8139–8155 (1997)
A. Bihlo, Invariant meshless discretization schemes. J. Phys. A 46(6), 062001 (2013)
A. Bihlo, J.-C. Nave, Invariant discretization schemes using evolution-projection techniques. SIGMA 9, Paper 052 (2013)
A. Bihlo, J.-C. Nave, Convecting reference frames and invariant numerical models. J. Comput. Phys. 272, 656–663 (2014)
A. Bihlo, R.O. Popovych, Invariant discretization schemes for the shallow-water equations. SIAM J. Sci. Comput. 34(6), B810–B839 (2012)
A. Bihlo, E. Dos Santos Cardoso-Bihlo, R.O. Popovych, Invariant parameterization and turbulence modeling on the beta-plane. Phys. D 269, 48–62 (2014)
A. Bihlo, X. Coiteux-Roy, P. Winternitz, The Korteweg–de Vries equation and its symmetry-preserving discretization. J. Phys. A 48(5), 055201 (2015)
A. Bihlo, E. Dos Santos Cardoso-Bihlo, R.O. Popovych, Algebraic method for finding equivalence groups. J. Phys. Conf. Ser. 621, 012001 (2015)
G.W. Bluman, S.C. Anco, Symmetry and Integration Methods for Differential Equations. Applied Mathematical Sciences, vol. 154 (Springer, New York, 2002)
G.W. Bluman, A.F. Cheviakov, S.C. Anco, Applications of Symmetry Methods to Partial Differential Equations. Applied Mathematical Sciences, vol. 168 (Springer, New York, 2010)
A. Bourlioux, C. Cyr-Gagnon, P. Winternitz, Difference schemes with point symmetries and their numerical tests. J. Phys. A 39(22), 6877–6896 (2006)
A. Bourlioux, R. Rebelo, P. Winternitz, Symmetry preserving discretization of \(\mathop{\mathrm{sl}}\nolimits (2, \mathbb{R})\) invariant equations. J. Nonlinear Math. Phys. 15(Suppl. 3), 362–372 (2008)
M. Boutin, On orbit dimensions under a simultaneous Lie group action on n copies of a manifold. J. Lie Theory 12(1), 191–203 (2002)
R.L. Bryant, S.S. Chern, R.B. Gardner, H.L. Goldschmidt, P.A. Griffiths, Exterior Differential Systems. Mathematical Sciences Research Institute Publications, vol. 18 (Springer, New York, 1991)
C. Budd, V. Dorodnitsyn, Symmetry-adapted moving mesh schemes for the nonlinear Schrödinger equation. J. Phys. A 34(48), 10387–10400 (2001)
R. Campoamor-Stursberg, M.A. Rodríguez, P. Winternitz, Symmetry preserving discretization of ordinary differential equations. Large symmetry groups and higher order equations. J. Phys. A 49(3), 035201 (2016)
J. Carminati, K. Vu, Symbolic computation and differential equations: Lie symmetries. J. Symb. Comput. 29(1), 95–116 (2000)
B. Champagne, P. Winternitz, On the infinite-dimensional symmetry group of the Davey–Stewartson equations. J. Math. Phys. 29(1), 1–8 (1988)
M. Chhay, A. Hamdouni, Lie symmetry preservation by finite difference schemes for the Burgers equation. Symmetry 2(2), 868–883 (2010)
D. David, N. Kamran, D. Levi, P. Winternitz, Symmetry reduction for the Kadomtsev–Petviashvili equation using a loop algebra. J. Math. Phys. 27(5), 1225–1237 (1986)
V.A. Dorodnitsyn, Transformation groups in net spaces. J. Sov. Math. 55(1), 1490–1517 (1991)
V. Dorodnitsyn, Noether-type theorems for difference equations. Appl. Numer. Math. 39(3–4), 307–321 (2001)
V. Dorodnitsyn, Applications of Lie Groups to Difference Equations. Differential and Integral Equations and Their Applications, vol. 8 (CRC Press, Boca Raton, 2011)
V. Dorodnitsyn, R. Kozlov, A heat transfer with a source: the complete set of invariant difference schemes. J. Nonlinear Math. Phys. 10(1), 16–50 (2003)
V. Dorodnitsyn, P. Winternitz, Lie point symmetry preserving discretizations for variable coefficient Korteweg–de Vries equations. Nonlinear Dyn. 22(1), 49–59 (2000)
V. Dorodnitsyn, R. Kozlov, P. Winternitz, Lie group classification of second-order ordinary difference equations. J. Math. Phys. 41(1), 480–504 (2000)
V. Dorodnitsyn, R. Kozlov, P. Winternitz, Symmetries, Lagrangian formalism and integration of second order ordinary difference equations. J. Nonlinear Math. Phys. 10(Suppl. 2), 41–56 (2003)
V. Dorodnitsyn, R. Kozlov, P. Winternitz, Continuous symmetries of Lagrangians and exact solutions of discrete equations. J. Math. Phys. 45(1), 336–359 (2004)
S. Elaydi, An Introduction to Difference Equations, 3rd edn. Undergraduate Texts in Mathematics (Springer, New York, 2005)
M. Faucher, P. Winternitz, Symmetry analysis of the Infeld–Rowlands equation. Phys. Rev. E (3) 48(4), 3066–3071 (1993)
M. Fels, P.J. Olver, Moving coframes. II. Regularization and theoretical foundations. Acta Appl. Math. 55(2), 127–208 (1999)
R.B. Gardner, The Method of Equivalence and Its Applications. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 58 (SIAM, Philadelphia, 1989)
H.W. Guggenheimer, Differential Geometry. Dover Books on Advanced Mathematics (Dover, New York, 1977)
E. Hairer, C. Lubich, G. Wanner, Geometric Numerical Integration, 2nd edn. Springer Series in Computational Mathematics, vol. 31 (Springer, Berlin, 2006)
R. Hernández Heredero, D. Levi, P. Winternitz, Symmetry preserving discretization of the Burgers equation, in SIDE III—Symmetries and Integrability of Difference Equations, ed. by D. Levi, O. Ragnisco, vol. 25, CRM Proceedings & Lecture Notes (American Mathematical Society, Providence, 2000), pp.197–208
R. Hirota, Nonlinear partial difference equations. I. A difference analogue of the Korteweg–de Vries equation. J. Phys. Soc. Jpn. 43(4), 1424–1433 (1977)
W. Huang, R.D. Russell, Adaptive Moving Mesh Methods. Applied Mathematical Sciences, vol. 174 (Springer, New York, 2011)
P.E. Hydon, Discrete point symmetries of ordinary differential equations. R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 454(1975), 1961–1972 (1998)
P.E. Hydon, How to construct the discrete symmetries of partial differential equations. Eur. J. Appl. Math. 11(5), 515–527 (2000)
P.E. Hydon, Symmetries and first integrals of ordinary difference equations. R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 456(2004), 2835–2855 (2000)
P.E. Hydon, Symmetry Methods for Differential Equations. Cambridge Texts in Applied Mathematics (Cambridge University Press, Cambridge, 2000)
P.E. Hydon, Difference Equations by Differential Equation Methods. Cambridge Monographs on Applied and Computational Mathematics, vol. 27 (Cambridge University Press, Cambridge, 2014)
P.E. Hydon, E.L. Mansfield, Extensions of Noether’s second theorem: from continuous to discrete systems. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 467(2135), 3206–3221 (2011)
N.H. Ibragimov, R.N. Ibragimov, Applications of Lie Group Analysis in Geophysical Fluid Dynamics. Ser. Complex Nonlinearity Chaos, vol. 2. (World Scientific Publishing, Singapore, 2011)
N. Kamran, Contributions to the study of the equivalence problem of Élie Cartan and its applications to partial and ordinary differential equations. Acad. Roy. Belg. Cl. Sci. Mém. Collect. 8o (2) 45(7) (1989)
J.P. Kenney, Evolution of differential invariant signatures and applications to shape recognition. Ph.D. Thesis, University of Minnesota (2009)
P. Kim, Invariantization of the Crank–Nicolson method for Burgers’ equation. Phys. D 237(2), 243–254 (2008)
P. Kim, P.J. Olver, Geometric integration via multi-space. Regul. Chaotic Dyn. 9(3), 213–226 (2004)
B. Leimkuhler, S. Reich, Simulating Hamiltonian Dynamics. Cambridge Monographs on Applied and Computational Mathematics, vol. 14 (Cambridge University Press, Cambridge, 2004)
R.J. LeVeque, Finite Volume Methods for Hyperbolic Problems. Cambridge Texts in Applied Mathematics (Cambridge University Press, Cambridge, 2002)
D. Levi, M.A. Rodríguez, λ-symmetries for discrete equations. J. Phys. A 43(29), 292001 (2010)
D. Levi, R.I. Yamilov, Conditions for the existence of higher symmetries and nonlinear evolutionary equations on the lattice. in Algebraic Methods in Physics, ed. by Y. Saint-Aubin, L. Vinet, CRM Series in Mathematical Physics (Springer, New York, 2001), pp. 135–148
D. Levi, R.I. Yamilov, The generalized symmetry method for discrete equations. J. Phys. A 42(45), 454012 (2009)
D. Levi, P. Winternitz, Continuous symmetries of difference equations. J. Phys. A 39(2), R1–R63 (2006)
D. Levi, S. Tremblay, P. Winternitz, Lie point symmetries of difference equations and lattices. J. Phys. A 33(47), 8507–8523 (2000)
D. Levi, S. Tremblay, P. Winternitz, Lie symmetries of multidimensional difference equations. J. Phys. A 34(44), 9507–9524 (2001)
D. Levi, M.C. Nucci, M.A. Rodríguez, λ-symmetries for the reduction of continuous and discrete equations. Acta Appl. Math. 122, 311–321 (2012)
D. Levi, L. Martina, P. Winternitz, Lie-point symmetries of the discrete Liouville equation. J. Phys. A 48(2), 025204 (2015)
D. Levi, L. Martina, P. Winternitz, Structure preserving discretizations of the Liouville equation and their numerical tests. SIGMA 11, Paper 080 (2015)
D. Levi, C. Scimiterna, Z. Thomova, P. Winternitz, Contact transformations for difference schemes. J. Phys. A 45(2), 022001 (2012)
H. Levy, F. Lessman, Finite Difference Equations (Dover, New York, 2011)
E.L. Mansfield, A Practical Guide to the Invariant Calculus Cambridge Monographs on Applied and Computational Mathematics, vol. 26 (Cambridge University Press, Cambridge, 2010)
E.L. Mansfield, P.E. Hydon, Difference forms. Found. Comput. Math. 8(4), 427–467 (2008)
G. Marí Beffa, P.J. Olver, Poisson structures for geometric curve flows in semi-simple homogeneous spaces. Regul. Chaotic Dyn. 15(4–5), 532–550 (2010)
G. Marí Beffa, E.L. Mansfield, Discrete moving frames on lattice varieties and lattice based multispaces. Found. Comput. Math. (2016). doi:10.1007/s10208-016-9337-5
P.J. Olver, Applications of Lie Groups to Differential Equations, 2nd edn. Graduate Texts in Mathematics, vol. 107 (Springer, New York, 1993)
P.J. Olver, Moving frames and singularities of prolonged group actions. Sel. Math. (N.S.) 6(1), 41–77 (2000)
P.J. Olver, Geometric foundations of numerical algorithms and symmetry. Appl. Algebra Eng. Commun. Comput. 11(5), 417–436 (2001)
P.J. Olver, Equivalence, Invariants, and Symmetry (Cambridge University Press, Cambridge, 2009)
P.J. Olver, Recursive moving frames. Res. Math. 60(1–4), 423–452 (2011)
P.J., Olver, J. Pohjanpelto, Moving frames for Lie pseudo-groups. Can. J. Math. 60(6), 1336–1386 (2008)
P.J. Olver, J. Pohjanpelto, Differential invariant algebras of Lie pseudo-groups. Adv. Math. 222(5), 1746–1792 (2009)
P.J. Olver, F. Valiquette, Recursive moving frames for Lie pseudo-groups. Preprint, University of Minnesota (2015)
L.V. Ovsiannikov, Group Analysis of Differential Equations (Academic Press, New York, 1982)
G.R.W. Quispel, D.I. McLaren, A new class of energy-preserving numerical integration methods. J. Phys. A 41(4), 045206, 7 (2008)
R. Rebelo, F. Valiquette, Symmetry preserving numerical schemes for partial differential equations and their numerical tests. J. Differ. Equ. Appl. 19(5), 738–757 (2013)
R. Rebelo, F. Valiquette, Invariant discretization of partial differential equations admitting infinite-dimensional symmetry groups. J. Differ. Equ. Appl. 21(4), 285–318 (2015)
J.N. Reddy, An Introduction to Finite Element Method. McGraw-Hill Series in Mechanical Engineering, 3rd edn. (McGraw-Hill, New York, 2006)
M.A. Rodríguez, P. Winternitz, Lie symmetries and exact solutions of first-order difference schemes. J. Phys. A 37(23), 6129–6142 (2004)
Yu.I. Shokin, The Method of Differential Approximation. Springer Series in Computational Physics (Springer, Berlin, 1983)
Z. Thomova, P. Winternitz, Maximal abelian subgroups of the isometry and conformal group of Euclidean and Minkowski spaces. J. Phys. A 31(7), 1831–1858 (1998)
F. Valiquette, Solving local equivalence problems with the equivariant moving frame method. SIGMA 9, Paper 029 (2013)
M. Welk, P. Kim, P.J. Olver, Numerical invariantization for morphological PDE schemes, in Scale Space and Variational Methods in Computer Vision, ed. by F. Sgallari, A. Murli, N. Paragios. Lecture Notes in Computer Science, vol. 4485 (Springer, New York, 2007), pp. 508–519
P. Winternitz, Symmetries of discrete systems, in Discrete Integrable Systems, ed. by B. Grammaticos, Y. Kosmann-Schwarzbach, T. Tamizhmani. Lecture Notes in Physics, vol. 644 (Springer, Berlin, 2004), pp. 185–243
N.N. Yanenko, Yu.I. Shokin, Group classification of difference schemes for the system of equations of gas dynamics. Trudy Mat. Inst. Steklov. 122, 85–97 (1973). In Russian
G. Zhong, J.E. Marsden, Lie–Poisson Hamilton–Jacobi theory and Lie–Poisson integrators. Phys. Lett. A 133(3), 134–139 (1988)
Acknowledgements
The research of the first author is supported in part by a Tier 2 NSERC Canada Research Chair grant. The authors would like to thank the organizers of the ASIDE summer school for inviting them to give a series of lectures on continuous symmetries of discrete equations. We also thank Peter J. Olver for his comments on our lecture notes.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this chapter
Cite this chapter
Bihlo, A., Valiquette, F. (2017). Symmetry-Preserving Numerical Schemes. In: Levi, D., Rebelo, R., Winternitz, P. (eds) Symmetries and Integrability of Difference Equations. CRM Series in Mathematical Physics. Springer, Cham. https://doi.org/10.1007/978-3-319-56666-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-56666-5_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-56665-8
Online ISBN: 978-3-319-56666-5
eBook Packages: Physics and AstronomyPhysics and Astronomy (R0)