Seminar Sophus Lie 2 (1992) 223–233

Gröbner Bases, Standard Forms of

Differential Equations and Symmetry Computation

Günter Czichowski and Maik Thiede

1. Introduction

In the last twenty years Gröbner base constructions (Buchberger’s algorithm) have found a greater interest for many computer algebra applications. At the first time the main field was of course due to (commutative) polynomial rings, algebraic equations etc., but in recent time there is an increasing number of papers concerning constructions in noncommutative rings and algebras, especially Lie algebras [1,2,8], too. With respect to this topic the case of rings of differential operators is very important, since the corresponding algorithmic constructions are closely related to methods for the systematic simplification of systems of linear differential equations. The basic ideas in this field have already been known for many years ago [7,10]. But in the last time they were used and developed with respect to algorithmic and computational aspects [11,13,14]. A very important field for applications is the symmetry computation for differential equations. Here, there exist some methods and algorithms, this paper is related to an algorithm presented by G. J. Reid [11], whose kernel is the systematic evaluation of integrability conditions. This is controlled by a certain order, and the method is in fact a Gröbner basis construction for a system of linear differential equations, althought there is no hint in this direction. Our aim is to present consequently this point of view here and to give some conclusions and examples.

2. Standardforms for Differential Operators

Here we will describe an algorithm, which transforms a system of linear differential operators (or, respectively, the corresponding system of linear homogeneous differential equations) to a standardform. This is the noncommutative Gröbner base construction corresponding to the algorithm of Reid mentioned above. With respect to differential equations the method uses two basic steps - addition of integrability conditions and reduction of equations by the system. The situation here differs from other constructions introduced earlier for noncommutative structures [1,2], since coefficients and basic monomials do not commute i.g., but the algebras of operators regarded here in the first part are of course solvable. Further, for simplicity we regard here only differential operators in two variables x, y, but this restriction is not essential. The starting point for all further constructions is the following fundamental theorem, which can be proved as an analog to the Hilbert base theorem for polynomial ideals, the proof differs from the classical proof only with respect to technical changes.

Theorem 2.1. Let F denote a differential field of functions depending on two variables x, y, and D the ring of all linear differential operators in x, y with coefficients from F:

D = \{D = ∑_{i∈I,j∈J} a_{ij} \frac{∂^{i+j}}{∂x^{i}∂y^{j}} | I, J finite, a_{ij} ∈ F \}

Then D is a left-noetherian ring.

D is considered here rather as a pure algebraic object, the question of a corresponding domain for the coefficient functions will be discussed later.

2.1. Basic notions

The analogue to the case of polynomial rings is obvious: Monomials are operators of the form M = \frac{∂^{i+j}}{∂x^{i}∂y^{j}} , every operator from D is then a linear combination of monomials with coefficients from F.

Further one has to fix a term order, this is a total order “≤” in the set of monomials satisfying 1 ≤ M, and M_{1} ≤ M_{2} ⇒ MM_{1} ≤ MM_{2} for all monomials M, M_{1}, M_{2}.

If {M_{n}} is a given sequence of monomials, one can regard the left ideals of D generated by a finit number of this monomials. Using the above theorem, one immediately gets the following two statements:

Lemma 2.2. Every decreasing sequence of monomials terminates.

Lemma 2.3. (Dickson’s Lemma) Let {M_{n}} be a sequence of monomials such that for k ≤ n M_{n} is not divisible by M_{k}. Then {M_{n}} terminates.

In particular, every operator D ∈ D contains a highest monomial (the leading derivative) which characterizes the size of D.

The notion of reduction concerns the simplification (with respect to the chosen order) of one operator D by another operator D_{1}; the result is an operator D^{∗}. The symbolic formula D → D^{∗} modulo D_{1} for this procedure means that there is an equation

D^{∗} = D − aMD_{1},

where a ∈ F and the monomial M are chosen such that the leading term of aMD_{1} cancels a term of D.

The reduction of an operator D by a system S = {D_{1}, …, D_{n}} to an operator D^{∗} then means, that there is a chain of subsequent reductions modulo operators from S, which transforms D to D^{∗}. In general there are various possibilities for the reductions of a given operator D modulo a given system S. But every reduction of D leads to an operator which is less than D (with respect to the monomial order, that means with respect to the monomials contained in D). Therefore, from the above lemmata it easily follows, that any chain of reductions must terminate. An operator D^{∗} is called a normal form of D (with respect to S) if D^{∗} is obtained by reductions modulo S from D and further reductions of D^{∗} are impossible. In general there are several normal forms of a given operator; this is the central point for the definition of standard forms. Definition. A system SF of operators from D is called standard form, if every operator D ∈ D has exactly one normal form modulo SF. A reduced standard form is a standard form SF, in which every operator is in normal form with respect to the remaining operators of SF and has the highest coefficient 1.

For the construction of standard forms one needs further as analogue to the classical case a second operation corresponding to the computation of integrability conditions for linear differential equations. Definition. Let D_{1}, D_{2} denote differential operators from D. Then the operator

S(D_{1}, D_{2}) = M_{1}D_{1} − \frac{a_{1}}{a_{2}} M_{2}D_{2}

is called the S-operator of D_{1}, D_{2}. Here a_{1}, a_{2} ∈ F are the highest coefficients of D_{1} and D_{2}, and the the monomials M_{1}, M_{2} are chosen minimally such that the leading monomials of M_{1}D_{1} and M_{2}D_{2} are equal.

The following theorem is fundamental for the existence and construction of standard forms of differential operators:

Theorem 2.4. Let S = {D_{1}, …, D_{n}} be a system of differential operators from D. Then the following statements are equivalent:

(1) S is a standard form.

(2) Every S-operator S(D_{i}, D_{k}) with D_{i}, D_{k} ∈ S can be reduced modulo S to zero.

(3) If L denotes the left ideal generated by S, then every operator D ∈ L can be reduced modulo S to zero.

Remark. Statement (3) is not trivial, since reductions are closely related to the order! Indication of Proof. The essential part of the proof is that of the implication (2) ⇒ (3), the idea is sketched here only:

Let be D ∈ L. Then D has the form D = A_{1}D_{1} + ⋯ + A_{n}D_{n} with certain operators A_{i} from D. One can regard the n-tupel (A_{1}, …, A_{n}) as a (not uniquely determined) representant for D, which characterizes the size of D . Then the relations S(D_{i}, D_{k}) → 0 mod S can be used to construct smaller representants for the reductions of D so long as these are not equal to zero.

2.2. Construction of standard forms

The characterization of standard forms by Theorem 2.1 suggests the following algorithm, which leads from a given System S = {D_{1}, …, D_{n}} of differential operators to a standard form.

Step 1: Input of S.

Step 2: Form B := {(D_{i}, D_{j}), D_{i}, D_{j} ∈ S, D_{i} ≠ D_{j}}

Step 3: While B ≠ Ø choose a pair (D_{i}, D_{j}) from B and compute a normal form D^{∗} modulo S of the corresponding S-operator.

Step 4: If D^{∗} = 0 then cancel (D_{i}, D_{j}) in B.

If B = Ø then S is a standard form and the algorithm is finished else goto Step 3. If D^{∗} ≠ 0 then form S := S ∪ {D^{∗}} and goto Step 2.

The algorithm must terminate, the argument is the same as in the classical case: Consider the leading monomials of the operators from S and the left ideals which can be generated by this monomials subsequently in the various steps. The sequence of these monomials must terminate… Some examples follow in section 3.2.

3. Standard forms of Differential Equations and Symmetry Computation

3.1. Concept and Effects

Our aim is now to apply the Gröbner base constructions, or the standard form algorithm for differential operators, to systems of linear differential equations. Although the method is clear in principle, we have to make here some remarks with respect to effects. At first, very important for Gröbner base constructions is the chosen term order for monomials. The orders used in general are based on the priorities 1. Total degree of derivatives, 2. Rank of functions, 3. Lexicographic order of differentiation variables [11,13]. This makes sense with respect to the classical methods in the analysis of differential equations and corresponds to the aim “express higher derivatives by lower derivatives.”

But from a rather algebraic point of view, at first the properties “higher” and “lower ” are declared by the abstract term order and , at second, with respect to a certain analogue to algebraic equations and in order to get a block structure with respect to the functions, it is more useful to start with an order determined by the priorities

1. Rank of the functions,

2. Lexicographic order of the variables,

3. Degree of derivatives.

The advantages of corresponding standard forms of systems of linear differential equations are the following:

1. By ordering the differential equations with respect to the leading derivatives, blocks are obtained with respect to the several functions. Especially, if it is possible to derive differential equations with respect to only one function from the system, then the standard form must contain such equations, with respect to a suitable rank of functions, too.

2. One gets an analogue to the case of polynomials ore algebraic equations, respectively:

Systems of algebraic equations Systems of linear differential equations
Solvability  Nontrivial Solvability
Finitely many solutions  Finite-dimensional space of solutions
Univariate equations  Ordinary differential equation

3. In particular, a system of linear differential equations for the functions u_{1}, …, u_{m} has only trivial solutions if and only if its standard form is

u_{1} = 0, …, u_{m} = 0,

this means, that these equations can be derived from the original system by using only differentiations and forming linear combinations. The solution space is finite dimensional iff for every function u_{j} and every variable x_{i} the standard form contains an equation with a leading derivative of the form \frac{∂^{k}u_{j}}{∂x_{i}^{k}} [11].

4. With respect to the order mentioned above it follows: If the space of solutions is finite dimensional , then the last block (with the “lowest” leading derivatives) of a standard form must be a block with only one function and the last differential equation must be in fact an ordinary differential equation. Since the dimension of the solution space is invariant, one can (with respect to other ranks of functions and differentiation variables) derive certain ordinary differential equations. This leads by solving to separation of variables and simplification of the problem.

But to prove this effects one must leave the pure algebraic point of view. At least it seems to be impossible to get a central statement without additional analytical assumptions: The solution space determines the standard form. We will discuss this problems in the following.

3.2. Algebraic and Analytic Background

Suppose that a system of linear differential equations for one function u is given. We will write it in the form

D_{1}(u) = 0, …, D_{n}(u) = 0,

where D_{1}, …, D_{n} denote linear differential operators with coefficients from a differential field F. Using these differential equations we can form new equations and operators by differentiation and algebraic operations; the adding of this new equations does not change the space of solutions. The problem concerning standard forms can be formulated now as follows:

Let D be the ring of all linear differential operators with coefficients from F and L a left ideal of D. Determine, with respect to a fixed order, a Gröbner base of L.

This problem is solved by the standard form algorithm. If a system S of linear differential equations for m functions u_{1}, …, u_{m} is given, then every equation can be written as

D_{1}(u_{1}) + ⋯ + D_{m}(u_{m}) = 0,

and, for a fixed function rank, in this way to every differential equation there corresponds an m-tupel (D_{1}, …, D_{m}) of differential operators from D^{m}. The action of a differential operator D ∈ D on the above equation leads to the mtupel (DD_{1}, …, DD_{m}) ∈ D^{m}, and therefore we have to regard D^{m} as D-module by muliplication of the components from the left by elements of D. The standard form problem is then formulated as follows:

Suppose that D^{m} is regarded as D-left module in the way described above and let M be a submodule of D^{m}. Determine, with respect to a given order, a Gröbner base of M.

If the function rank has the highest priority in the term order, then the standard form algorithm of Section 2 runs firstly with respect to the highest function, then in the remaining block with respect to the following function etc.

We will now introduce additional analytic assumptions, which are needed for the effects mentioned in the last section. Indeed, if one has a reduced standard form for a given system of linear differential equations, this leads to a partition of all derivatives into “evaluated” and “parametric” derivatives [11]. A derivative (monomial) is called evaluated, if it can be obtained by differentiation from the leading derivatives given by the standard form equations. All other derivatives are called parametric. The intention is obvious: If the corresponding assumptions for existence and uniqueness of solutions are fullfilled—as in the theorem of Cauchy-Kowalewski—then the values of the parametric derivatives can be chosen arbitrarily and the values of the evaluated derivatives are obtained then by using differentiation from the standard form equations. Especially, the dimension of the space of solutions (regarded as germs at a particular point) is equal to the number of parametric derivatives [11].

We will now formulate conditions, which are not very restrictive and ensure the facts described above.

1. Let G be an open domain in R^{n} and F denote a differential field of functions, which are meromorphic in G.

2. Let S be a system of linear homogeneous differential equations with coefficients from F and SF denote the reduced standard form of S. A point x ∈ G is called regular, if all coefficients of SF are analytic in x. The statement “S has a finite dimensional solution space” then means, that for every regular point x ∈ G the space of the solutions being analytic in x (as germs) is finite dimensional.

With respect to the general situation the following theorem gives now a satisfactory charactarization of standard forms from the local point of view.

Theorem 3.1. Let SF_{1} and SF_{2} denote two reduced standard forms with coefficients being analytic in an open domain G such that for every x ∈ G the spaces of solutions, which are analytic in x, coincide. Then SF_{1} and SF_{2} are identical in G . Idea of the Proof. The idea of the proof is to give firstly an invariant characterization of the sets of evaluated and parametric derivatives. If this sets coincide for SF_{1} and SF_{2}, then it follows immediately, that equations with the same leading derivative must coincide.

Remark. Of course, the reduced standard form is determined uniquely in every case by the original system—the argumentation is algebraic and similar to the classical case—but this is not the essential point here.

In order to use this theorem we illustrate the consequences for the construction of ordinary differential equations from a given system

D_{1}(u_{1}) = 0, …, D_{m}(u_{m}) = 0

with a finite dimensional solution space. If u_{m} is chosen as the lowest function und x_{n} as the lowest variable, then the “u_{m}-parts” of the solutions form a finite dimensional space and satisfy therefore an equation D(u_{m}) = 0, where D is a differential operator with respect to x_{n} only. Since the addition of D(u_{m}) = 0 to the original system does not change the solution space, the above theorem implicates the reduction to zero of this equation by the standard form of the above system. But the operator D can be reduced only by operators, which are differential operators with respect to x_{n} alone.

4. Symmetry Computation, Examples

We give as applications here some examples concerning the symmetry computation for ordinary differential equations. If one starts with an Ansatz ∂ = ξ(x, y)\frac{∂}{∂x} + η(x, y)\frac{∂}{∂y} for the symmetry generators, then a well known procedure leads to the so called determining equations, which form a system of linear homogeneous differential equations for the functions ξ and η. Since the maximal number of symmetries is 8 for second order equations and n+4 for nth-order equations (n ≥ 2) [9], the space of solutions (ξ, η) is finite dimensional. Therefore, by applying standard forms, the problem of symmetry computation will be reduced to solving linear homogeneous ordinary differential equations. If the procedure of constructing the determining equations is regarded as algorithmic, the result can be formulated as follows: The symmetry computation for ordinary differential equation is algorithmic ”modulo” solving linear homogeneous ordinary differential equations. This is a partial answer to a question of F.Schwarz [12].

In the following examples we give for some second order ordinary differential equations the determining equations , its standard forms (with respect to a fixed order) and the (generally 4) linear homogeneous ordinary differential equations which can be derived on the first level from the standard form by changing the order of functions and variables.

Example 1. Differential equation:

y′′ = \frac{(y′^{2} + 1)^{\frac{3}{2}} + 2(y′x − y)(y′^{2} + 1)}{x^{2} + y^{2} + 1}.

Determining equations:

0 = −(x^{2} + y^{2} + 1)^{2}ξ_{yy} − 2(x^{2} + y^{2} + 1)x(ξ_{x} − 2η_{y}) − 2(x^{2} + y^{2} + 1)yξ_{y},
−2x^{2}ξ − 4xyη + 2y^{2}ξ + 2ξ,
0 = 2(x^{2} + y^{2} + 1)^{2}(2ξ_{xy} − η_{yy}) + 2(x^{2} + y^{2} + 1)x(2ξ_{y} + 3η_{x}),

230 Czichowski and Thiede

−2(x^{2} + y^{2} + 1)yη_{y} − 2x^{2}η + 4xyξ + 2y^{2}η − 2η,

0 = 2(x^{2} + y^{2} + 1)^{2}(ξ_{xx} − 2η_{xy}) + 2(x^{2} + y^{2} + 1)xξ_{x},

−2(x^{2} + y^{2} + 1)y(3ξ_{y} + 2η_{x}) − 2x^{2}ξ − 4xyη + 2y^{2}ξ + 2ξ,

0 = ξ_{y} + η_{x},
0 = 2(x^{2} + y^{2} + 1)^{2}η_{xx} − 2(x^{2} + y^{2} + 1)xη_{x} + 2(x^{2} + y^{2} + 1)y(2ξ_{x} − η_{y})
+2x^{2}η − 4xyξ − 2y^{2}η + 2η,
0 = (x^{2} + y^{2} + 1)(2ξ_{x} − η_{y}) − 2xξ − 2yη,
0 = (x^{2} + y^{2} + 1)(ξ_{x} − 2η_{y}) + 2xξ + 2yη.

Standard form:

0 = (x^{2} + y^{2} + 1)η_{y} − 2xξ − 2yη,
0 = (x^{2} + y^{2} + 1)η_{yy} + 2η_{x}x − 2η,
0 = (η_{xy}x − η_{y})(x^{2} + y^{2} + 1) − 2η_{x}xy + yη,
0 = (x^{2} + y^{2} + 1)η_{xx} − 2η_{x}x + 2η.

Ordinary differential equations which can be derived:

0 = (x^{2} + y^{2} + 1)ξ_{yy} − 2ξ_{y}y + 2ξ,
0 = ξ_{xxx},
0 = η_{yyy},
0 = (x^{2} + y^{2} + 1)η_{xx} − 2η_{x}x + 2η.

The symmetry generators ∂ = ξ(x, y)\frac{∂}{∂x} + η(x, y)\frac{∂}{∂y} are given by

ξ = αy + β(1 + x^{2} − y^{2}) + 2γxy, η = −αx + γ(1 − x^{2} + y^{2}) + 2βxy. The differential equation has so(3)-symmetry. Example 2. Differential equation:

y′′ = (1 + y′^{2})^{\frac{3}{2}} e^{βatan(y′)}.

Determining equations:

0 = ξ_{yy},
0 = 2ξ_{xy} − η_{yy},
0 = ξ_{x}β − 3ξ_{y} − 3η_{x} − η_{y}β,
0 = ξ_{x} + ξ_{y}β − 2η_{y},
0 = ξ_{xx} − 2η_{xy},
0 = 2ξ_{x} + η_{x}β − η_{y},
0 = η_{xx},

Standard form:

0 = ξ_{y} + η_{x},
0 = ξ_{x} + η_{x}β,
0 = η_{x}β + η_{y},
0 = η_{xx}.

The ordinary differential equations are

ξ_{yy} = ξ_{xx} = η_{yy} = η_{xx} = 0.

The symmetry generators are easily computed and form a three dimensional solvable Lie algebra. Example 3. Differential equation:

y′′ = \frac{yy′}{x} + y′^{2}.

Determining equations:

0 = ξ_{yy} + ξ_{y},
0 = 2ξ_{xy}x + 2ξ_{y}y − η_{yy}x + η_{y}x,
0 = ξ_{xx}x^{2} + ξ_{x}xy − 2η_{xy}x^{2} + 2η_{x}x^{2} + xη − yξ,
0 = η_{xx}x − η_{x}y,

Standard form:

0 = ξ_{y}, 0 = ξ_{x}x − ξ, 0 = η.

These equations are ordinary differential equations. The original differential equation has one symmetry. Example 4. Differential equation:

y′′ = 6y^{2} + x.

Determining equations:

0 = ξ_{yy},
0 = 2ξ_{xy} − η_{yy},
0 = ξ_{xx} + 3ξ_{y}x + 18ξ_{y}y^{2} − 2η_{xy},
0 = 2ξ_{x}x + 12ξ_{x}y^{2} − η_{xx} − η_{y}x − 6η_{y}y^{2} + 12yη + ξ.

Standard form:

ξ = 0, η = 0.

(No symmetries). Here the determining equations are not difficult, and the result of the standard form procedure is very simple, but the original algorithm itself produces very many dates and computations!

Example 5. Consider the linear differential equation

y′′ = ρ(x)y.

Here one can derive, for the functions ξ and η, the equations ξ_{yy} = 0 and η_{yyy} = 0. By a corresponding separation Ansatz the standard form procedure leads to two ordinary linear homogeneous differential equations, the original equation and the third order equation

z′′′ − 4ρz′ − 2ρ′z = 0

Therefore symmetry computation is effective in this case only if there are known solutions of this equation. Iteration of the whole procedure, that means to ask for symmetries of this last equation, breaks off, since no other ordinary differential equations than this equation itself are produced by the standard form procedure for symmetry computation. Without the above Ansatz the ordinary differential equations for ξ and η with respect to x are in a general form rather complicated, for instance the equation for ξ is 0 = (3ρ′′ρ − 4ρ′^{2} + 9ρ^{3})ξ_{xxxxx} + (−3ρ′′′ρ + 5ρ′′ρ′ − 27ρ′ρ^{2})ξ_{xxxx} + (4ρ′′′ρ′ − 5ρ′′^{2} − 30ρ′′ρ^{2} + 56ρ′^{2}ρ − 45ρ^{4})ξ_{xxx} + (12ρ′′′ρ^{2} − 50ρ′′ρ′ρ + 40ρ′^{3} + 18ρ′ρ^{3})ξ_{xx} + (2ρ′′′ρ′ρ − 4ρ′′^{2}ρ + 2ρ′′ρ′^{2} + 2ρ′^{2}ρ^{2} + 36ρ^{5})ξ_{x} + (−18ρ′′′ρ^{3} + 90ρ′′ρ′ρ^{2} − 80ρ′^{3}ρ + 18ρ′ρ^{4})ξ.

References

[1] Apel, J., “Gröbnerbasen in nichtkommutativen Algebren und ihre Anwendung,” Dissertation, Universität Leipzig, 1988.

[2] Apel, J., and W. Laßner, An extension of Buchbergers algorithm and calculating in enveloping fields of LIE-algebras, Preprint NTZ Universität Leipzig, 1985.

[3] Buchberger, B., Gröbner bases—an algorithmic method in polynomial ideal theory, Ch. 6 in N. K. Bose (ed.) (Multidim. Systems Theory), D. Reidel Publ. Comp., 1985.

[4] Buchberger, B., G. E. Collins, and R. Loos, “Computer Algebra,” Springer, 1983.

[5] Czichowski, G., Behandlung von Differentialgleichungen mit LIE-Theorie und Computer, Mitt. d. MGdDDR, Heft 3–4, (1988), 3–20.

[6] Czichowski, G.,LIE Theory of Differential Equations and Computer Algebra, Seminar Sophus Lie (Heldermann Verlag Berlin), 2 (1991), 83–91.

[7] Janet, M., “Les Systèmes d’ équations aux dérivées partielles,” Gauthier-Villars, Paris 1927.

[8] Kandri-Rody, A., and V. Weispfenning, Non-commutative Gröbner bases in algebras of solvable type, Preprint Univ. Passau MIP-8807, 1988.

[9] Lie, S., ,,Vorlesungen über Differentialgleichungen mit bekannten infinitesimalen Transformationen“, Teubner, Leipzig, 1912.

[10] Riquier, C., “Les systèmes d’ équations aux dérivées partielles,” Gauthier-Villars, Paris 1910.

[11] Reid, G. J., A triangularization algorithm which determines the Lie symmetry algebra of any system of PDEs, J. Phys., A–Math. Gen. 23 (1990), L 853.

[12] Schwarz, F., Computer Algebra and Differential Equations, GMD Report, St. Augustin 1991.

[13] —, Monomial orders and Gröbner bases, ACM SIGSAM Bulletin 25 (1991), 10–23.

[14] Wolf, T., An analytic algorithm for decoupling and integration systems of nonlinear partial differential equations, J. Comp. Ph. 60 (1985), 437–446.

Ernst-Moritz-Arndt-Universität FR Mathematik/Informatik F. L. Jahnstr. 15 a O–2200 Greifswald, Germany czichowski@math-inf.uni-greifswald.dbp.de

Received October 21, 1992