9512.net

# The integration of systems of linear PDEs using conservation laws of syzygies

The integration of systems of linear PDEs using conservation laws of syzygies
Thomas Wolf Department of Mathematics Brock University, 500 Glenridge Avenue, St.Catharines, Ontario, Canada L2S 3A1 email: twolf@brocku.ca February 1, 2008
Abstract A new integration technique is presented for systems of linear partial di?erential equations (PDEs) for which syzygies can be formulated that obey conservation laws. These syzygies come for free as a by-product of the di?erential Gr¨bner Basis computation. Compared with the more o obvious way of integrating a single equation and substituting the result in other equations the new technique integrates more than one equation at once and therefore introduces temporarily fewer new functions of integration that in addition depend on fewer variables. Especially for high order PDE systems in many variables the conventional integration technique may lead to an explosion of the number of functions of integration which is avoided with the new method. A further bene?t is that redundant free functions in the solution are either prevented or that their number is at least reduced.

arXiv:cs/0301028v1 [cs.SC] 28 Jan 2003

1

A critical look at conventional integration

In this paper a new integration method is introduced that is suitable for the computerized solution of systems of linear PDEs that admit syzygies. In the text we will call the integration of single exact di?erential equations, i.e. equations which are total derivatives, the ‘conventional’ integration method (discussed, for example, in [11]). To highlight the di?erence with the new syzygy based integration method we have a closer look at the conventional method ?rst. About notation: To distinguish symbolic subscripts from partial derivatives we indicate partial derivatives with a comma, for example, ?xy ei = ei ,xy . To solve, for example, the system 0 = f,xx 0 = xf,y +f,z (1) (2)

for f (x, y, z) one would, at ?rst, integrate (1) with 2 new functions of integration g(y, z), h(y, z), then substitute f = xg + h (3) 1

into (2), do a separation with respect to di?erent powers of x to obtain the system 0 = g,y 0 = g,z +h,y 0 = h,z and solve that to get the solution f = x(az + b) ? ay + c, a, b, c = const.

The main gain of information on which the overall success was based did happen after the substitution at the stage of separating (2) into 3 equations. The integration of (1) itself did not provide new information. The equation 0 = f,xx is more compact than f = xg + h and equally well usable in an ongoing elimination process (Gr¨bner Basis computation). (Similarly, in this sense, o f (x) = a sin(x) + b cos(x) would not provide new information compared to 0 = f ′′ + f as sin and cos are only de?ned as solutions of this ODE.) The main conclusion is: The integration of a single equation does not necessarily imply progress in the solution of a system of PDEs, especially if a direct separation does not become possible as the result of substituting a computed function. This is the case in the example 0 = f,yzz 0 = f,xx +f,z . (=: e1 ) (=: e2 ) (4) (5)

discussed in more detail in the next section. Integration of (4) to f = g1 (x, y) + zg2 (x, y) + g3 (x, z) and substitution into (5) does not yield a separable equation and is therefore not as straight forward to utilize as in the ?rst example. There is another problem with the conventional method which seems insigni?cant at ?rst sight but becomes severe for high order PDE systems in many independent variables, for example in the application in section 9. Substituting f = g1 (x, y) + zg2 (x, y) + g3 (x, z) into (5) as done in section (2.2) and ?nding the general solution for g1 , g2 , g3 is, strictly speaking, a di?erent problem from ?nding the general solution for f of (4), (5)! The general solution for g1 , g2 , as determined in section 2.2, will involve among other functions the two essential free functions g6 (x), g7 (x). From the point of view of the original system (4), (5) these are redundant functions as they can be absorbed by g3 . Redundancy is an inherent problem of the conventional integration method which has nothing to do of how e?cient the remaining system after integration and substitution is solved. In section 6 this issue is discussed in more detail. With the new syzygy based integration the situation is very di?erent. Here the decision whether to integrate is based on syzygies, i.e. on relations between equations, like
2 2 0 = (?x + ?z )e1 ? ?y ?z e2

in the last example and is not based on the form of a single equation. This extra information content coming from the syzygies allows the method to perform useful integrations for systems like (4), (5) with an instantly useful result. As will be explained further below, syzygy based integration does not only integrate one single equation at a time, but in a sense, it performs an integration which is compatible with all the equations involved in the syzygy. (More exactly, it integrates all equations 0 = P i at once one time where P i are the components of the conserved current of the conservation law of the syzygies.) 2

This restrictive ’compatibility constraint’ has the e?ect that the integral involves fewer new functions of integration which furthermore depend on fewer variables. Consequently fewer new functions have to be computed later on which shortens the computation. Also, fewer redundant functions are generated which not only avoids the explosion of the number of intermediately generated functions but also simpli?es the ?nal solution. These e?ects are especially important for high order PDEs in many variables as explained in section 6. The above distinctions between both integration techniques are not purely academic. Section 9.2 describes how integrations can be combined with eliminations. To apply integrations early in the solution process is not new. This strategy has been pursued by the program Crack for nearly 2 decades. What is interesting and new is how much more bene?cial the syzygy based integration proves to be compared with conventional integration. In section 9.2 such a comparison has been made. One problem has been solved 3 times with a combination of di?erent modules, including elimination and conventional and syzygy based integration. The 3 runs di?er only in the priority of applying these modules and were compared by their running times as well as the number of redundant functions in the ?nal solution. About the remainder of the paper In section 3 the algorithm is described in general and an overview is provided. Using the information content of syzygies in the form of conservation laws seems to be the most direct and useful way but it is not the only one possible. In section 4 a variation of the algorithm is explained which is based on vanishing curls of syzygies. Di?erent aspects of the computation of conservation laws for syzygies are the subject of the following section. The redundancy problem mentioned above is looked at in detail in section 6. Even though conservation laws of syzygies might be known, it may not be advantageous to use them if the aim is the exact solution of the original PDE-system. In section 7 examples are given. A short description of how syzygies are recorded in section 8 is followed by section 9 introducing the ‘real-life’ application which led to the development of syzygy based integration. In three computer runs it is shown that this integration method and elimination can be naturally combined for the solution of linear PDE systems. In the following section the introductory example is continued and both integration methods are compared.

2

An introductory example

We continue the above example to explain the basic mechanism of syzygy based integration. A more complex example is given in section 9.

2.1

Treated with the new method

In applying integrability conditions for PDEs systematically, i.e. in computing a di?erential Gr¨bner o basis, identities between equations 0 = ea will result that take the form of di?erential expressions with the ea as dependent variables. We consider the simple system (4), (5), i.e. 0 = f,yzz 3 (= e1 )

0 = f,xx +f,z .

(= e2 )

Assuming, for example, a total ordering >o of derivatives that implies ?x >o ?z and ?y >o ?z , a di?erential Gr¨bner Basis computation would ?rst eliminate f,xxyzz through cross-di?erentiation: o 0 = e2 ,yzz ?e1 ,xx = f,yzzz then a substitution of f,yzz using e1 yields 0 = e3 ? e1 ,z and a substitution of e3 using (6) provides the identity 0 = e2 ,yzz ?(e1 ,xx +e1 ,z ). (7) (=: e3 ) (6)

The choice of ordering does not matter here. Any ordering would have resulted in identity (7). In this paper we concentrate ourselves to the integration of syzygies, like (7), which either have the form of a divergence or can be combined linearly to give a divergence 0 = Di P i with suitable vector components P i (ek ) that are di?erential expressions in the ek . Only in section 4 we outline a variation of this principle to deal with a vanishing curl of syzygies. The computation of conservation laws of syzygies has several aspects: how to do it in general, why the computation of conservation laws for syzygies is a relatively simple task and how to do it in less generality but much faster. In the interest of a compact example we postpone this discussion to section 5. There are di?erent ways to write (7) as a divergence. We choose any one with as few as possible components (here two: P x , P z ). This preference is justi?ed towards the end of this section below equation (20). The question how conservation laws with fewer components are computed is described in section 5 as well. We obtain: 0 = ?e1 ,xx + (e2 ,yz ?e1 ),z = P x ,x +P z ,z = (?f,xyzz ),x + (f,xxyz ),z . (8) (9) (10)

In the following we will use the vector P i in two representations, ?rst in terms of ei , in our example from the syzygy (8): (11) P x = ?e1 ,x , P z = e2 ,yz ?e1 and second the representation of P i in terms of the function f , in our example from the identity (10): P x = ?f,xyzz , P z = f,xxyz . (12) With P satisfying the conservation law condition (9) we can write P as a 2-dim. curl P x = ?Q,z , P z = Q,x (13)

for some potential Q. Using for P i the representation (12) we identify Q = f,xyz . The existence of di?erential expressions in unknowns, say f α , for the potential Q is guaranteed because all syzygies and all their consequences like 0 = Di P i are satis?ed identically for any f α . In 4

the appendix B an algorithm DivInt is given that computes potentials Qij (f α ) in general for an arbitrary number of independent variables. To do the next step in this example, we are reminded that expressions P i (ej ) are linear homogeneous in the ej and that they therefore must be zero, i.e. P x = P z = Q,x = Q,z = 0. This means that Q is independent of x, z, giving Q = c1 (y) and the new equation 0 = Q ? c1 = f,xyz ?c1 (=: e4 ) (14)

with the new function of integration c1 = c1 (y). Apart from the integral (14) we also get new syzygies. Having on one hand expressions for P i in terms of e1 , e2 due to equations (11) and on the other hand P i in terms of Q,j from equations (13) and Q in terms of e4 from equation (14) we get two new identities 0 = P x + Q,z = ?e1 ,x +e4 ,z 0 = P z ? Q,x = e2 ,yz ?e1 ? e4 ,x . (15) (16)

As equation e1 turns up algebraically in at least one of the new identities, this equation 0 = e1 is redundant and can be dropped. Redundancy of an original equation due to integration need not always be the case but it is the case in this example because at least one of P x and P z happens to be algebraic in e1 (in this case P z ). Identity (16) has already conservation law form. Substituting e1 from identity (16) into (15) preserves this form: 0 = (?e4 ,x ),x + (e2 ,xy ?e4 ),z . (17)

This completes one syzygy based integration step. Because the new system of equations 0 = e2 = e4 obeys the syzygy (17) which has a conservation law form with only 2 components P x , P z we can start another integration step without having to do a di?erential reduction or cross di?erentiation step. It turns out there are in total 3 more very similar syzygy integration steps to be performed which are summarized in appendix A. After these 3 steps the remaining system to solve consists of the 2 equations 0 = f,xx +f,z x3 x2 0 = f,y + c1 ? c2 ? xzc1 + zc2 ? xc3 ? c4 6 2 which satisfy the identity 0 = ?e2 ,y +e7 ,xx +e7 ,z . (20) This is a divergence too but now in three di?erentiation variables. With three non-vanishing P i the condition 0 = Di P i has the solution P i = Dj Qij with more than one non-vanishing Qij and the condition 0 = P i = Dj Qij has the solution Qij = Rijk ,k with free functions Rijk (xn ) = R[ijk](xn ) where [ijk] stands for total antisymmetrization. In three dimensions this introduces one new function R(xn ) = Rxyz through Qxy = R,z , Qyz = R,x , and Qzx = R,y . By performing a syzygy based integration again we would solve the remaining equations (18),(19) for one function f but also introduce one new unknown function R of all variables and therefore not make real progress. This is demonstrated in the ?rst example in section 7. These considerations explain why we try to ?nd conservation laws of syzygies with as few as possible non-zero P i . We return to our example and decide to integrate 0 = e7 (i.e. (19)) conventionally because ? identity (20) can not be written as a divergence with only 2 terms and 5 (= e2 ) (= e7 ) (18) (19)

? equation (19) can be integrated conventionally with respect to only one integration variable, so we will not introduce redundant functions as discussed in the introduction and in section 6. To y-integrate equation (19) we introduce four new functions d1 (y), . . . , d4 (y) through ci = di ,y and one new function d5 = d5 (x, z) and obtain f =? x2 x3 d1 + d2 + xzd1 ? zd2 + xd3 + d4 + d5 6 2 (21)

with the only remaining equation (18) now taking the shape 0 = d5 ,xx +d5 ,z . (22)

A single equation does not have syzygies and the method can not be applied further. What we achieved is the integration of equation (4) and the change of equation (5) for 3 independent variables into equation (22) for 2 variables.

2.2

The same example in a conventional treatment

For comparison, we solve the system (4), (5) again, this time in the conventional direct way. After integrating (4) to f = g1 (x, y) + zg2 (x, y) + g3 (x, z) (23) and substitution of f the equation (5) reads 0 = g1 (x, y),xx +zg2 (x, y),xx +g3 (x, z),xx +g2 (x, y) + g3 (x, z),z . (24)

In equation (24) there is no function that does depend on all variables and each variable does occur in at least one function. An algorithm for such ‘indirectly separable equations’ (ISEs) is contained in the package Crack (see [9] and sub-section 9.2). These equations undergo a series of di?erentiations and divisions (producing a list of divisors) ? to eliminate all functions of some variable, ? to do a direct separation with respect to this variable, and ? to use the same list of divisors now in reverse order as integrating factors to back-integrate the equations which resulted from direct separation. In the case of equation (24) a single y-di?erentiation eliminates g3 and allows a direct z separation (as g1 , g2 are independent of z) giving 0 = g2 (x, y),xxy , 0 = g1 (x, y),xxy +g2 (x, y),y and through back-integration with respect to y further 0 = g2 (x, y),xx +g4 (x) 0 = g1 (x, y),xx +g2 (x, y) + g5 (x) 0 = g3 (x, z),xx +g3 (x, z),z ?zg4 (x) ? g5 (x) (25) (26) (27)

6

with new functions of integration g4 , g5 . Renaming g4 = g6 (x),xxxx , g5 = g7 (x),xx and integrating equations (25), (26) gives g2 = ?g6 (x),xx ?xg8 (y) ? g9 (y) x2 x3 g1 = g6 (x) + g8 (y) + g9 (y) + xg10 (y) + g11 (y) ? g7 (x) 6 2 0 = g3 (x, z),xx +g3 (x, z),z ?zg6 (x),xxxx ?g7 (x),xx x3 x2 f = g3 (x, z) + g6 (x) + g8 (y) + g9 (y) + xg10 (y) + g11 (y) ? g7 (x) 6 2 ?z(g6 (x),xx +xg8 (y) + g9 (y)). (28) (29) (30)

(31)

The solution (31) is identical to (21) and the remaining condition (30) is identical to (22) if we drop the redundant functions g6 , g7 which can be absorbed by g3 and substitute g8 = ?d1 , g9 = d2 , g10 = d3 , g11 = d4 , g3 = d5 . A method to recognize redundancy is described in [13]. It involves the solution of an over-determined system of equations which involves even more e?ort. The introduction of redundant functions g6 , g7 in the conventional method was unavoidable because after reaching system (25) - (27) with the task to compute g1 , . . . , g5 the information was lost that, strictly speaking, not the most general expressions for g1 , . . . , g5 need to be computed but only the most general expression for f = g1 (x, y) + zg2 (x, y) + g3 (x, z). Setting g6 = g7 = 0 would be a restriction for g2 and g1 in (28), (29) but is not a restriction for f in (31).

3

The algorithm in general

In our notation xi , i = 1, . . . , p are the independent variables and f α are the unknown functions α which do not need to depend on all xi . These functions satisfy equations 0 = ea (xn , fJ ) where α 2 J is a multi-index (standing, for example, for 112 , i.e. ?x1 ?x2 ) and where fJ stands for a possible α α dependence on f and any partial derivatives of f . Total derivatives appear as Di . Summation is performed over identical indices. The following description is summarized in the overview underneath. The number(s) at the start of each item refer to the line number of the corresponding step in the overview. (32),(33): For a given system of di?erential equations (32) the investigation of integrability conditions (e.g. Gr¨bner basis computation) yields identities (33), called syzygies. In these syzygies o the ek take the role of dependent variables. The program Crack has been used to compute syzygies for examples presented in this paper but many other computer algebra programs are available (for example, RIF [8], di?alg [2],[3],[4], di?grob2 [6]) although only few generate syzygies automatically. (34): To ?nd conservation laws of syzygies one either can perform a more expensive but general search by using the package ConLaw [12] or other computer algebra software, or one can do a more specialized, less general but faster computation as described in section 5.3. In the conservation laws as in the syzygies the dependent variables are the ek . In order to introduce as few as possible new functions through a syzygy based integration, one aims at conservation laws with as few as possible non-zero P i (see discussion towards the end of section 2.1). Possible methods to achieve this are described in section 5.2. Most often syzygies are very simple expressions and already have a conservation law form. Computing conservation laws is not fully algorithmic but it is argued in section 5.1 that this task is relatively simple for under-determined systems of syzygies. 7

(35): If a conservation law for the syzygies is known then the following steps can de?nitely be performed. The question is only whether it is bene?cial for the purpose of the computation. If one has found a conservation law with only 2 components P i then the integration will introduce just one new constant and will always be bene?cial. If the conservation law has 3 or more components P i then at least one new function of all variables will be introduced. In that case, if the purpose of the integration is the solution of the PDE system (32) then one would have to balance how many functions one can solve for due to the new integrated equations (39) against how many new functions are introduced and possible decide not to continue. Examples for syzygy based integrations which are useful from the point of solving PDE-systems and others that are not are shown in section 7. If usefulness can not be decided at this stage then the integration should be performed and decided afterwards. The computational complexity of the integration, i.e. of the algorithm DivInt is very low. (36): In the computed conserved currents P i (x, ek ) we replace the equation names ek by their expressions (32) in terms of x, f α . (37): The resulting P i(x, f α ) in (36) are the input to the algorithm DivInt (given in the appendix B) to compute a special solution for the potentials Qij = Q[ij] (x, f α ) satisfying P i = Dj Qij . Here again [ij] stands for anti-symmetrization. DivInt works because the kernel of a divergence Di P i is a curl Dj Qij with Qij = ?Qji and because 0 = Di P i is satis?ed identically in all f α and their derivatives. (38): Because the syzygies 0 = ?m (x, ek ) are linear homogeneous expressions in the ek , therefore Di P i being a linear homogeneous expression in the ?m is also a linear homogeneous expression in the ek . Hence the P i are linear homogeneous expressions in the ea . Consequently, we have 0 = P i in the space of solutions of the original equations.1 (39): On the other hand, the algorithm DivInt computes expressions Qij satisfying P i = Dj Qij identically and therefore 0 = Dj Qij in the space of solutions of the original equations. The general solution of this condition for the Qij is shown in (39) and is the result of the whole computation. Its form depends on the number p of non-vanishing components P i : for p = 2 a single constant of integration R is introduced for p > 2 one or more functions Rijk (x) are introduced. (40): The formal integration of 0 = Dj Qij gives new equations whose right hand sides are abbreviated by eij . (41): We are instantly able to formulate syzygies which these new equations 0 = eij satisfy. (42),(43): If any one of them can be solved for one em (as indicated in (42)) then em = ω can be substituted in other syzygies and the original equation 0 = em (x, f α ) can be deleted as it is a consequence of the equations ek , eij in ω(x, ek , eij ,j ). (44): 1. As new syzygies have been generated in (41) there is a chance that anyone of them has already a conservation law form, like (15). 2. The substitution of a redundant equation in step (42) may also lead to a syzygy in conservation law form, either in the other newly generated syzygy or in any other syzygies.
When computing a di?erential Gr¨bner Basis the equations in the ?nal basis are also only di?erential consequences o of the initial equations and one would not want to delete them. Here the situation is di?erent. 0 = em has been integrated and can be deleted if em occurs algebraically in other syzygies.
1

8

3. Finally, there is always the possibility that the new syzygies combined with other syzygies take a conservation law form. This would have to be found out by a computation, for example using the program ConLaw. Given system: Crack → Syzygies: ConLaw → Cons. law form: Is CL useful? Conserved current: DivInt → New potentials: Integration of: to new integral(s): 0 = ek (x, f α ) 0 = ?m (x, ek ) 0 = Di P i(x, ek ), If not then stop. P i = P i (x, ek )|ek →ek (x,f α ) = P i(x, f α ) P i (x, f α ) = Dj Qij with Qij = Q[ij] (x, f α ) 0 = P i = Dj Qij R = const in 2 dim Qij (x, f α ) = ijk R ,k with Rijk = R[ijk](x) in >2 dim Qij (x, f α ) ? R Qij (x, f α ) ? Rijk ,k =: eij (32) (33) (34) (35) (36) (37) (38) (39) (40) (41) (42) (43) (44)

New equation names: 0 = New syzygies: Redundancies?

→ 0 = P i(x, ek ) ? eij ,j em = ω(x, ek , eij ,j ) → ? substitution of em = ω in any syzygy ? deleting equation 0 = em determination of conservation laws for syzygies

The continuation of the introductory example in appendix A is itemized similar to the description above. This allows the reader to go through an example and compare it with the overview step by step.

4

An integration based on curls of syzygies

The described ansatz of extracting information out of syzygies in order to do integrations is not the only possible way. In this section we want to provide a di?erent integration method, this time based on vanishing curls of syzygies. We will see that it is even more e?ective than divergence based integration but the required structure of the system of syzygies is more special which is the reason why it has not been implemented in Crack. Also, the computation of conservation laws for syzygies was implemented so far because computer programs, like ConLaw, are available to compute conservation laws and because the existence of conservation laws is a relative weak condition for syzygies. The method based on curls is shown in the following overview.

9

Given system: Syzygies: Curl free tensor: New potentials: Integration of: to new integral(s):

0 = ek (x, f α ) 0 = ?m (x, ek ) P ij = P ij (x, ek )|ek →ek (x,f α ) = P ij (x, f α ) P ij (x, f α ) = Dk Qijk with Qijk = Q[ijk](x, f α ) 0 = P ij = Dk Qijk Qijk (x, f α ) = R = const in 3 dim Rijkl ,l with Rijkl = R[ijkl](x) in >3 dim =: eijk

Vanishing curl cond.: 0 = Dj P ij with P ij = P [ij] (x, ek ),

New equation names: 0 = New syzygies: Redundancies?

Qijk (x, f α ) ? R Qijk (x, f α ) ? Rijkl ,l

→ 0 = P ij (x, ea ) ? eijk ,k em = ω(x, ek , eijk ,k ) → substitution of em ? substitution of em = ω in any syzygy ? deleting equation 0 = em determination of vanishing curls or divergences for syzygies

The super?cial di?erence between divergence and curl based integration is that P, Q, R have one extra index for the curl based method. This method also needs at least 3 independent variables. The following two examples involve each 4 independent variables and allow a closer comparison of both methods. A typical example: For 4 unknown functions a, b, c, d depending on x, y, z, t a system of 6 equations 0 = d,z ?c,t (=: exy ) , 0 = d,x ?a,t (=: eyz ) , is given. It has syzygies 0 0 0 0 = exy,y + exz,z + ext,t = ?exy,x + eyz,z + eyt,t = ?exz,x ? eyz,y + ezt,t = ?ext,x ? eyt,y ? ezt,z 0 = b,t ?d,y (=: exz ) , 0 = a,z ?c,x (=: eyt ) , 0 = c,y ?b,z (=: ext ) 0 = b,x ?a,y (=: ezt )

which take the form of a vanishing curl: 0 = Dj P ij for P ij = eij leading to potentials Qijk Qxyz = d, Qtxy = c, Qxzt = b, Qytz = a

and a single new free function of integration Rxyzt = g(x, y, z, t). The resulting integrals are a = g,x , b = g,y , c = g,z , d = g,t .

A related example for a conservation law syzygy: In comparison, the typical example using a conservation law syzygy in 4 independent variables would involve 6 unknown functions a, b, c, d, f, g and 4 equations, so a less over-determined system: 0 = a,y +b,z +c,t (=: e1 ) , 0 = ?b,x ?d,y +g,t (=: e3 ) , 10 0 = ?a,x +d,z +f,t (=: e2 ) 0 = ?c,x ?f,y ?g,z (=: e4 ).

The conservation law 0 = e1 ,x +e2 ,y +e3 ,z +e4 ,t gives P i = ei and potentials Qxy = a, The resulting integrals are a = r,z ?s,t , b = u,t ?r,y , c = s,y ?u,z , d = r,x ?w,t , f = w,z ?s,x , d = u,x ?w,y Qxz = b, Qxt = c, Qyz = d, Qyt = f, Qzt = g.

with new arbitrary functions r, s, u, w. If both methods would be applicable, i.e. if the system of syzygies would provide a vanishing divergence and a vanishing curl then one would prefer the curl based integration because it makes use of more syzygies. The last two examples look very arti?cial but one could exchange the unknown functions a, b, c, . . . by any functionally independent expressions, each of them involving at least one di?erent function, and the computations and results would be unchanged. The remainder of the paper is concerned with divergence based integration.

5

How to ?nd conservation laws of syzygies

In order to ?nd a combination of syzygies that is a divergence one could apply computer algebra programs ConLaw as described in [12], [13] by regarding the syzygies as the equations and the ea as unknown functions. In the following subsections we discuss why computing conservation laws of syzygies is simpler than computing conservation laws in general, how one can ?nd conservation laws with fewer components than independent variables and how conservation laws for syzygies are determined in Crack.

5.1

Under-determination of syzygies

α If one interprets syzygies as PDEs for unknowns ek , then the original equations ek = ek (xi , fJ ) are special solutions of these syzygies where the f α play the role of arbitrary functions in these solutions. Because at least one of the f α depends on all variables xi (otherwise the original system consists only of ISEs to be treated di?erently, not by checking integrability conditions), the syzygies must be an under-determined PDE-system for the unknowns ek . Computing conservation laws for under-determined systems of PDEs is an even more over-determined problem. The conservation law conditions have to be satis?ed identically in a jet space with coordinates xn , ea and all partial derivatives of all ea . The more ea occur in the syzygies the more restrictive are their conservation law conditions. Another way to see this is that conditions for integrating factors to give conservation laws are obtained by applying the variational derivative (Euler-Lagrange operator) to the product of integrating factors and syzygies (see [7]). Because there is one Euler operator for each ea we get as many conditions as there are di?erent ea . Finally, the more over-determined a system of conditions is, the easier it is to solve. Therefore the subtask of computing conservation laws of systems of syzygies is usually not a problem.

5.2

Choosing between di?erent syzygy conservation laws

The integration of a syzygy 0 = Di P i with two derivatives 0 = Dx P x + Dy P y is always useful but not necessarily the integration of a syzygy with more than 2 derivatives because there is at least 11

one new function of integration of all variables (see the example in section 7). Sometimes there is a choice allowing to write a syzygy in di?erent forms, for example 0 = e1 ,x +(e2 ,x )y + e3 ,z can also be written as 0 = (e1 + e2 ,y ),x +e3 ,z . To ?nd out whether a conservation law with fewer derivatives exists one has two options. First, one can make an ansatz for the conservation law with fewer derivatives and solves the resulting conditions (for example, with the programs ConLaw1 or ConLaw3). Alternatively, one computes the most general conservation law involving arbitrary functions. If a conservation law exists which does not contain derivatives Dj P j , j = m, . . . , p then 0 = Dj (CP j ), j = 1, . . . , m ? 1 is a conservation law with an arbitrary function C = C(xm , . . . , xp ). Reversely, ?nding a conservation law involving an arbitrary function C(xm , . . . , xp ) can be exploited to derive a conservation law involving no derivatives with respect to xm , . . . , xp as it is described in [10].

5.3

A faster method to ?nd conservation laws

Methods described above decide whether a conservation law can be built from syzygies, i.e. whether there is one in the di?erential ideal of the syzygies. Computations to decide this general question are potentially much more expensive than the other steps of the syzygy based integration which are all very quick. In the program CRACK therefore a di?erent, less general but much faster approach is taken. Instead of determining whether a linear combination of syzygies exists that makes up a conservation law, the program checks each individual syzygy whether it can be written as a divergence. This is done by using conventional integration to integrate the syzygy with respect to the ?rst variable, say x to obtain P x , then integrating the remainder with respect to the second variable, say y to obtain P y and so on. A divergence is obtained when no remainder remains after the last variable. To ?nd whether the syzygy can be written as a divergence with only two P i the above integration is tried at ?rst with all pairs of two independent variables. For example, in the case of syzygy (7) 0 = e2 ,yzz ?(e1 ,xx +e1 ,z ) an x-integration gives P x = ?e1 ,x . The remainder e2 ,yzz ?e1 ,z can not be completely y-integrated but z-integrated to P z = e2 ,yz ?e1 .

6

The redundancy problem

Redundant functions are unavoidably generated as soon as an equation is conventionally integrated with respect to at least two di?erent variables, for example, in the integration of 0 = A,x1 ,x2 to 0 = A + g(x1 ) + h(x2 ) where g, h depend in addition on all other independent variables occurring in the expression A. If A contains n variables x1 , . . . , xn then the arbitrariness of g and of h overlap to the extend of one function of x3 , . . . , xn . In other words, if g and h are computed from further equations then there will be one redundant function of n ? 2 variables in the solution of the original problem. Let us work out an estimate of how much redundancy is generated when integrating high order equations. If the conventional method integrates 0 = A,(x1 )m1 ,...,(xn )mn 12

to A=

n mi ?1 i=1 j=0

gij (xi ) j

where gij are free functions of all variables apart from xi then any two functions gia , gib, a = b have no overlap as their terms gia (xi )a , gib (xi )b involve di?erent powers of xi . Any other pairs of functions gab , gcd , a = c overlap. In total there is an overlap within pairs of functions gij equivalent to
n?1 n

mi × mj
i=1 j=i+1

(45)

functions of n ? 2 variables. In the introductory example the integration of 0 = f,yzz gave rise to 1 × 2 = 2 redundant functions of 3 ? 2 = 1 variable and in the ‘real-life’ application in section 9 the integration of 0 = c4 ,x3 x3 y2 y3 for c4 (t, r, x1 , x2 , x3 , y1 , y2, y3 ) generates an overlap within pairs of functions equivalent to 2 × 1 + 2 × 1 + 1 × 1 = 5 functions of 6 variables and for 0 = c4 ,x1 x2 x3 x3 x3 y1 y2 y2 even an equivalent of 21 functions of 6 variables. The overlap of two functions is partially also an overlap with other third functions and so on and should not be counted twice when trying to account exactly for all the redundancy. But this correction concerns the arbitrariness content equivalent to functions of less than n ? 2 variables so the above formula (45) is a good initial approximation of redundancy. Keeping in mind that typically a few hundred such integrations may be necessary, the severity of the problem becomes obvious. Is the redundancy problem an artifact of the chosen examples? If one determines higher order symmetries of PDEs then the symmetry conditions may be linear PDEs in, say, 30 independent variables (coordinates in jet space). Usually the general solution of this overdetermined linear PDE-system involves constants (corresponding to individual symmetries) which means that 30 conventional ‘successive layers’ of integrations would have to be done, each ‘layer’ containing integrations that express a function of n variables through functions in n ? 1 variables. In total at least several hundred integrations may become necessary. From this point of view the above mentioned application in section 9 to compute c4 is typical. Could redundancy be prevented otherwise? Partial di?erential equations may contain symmetries involving arbitrary functions but if not then the general solution of the symmetry conditions contains only constants. In that case choosing a strictly lexicographical ordering of derivatives in the elimination process the di?erential Gr¨bner o basis will involve ordinary di?erential equations (ODEs). They may not be in the form of total derivatives but at least in case they could be integrated, the redundancy problem would not appear as each ODE is integrated with respect to only one independent variable. The drawback is that Gr¨bner Basis computations are well known to be computationally much more expensive when o performed with a lexicographical ordering of variables than when performed using a total degree ordering of variables. A total degree ordering will provide shorter equations of lower di?erential order but with mixed derivatives, leading to redundancy with conventional integration. The conclusion is that even in the special cases where the general solution of the linear PDE system contains essentially only constants, the syzygy based integration is superior allowing to use elimination schemes with total degree orderings that are more e?cient than schemes using strictly lexicographical ordering and still being able to reduce the redundancy problem. Does syzygy based integration cure the redundancy problem completely? In the course of one syzygy based integration all equations 0 = P i are integrated at once one time. If 0 = P i (ej ) is equivalent to the whole system 0 = ek , or, like in the introductory example (4),(5) where successive syzygy based integration integrates the system, then redundancy is avoided. If, 13

on the other hand, only a subsystem of equations 0 = ek is involved in 0 = P i (ej ) and the result of a syzygy based integration has to be substituted in other equations then redundancy may still appear as recorded in table 1 in section 9.2 but to a clearly lesser extend. Is there another way to determine redundant functions or constants in order to delete them? In computations where each free constant in the solution of an overdetermined PDE-system corresponds to a symmetry or to a conservation law one is interested to determine and drop redundancy in order to get an accurate account of their number. For this purpose a method has been developed (see [13]) but this requires the solution of an overdetermined PDE-system on its own and may therefore be expensive.

7

Cases when a syzygy based integration is not useful

When applying the new integration method to solve a PDE-systrem it not only matters whether all steps are algorithmic but also whether its execution is bene?cial. Information contained in syzygies is useful if it provides a factorization of di?erential operators. If they do not factorize (for example, if they are of ?rst order) then a syzygy based integration can still be useful if more functions are solved for than new functions are introduced. If the divergence Di P i contains more than two derivatives, i.e. the conserved current P i has more than 2 components, then the integral equations (39) contain at least one new function Rijk of all variables and we may not gain new information from the integration if we can not solve for at least 2 functions. This is demonstrated in the following series of 3 examples with successively more functions to be solve for and an increasing usefulness of the integration. Example: When computing the Gr¨bner basis of the two equations o 0 = f,x +f,y 0 = f,z (=: e1 ) (=: e2 ) (46) (47)

for a function f = f (x, y) (and in doing that con?rming that they are already a Gr¨bner basis) one o will generate the identity 0 = e2 ,x +e2 ,y ?e1 ,z . (48) From identifying P x = e2 from (48) and the general formula P x = Dy Qxy + Dz Qxz together with (47) we identify Qxy = 0, Qxz = f, Qyz = f . With the new function Rxyz = c(x, y, z) substituted into the formula Qij = Rijk ,k the new equations are 0 = c,z 0 = f ? c,x 0 = f + c,y . (49) (50) (51)

After a substitution of f from (50) into (51) they are identical to the original set (46), (47), only now for a function c instead of f . No progress was made. In contrast, for the following two similar examples the integration of syzygies is advantageous. Example: For the equations 0 = f,x +g,y 0 = f,z 0 = g,z 14 (=: e1 ) (=: e2 ) (=: e3 ) (52) (53) (54)

the identity 0 = e2 ,x +e3 ,y ?e1 ,z results. Integrated in the above manner it gives 0 = c,x +g 0 = ?c,y +f 0 = c,z (56) (57) (58) (55)

leaving only equation (58) for c = c(x, y, z) to be solved, an improvement compared to the original system (52) – (54). In the next example no equations remain to be solved. Example: For the equations 0 = h,y ?g,z 0 = f,z ?h,x 0 = g,x ?f,y the identity 0 = e1 ,x +e2 ,y +e3 ,z leads to 0 = f + c,x 0 = g + c,y 0 = h + c,z (63) (64) (65) (62) (=: e1 ) (=: e2 ) (=: e3 ) (59) (60) (61)

with an arbitrary function c = c(x, y, z) and no remaining equation. In order to incorporate this method of integration into a general program for solving overdetermined systems the usefulness of integration has to be judged automatically based on the number of derivatives in the divergence and the number of functions solved for. But also other adjustments to the whole program have to be made. These are discussed in the following short section.

8

Implementation

Apart from the implementation of the algorithm DivInt as shown in the appendix B, also changes to the package Crack were needed in order to automate syzygy based integrations. When checking integrability conditions in a Gr¨bner basis computation the program had to keep track of any o resulting identities (syzygies). This was done in the following way which is conceptually the same as the extended Buchberger algorithm (see, for example, the books [1] and [5]). To each equation, for example e3 in (6), we will assign not only a value, like f,yzzz , but also, what we will call a ‘history-value’ or short ‘history’, i.e. e2 ,yzz ?e1 ,xx . This history of an equation expresses one equation in terms of other equations, i.e. how it was historically computed doing the algebraic or di?erential Gr¨bner basis computation. At the beginning the history of each equation o ea is ea itself. Whenever a new equation is computed then not only its value but also its history is calculated. For example, when in this example f,yzzz is eliminated from equation (6) using equation (4) then a new equation 0 = e4 is generated where e4 has the value 0 (as all terms cancel) and has 15

the history value e3 ? e1 ,z where e3 and e1 are replaced by their history values. The history of e1 is e1 whereas the history of e3 is e2 ,yzz ?e1 ,xx giving for e4 the history e2 ,yzz ?e1 ,xx ?e1 ,z as is shown in (7). In the next section a substantial application is described which is suitable to demonstrate the advantages of the new integration method.

9
9.1

The application that led to the development of the syzygy based integration
The problem

A problem introduced to the author by Stephen Anco concerns the computation of all conservation laws of the radial SU(2) chiral equation in 2 spatial dimensions where the integrating factors are of at most 2nd order. The equation can be written as a ?rst order system for two 3-component vectors j(r,t), k(r,t): k,t = j,r + j × k j,t = (rk),r /r. Equation (67) is already in conservation law form: (rj),t +(?rk),r = 0 and the only other known conservation law (of energy) has zeroth order integrating factors: rk · [k,t ?j,r ?j × k] + j · [j,t ?(rk),r /r] = r (j · j + k · k) ,t + (?rj · k) ,r = 0 2 (68) (66) (67)

The existence conditions for conservation laws below were generated with the program ConLaw2 described in [12]. It generates conditions for 6 integrating factors Q1 , . . . , Q6 (like the multipliers rk1, rk2 , rk3 , j1 , j2 , j3 on the left hand side of (68)). Each of the Qi is an unknown function of 20 independent variables t, r, j, k, l (= j,r ), m (= k,r ), u (= j,rr ), w (= k,rr ). The system consists of 18 conditions of the form 0 = Q1 ,u1 ?Q4 ,w1 r and 6 conditions of the form
0 = Q3 ,j1 l1 r2 + Q3 ,l1 u1 r2 + Q3 ,j2 l2 r2 + Q3 ,l2 u2 r2 + Q3 ,j3 l3 r2 + Q3 ,l3 u3 r2 + Q3 ,k1 m1 r2 + Q3 ,m1 w1 r2 +Q3 ,k2 m2 r2 + Q3 ,m2 w2 r2 + Q3 ,k3 m3 r2 + Q3 ,m3 w3 r2 + Q3 ,r r2 ? Q6 ,j1 k1 r2 ? Q6 ,j1 m1 r3 + Q6 ,l1 k1 r ?Q6 ,l1 m1 r2 ? Q6 ,l1 w1 r3 ? 2Q6 ,u1 k1 + 2Q6 ,u1 m1 r ? Q6 ,u1 w1 r2 ? Q6 ,j2 k2 r2 ? Q6 ,j2 m2 r3 + Q6 ,l2 k2 r ?Q6 ,l2 m2 r2 ? Q6 ,l2 w2 r3 ? 2Q6 ,u2 k2 + 2Q6 ,u2 m2 r ? Q6 ,u2 w2 r2 ? Q6 ,j3 k3 r2 ? Q6 ,j3 m3 r3 + Q6 ,l3 k3 r ?Q6 ,l3 m3 r2 ? Q6 ,l3 w3 r3 ? 2Q6 ,u3 k3 + 2Q6 ,u3 m3 r ? Q6 ,u3 w3 r2 ? Q6 ,k1 l1 r3 ? Q6 ,k1 j2 k3 r3 + Q6 ,k1 j3 k2 r3 ?Q6 ,m1 u1 r3 ? Q6 ,m1 j2 m3 r3 ? Q6 ,m1 l2 k3 r3 + Q6 ,m1 j3 m2 r3 + Q6 ,m1 l3 k2 r3 ? Q6 ,w1 j2 w3 r3 ? 2Q6 ,w1 l2 m3 r3 ?Q6 ,w1 u2 k3 r3 + Q6 ,w1 j3 w2 r3 + 2Q6 ,w1 l3 m2 r3 + Q6 ,w1 u3 k2 r3 + Q6 ,k2 j1 k3 r3 ? Q6 ,k2 l2 r3 ? Q6 ,k2 j3 k1 r3 +Q6 ,m2 j1 m3 r3 + Q6 ,m2 l1 k3 r3 ? Q6 ,m2 u2 r3 ? Q6 ,m2 j3 m1 r3 ? Q6 ,m2 l3 k1 r3 + Q6 ,w2 j1 w3 r3 + 2Q6 ,w2 l1 m3 r3 +Q6 ,w2 u1 k3 r3 ? Q6 ,w2 j3 w1 r3 ? 2Q6 ,w2 l3 m1 r3 ? Q6 ,w2 u3 k1 r3 ? Q6 ,k3 j1 k2 r3 + Q6 ,k3 j2 k1 r3 ? Q6 ,k3 l3 r3 ?Q6 ,m3 j1 m2 r3 ? Q6 ,m3 l1 k2 r3 + Q6 ,m3 j2 m1 r3 + Q6 ,m3 l2 k1 r3 ? Q6 ,m3 u3 r3 ? Q6 ,w3 j1 w2 r3 ? 2Q6 ,w3 l1 m2 r3 ?Q6 ,w3 u1 k2 r3 + Q6 ,w3 j2 w1 r3 + 2Q6 ,w3 l2 m1 r3 + Q6 ,w3 u2 k1 r3 ? Q6 ,t r3 ? k1 Q2 r2 + k2 Q1 r2

16

After introducing new unknown functions xi , yi through ui = xi + yi , wi = xi ? yi the 18 short equations took the form of a total derivative and each one could be integrated on its own but when the computed functions were substituted only indirectly separable equations (ISEs) like (22) were obtained.2 Despite of the initial success in performing these integrations all attempts to complete the solution of the over-determined system failed with the 1999 version of Crack. That this was not simply a matter of lacking computing power became obvious after extracting a small sub-system of equations for only one of the unknown functions3 c4 (t, r, x1 , x2 , x3 , y1 , y2, y3 ) where some of the equations are easy to integrate: 0 = = = = = = = = c4 ,x3 x3 y2 y3 = c4 ,x1 x2 y1 y3 y3 = c4 ,x1 x2 y1 y1 y3 = c4 ,x1 x2 x3 y1 y1 = c4 ,x2 x3 x3 x3 y1 y1 y3 c4 ,x1 x2 x3 x3 x3 y1 y2 y2 = c4 ,x1 x2 x2 x3 y1 y1 y2 y2 = c4 ,x1 x2 x3 x3 y3 y3 y3 ?c4 ,x2 x3 x3 x3 y1 y3 y3 c4 ,x1 x2 x3 x3 y1 y2 y2 ?2c4 ,x1 x2 x2 x3 y1 y2 y3 = c4 ,x1 x2 x3 x3 y1 y2 ?2c4 ,x1 x2 x2 x3 y1 y3 ?c4 ,x1 x2 x2 x3 x3 y1 y3 x3 c4 ,x1 x2 x3 x3 x3 y1 y3 x1 ? c4 ,x1 x2 x3 x3 y3 y3 +c4 ,x2 x3 x3 x3 y1 y3 c4 ,x3 x3 x3 y1 y3 x1 + c4 ,x3 x3 y1 y3 y3 y1 ? c4 ,x3 x3 y3 y3 (69) c4 ,x1 x2 x3 x3 y1 y2 y2 y2 y3 + 2c4 ,x1 x2 x2 x2 y1 y2 y3 ?2c4 ,x1 x2 x2 x3 y1 y2 y2 +c4 ,x1 x2 x2 x3 x3 y1 y2 y2 x3 c4 ,x1 x2 x3 x3 y1 y2 y2 y3 + 2c4 ,x1 x2 x2 x2 x3 y1 y3 x3 + 2c4 ,x1 x2 x2 x2 y1 y3 ?2c4 ,x1 x2 x2 x3 y1 y2 c4 ,x1 x2 x3 x3 x3 y1 y2 x1 x3 ? 3c4 ,x1 x2 x3 x3 y1 y2 x1 + 6c4 ,x1 x2 x2 x3 y1 y3 x1 ?c4 ,x1 x2 x2 x3 x3 y3 y3 x2 + c4 ,x2 x2 x3 x3 x3 y1 y3 x2 3 3

Even the solution or at least simpli?cation of this sub-system was not possible. The problem was not to ?nd equations with the form of a total derivative and to integrate them. The problem was the growing number of new functions of integration (which did still depend on 7 variables) and the appearance of too many only indirectly separable equations (ISEs). Since 1999 the module for handling ISEs has been improved considerably. The current version of Crack (Dec. 2001) can simplify the above system quickly using the conventional integration of total derivatives. Nevertheless, by adding the ability of performing syzygy based integrations the computation speeds up further and the solution involves fewer redundant arbitrary functions. Tests described below show that syzygy based integrations are well suited to be performed along the computation of a di?erential Gr¨bner basis without the negative side e?ect of introducing too o many redundant functions. By that Gr¨bner basis computations can be cut short and the risk of a o memory explosion be lowered.

9.2

A comparison of three computer runs

Before describing the details of 3 di?erent computer runs, a few comments about the setup have to be made. The package Crack for solving and simplifying over-determined PDE-systems contains about 30 modules for di?erent actions to be taken either with individual equations or with groups of equations of the system. Modules used to solve systems like (69) are 1. Direct separation of an equation with respect to some variable that occurs only explicitly in the equation.
Although each of the ISEs is over-determined on its own, this over-determination can not be utilized easily because there is no independent variable which occurs only explicitly that would lead to direct separations. 3 New constants and functions of integration are all called ci in Crack with successively increasing subscript.
2

17

2. Substitution of a function f either by zero or by at most 2 terms and only if other functions occurring in these 2 terms depend on fewer variables than f . 3. Integration of an equation if it consists of a single derivative with respect to only one variable. 4. Elimination of a function f from any equation if f occurs only algebraically and linearly and if f depends on all variables occurring in this equation. Substitution of f in all other equations. 5. Deleting of any redundant equations as described on the bottom of the overview in section 3. 6. Integration based on a syzygy in conservation law form. 7. Conventional integration of a PDE but only if su?ciently many integrations are possible such that the integrated equation can be used for a substitution. 8. Indirect separation of an equation (ISE). (This is a complex step which can invoke other direct separations and indirect separations of resulting equations.) 9. Reduction of the leading derivative of one equation with the help of another equation or formulation of an integrability condition between two equations. (This is a typical step in a Gr¨bner basis computation.) o 10. Any integration of any equation even if not complete. These modules are called in a speci?c sequence which can be chosen by specifying a list of numbers, each number representing one module. For example, if in table 1, column 2 the priority list of run 1 is chosen to be 1 2 3 4 8 9 7 10 then the modules as numbered above are tried in this order until one module is successful and then they are again tried beginning with 1 and so on. This is only a simpli?ed description of the operation of Crack but it is su?cient for the purpose of this section.
run 1 2 3 priority list of actions 1 2 3 4 8 9 7 10 1 2 3 4 7 8 9 10 1 2 3 4 5 8 6 9 7 10 # of steps 1077 1175 362 time in sec 124 122 23 # of terms in equ. (71) 6 12 8 # of redundant functions of 6 var. of 5 var. of 4 var. of 7 16 2 4 45 23 2 19 2 3 var. 0 5 0

Table 1. A comparison of three di?erent runs on the system (69).

In table 1 three computer runs are compared. Column 3 gives the number of successful calls of the modules in the priority lists. Times shown in column 4 have been measured in a session of the computer algebra system REDUCE version 3.7 with 120 MByte memory (although only a few MByte are needed for this computation) on a 1.7 GHz PC Pentium 4 under Linux. Column 5 gives the number of terms in the single unsolved equation which in the solution (70) below is the equation (71). In the remaining 4 columns the number of redundant functions of 6, 5, 4, or 3 variables is shown. For example, if two functions f (x, y, z) and zg(x) occur always together such that a substitution f + zg → f has the same e?ect as g → 0 then g can be set to zero without loss of generality.

18

9.3

Conclusions from the test

The central issue in these runs is, whether integrations (modules 6 and 7) are given a higher priority than the formulation of integrability conditions (module 9) or a lower priority. If integrability conditions have a higher priority than integrations, as in run 1, then at ?rst a complete di?erential Gr¨bner basis is computed before integrations start. The bene?t is that the di?erential order of o equations is as low as possible when integrations start (assuming a total degree ordering is used in the di?erential Gr¨bner basis computation). Consequently fewer integrations are necessary and o fewer functions will be generated which turn out later to be redundant. The disadvantage is that the computation of integrability conditions may take very long and blow up the systems size, or may even be practically impossible. One can attempt to give integrations a higher priority at the price of more redundant functions in the solution. This was done in run 2. The bene?t may be considerable, only in our small system (69) the Gr¨bner basis computation is not expensive at all, so the advantage of early integrations o does not become obvious here. But the disadvantage becomes obvious. Integrating higher order equations generates more new functions with many of them turning out to be redundant at the end. Finally, in the third run we get the best of both previous runs. Here, early integrations use syzygies in conservation law form as soon as they become available. The lowered di?erential order of equations reduces the complexity of the remaining Gr¨bner basis computation. Also, because o i with each integration at least 2 equations 0 = P are satis?ed, the number of new functions of integration is low and the number of variables these functions depend on is reduced. Consequently, only few functions turn out to be redundant in the computed solution as seen in columns 6-9 of table 1. The following solution is obtained in run 3 after redundant functions have been deleted (by hand) leaving 11 functions of 6 variables, 8 functions of 5 variables and 2 functions of 4 variables. It is equivalent to the solutions returned in runs 1 and 2.
2 1 c4 = c100 ,x2 x3 y1 y2 + 2 c100 ,x3 x1 y3 + c125 , x2 x2 y1 + c125 ,y2 x3 y1 y3 + c133 ,x2 x3 y1 + c133 ,y2 y1 y3 3 +c213 ,x3 x1 + c213 ,y3 y1 + c100 y1 y3 ? c109 x2 x3 y1 + c170 + c172 + c173 x3 + c181 y3 + c191 (70) ?c192 ? c193 x3 ? c194 + c200 + c205 ? 1 c65 x2 y3 ? c81 x3 ? c83 3 2

All functions depend on t, r and in addition on further variables in the following way: c83 (x2 , x3 , y1 , y2), c81 (x2 , y1, y2 , y3 ), c173 (x1 , x2 , y2 , y3 ), c172 (x1 , x2 , y2 , y3), c170 (x1 , x2 , x3 , y2 ), c194 (x1 , x3 , y1 , y3 ), c193 (x1 , y1 , y2 , y3), c192 (x1 , y1 , y2 , y3), c191 (x1 , x3 , y1, y2 ), c205 (x2 , y1 , y2, y3 ), c200 (x1 , x2 , y1 , y2 ), c100 (x1 , x2 , x3 ), c125 (x1 , x2 , y2), c133 (x1 , x2 , y2 ), c181 (x1 , x2 , x3 ), c213 (x2 , x3 , y3 ), c230 (x1 , y1, y3 ), c229 (x1 , y1, y3 ), c228 (x1 , x3 , y1), c65 (x2 , y1), c109 (x1 , y2 ). The function c194 has to satisfy the condition 0 = c194 ,x3 y1 x1 + c194 ,y1 y3 y1 ? c194 ,y3 ?c228 ? c229 ? c230 x3 , (71)

all other functions are free. The result of the conservation law investigation for the SU(2) chiral equation in the form (66), (67) is that no other conservation laws with integrating factors of at most 2nd order exist. More remarks concerning the collaboration of modules: ? Syzygy based integration can not replace conventional integration. If equations become decoupled then no integrability conditions apply and the equations have to be integrated conventionally if possible. 19

? The usefulness of conventional integration relies very much on the e?ciency of a module for the indirect separation (module 8 in the above list). The corresponding implementation in Crack will be described elsewhere. ? The issue of avoiding redundant functions is serious when a system like (69) is only a subsystem of a larger system and the solution of the smaller system is to be substituted in the larger one. Redundant functions would complicate the solution of the larger system unnecessarily. On the other hand, the identi?cation and deletion of redundant functions using a method described in [13], is di?cult and may be more expensive than the solution/simpli?cation of the system itself. This method does not prevent redundancy, it only can identify it in the solution. The package Crack is distributed together with the computer algebra system REDUCE. A newer version can be down-loaded from http://lie.math.brocku.ca/twolf/crack.

10

Summary

An integration method has been proposed that is applicable for linear PDE-systems that admit syzygies, i.e. systems which are overdetermined as a whole or contain an overdetermined subsystem. It therefore can not replace the straight forward integration of exact PDEs but when applicable it has a number of advantages: ? The information on which the integration is based is taken from syzygies in conservation law form. Syzygies are a by-product of the computation of di?erential Gr¨bner Basis. o ? Because not a single equation is integrated but a number of equations (0 = P i ) at once, fewer functions of integration, depending on fewer variables are introduced in the process. ? The problem of conventional integration to introduce redundant functions when integrating with respect to di?erent variables is either prevented or signi?cantly reduced. ? The new integration produces apart from integrated equations also new syzygies which are often the basis for continuing the integration further without having to compute new syzygies through a new Gr¨bner basis computation. o ? Syzygy based integration, conventional integration and elimination complement one another well in solving overdetermined linear PDE-systems if given the right priorities.

20

Appendix A: Continuation of the introductory example
In this appendix we continue the introductory example by performing three more syzygy based integration steps. The computation is broken up into items. The number(s) at the start of each item refer to the line number of the corresponding step in the overview at the end of section 3. (32): The remaining system to solve consists of 0 = f,xx +f,z 0 = f,xyz ?c1 . (= e2 ) (= e4 )

(33),(34): satisfying the identity in conservation law form 0 = (?e4 ,x ),x + (e2 ,xy ?e4 ),z (35): with only 2 derivatives. (36): Proceeding as in the ?rst integration step we now identify as the conserved current ? ? P x = ?e4 ,x = ?f,xxyz = ?Q,z ? ? P z = e2 ,xy ?e4 = f,xxxy +c1 = Q,x (72) (73)

? (37): and as the new potential Q we either identify or compute using algorithm DivInt in appendix B ? Q = f,xxy +xc1 (39),(40): giving the new equation ? 0 = Q ? c2 = f,xxy +xc1 ? c2 with the new function of integration c2 = c2 (y). (41),(42): Equation e4 is redundant as it turns up purely algebraically in ? ? 0 = P z ? Q,x = e2 ,xy ?e4 ? e5 ,x . (43): Substitution of e4 in (72) gives the new identity 0 = ?e2 ,xxy +e5 ,xx +e5 ,z . (36): This is as well a divergence with only two terms ? ? P x = ?e2 ,xy +e5 ,x = ?f,xyz +c1 = ?Q,z ? ? P z = e5 = f,xxy +xc1 ? c2 = Q,x ? (37): and the new potential Q x ? Q = f,xy + c1 ? xc2 ? zc1 2 21
2

(=: e5 )

(74)

(75)

(76) (77)

(39),(40): giving the new equation ? 0 = Q ? c3 = f,xy + x2 c1 ? xc2 ? zc1 ? c3 2 (=: e6 ) (78)

with the new function of integration c3 = c3 (y). (41),(42): Now, equation e5 is redundant as it turns up purely algebraically in ? ? 0 = P z ? Q,x = e5 ? e6 ,x . (43): Substitution of e5 in (76) gives the new identity 0 = ?e2 ,xy +e6 ,xx +e6 ,z . (79)

(36): This is a divergence as well and we will perform the integration cycle one more time with ˇ ˇ P x = ?e2 ,y +e6 ,x = ?f,yz +xc1 ? c2 = ?Q,z x2 ˇ ˇ P z = e6 = f,xy + c1 ? xc2 ? zc1 ? c3 = Q,x 2 ˇ (37): and the new potential Q x2 x3 ˇ Q = f,y + c1 ? c2 ? xzc1 + zc2 ? xc3 6 2 (39),(40): giving the new equation ˇ 0 = Q ? c4 = f,y + x3 x2 c1 ? c2 ? xzc1 + zc2 ? xc3 ? c4 6 2 (=: e7 ) (82) (80) (81)

with the new function of integration c4 = c4 (y). ˇ (41),(42): Now, equation e6 is redundant as it turns up purely algebraically in P z in (81) ˇ ˇ 0 = P z ? Q,x = e6 ? e7 ,x . (43): Substitution of e6 in (80) gives the new identity 0 = ?e2 ,y +e7 ,xx +e7 ,z . (83)

The conclusion of this example is shown in section 2.1 below equation (20). As argued there the syzygy based integration of equation (83) is not advantageous as (83) has a conservation law form with 3 derivatives instead of two. Instead one rather integrates (82) with respect to y and substitutes f in the remaining equation (5).

22

Appendix B: The algorithm DivInt
α The following algorithm computes expressions Qij (xn , fJ ) = Q[ij] that satisfy Dj Qij = P i. The α α given P i = P i (xn , fJ ) are assumed to satisfy Di P i = 0 identically in all fJ .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

Algorithm DivInt α Input variables: xn , functions: f α and conserved current: P i = P i (xn , fJ ) ij n α ij i Output Q (x , fJ ), j > i % satisfying Dj Q = P , E, F % E : list of new additional equations % F : list of new additional functions Body % no summation over double indices below ij E := {}, F := {}, Q := 0, with i, j ∈ 1, . . . , p, j > i % Integrate all terms with functions f α depending on all variables for i := 1 to (p ? 1) do for j := i + 1 to p do α while P i contains a term aiJ ?j fJ do % i.e. while any derivative of any f α % occurs that involves ?j i i iJ α P → P ? Dj (a fJ ) α P j → P j + Di (aiJ fJ ) ij ij iJ α Q → Q + a fJ % Integrate all derivatives involving functions f α not depending on all variables for i := 2 to p do for j := 1 to i ? 1 do α while P i contains a term aiJ ?j fJ do % i.e. while any derivative of any f α % occurs that involves ?j i i iJ α P → P ? Dj (a fJ ) α Qji → Qji ? aiJ fJ % Integrate remaining terms for i := 1 to p do if P i = 0 then α % integrate each term aiJ fJ of P i with respect to any one xj = xi % preferably one xj with ?j f α = 0 in the following way: if ?j f α = 0 then α q := fJ aiJ dxj P i → P i ? Dj q if j > i then Qij → Qij + q else Qji → Qji ? q else Introduce a new function f β (x1 , . . . , xi?1 , xi+1 , . . . , xp ) F → F ∪ {f β } α E → E ∪ {0 = ?j f β ? aiJ fJ } α P i → P i ? aiJ fJ if j > i then Qij → Qij + f β else Qji → Qji ? f β α return Qij (xn , fJ ), E (list of new equations), F (list of new functions) 23

Explanation of the algorithm Lines 9 - 16 α This part of the procedure is su?cient if the input expressions P i (xn , fJ ) do only contain functions α 1 p f depending on all p independent variables x , . . . , x . A typical example: If an expression P y contains a term f,z then Dy P y (no summation) contains ?y f,z which has to be cancelled by ??z f,y from Dz P z (no summation) to give 0 = Dk P k (summation) identically in all fJ . This means P z contains ?f,y . In this short example the lines 14 - 16 would subtract f,z from P y , subtract ?f,y from P z and add f to Qyz . There is no principal di?erence α between P y containing a term f,z or P y containing aiJ ?z fJ . As both, P i and P j are updated in lines 14 and 15, j does not run over indices 1 . . . i?1. Because Qii = 0 (Qij is antisymmetric) there is no need to integrate an i-derivative in P i and therefore j starts from i + 1 in line 11. If all terms in all P i contain a function f α of all variables then any term in any Qij occurs twice, once with an xj -derivative in P i and once as negative xi -derivative in P j . When the program completed lines 10 - 16, all P i have the value zero and the solution Qij is found (for i < j, values for Qji follow from the antisymmetry). Lines 18 - 42 The only possibility that after completing lines 10 - 16 not all P i are already zero occurs if some f α do not depend on all variables. That is, for example, the case if functions entered the problem due to running DivInt previously in earlier integrations. In general, if terms remain in some P i which necessarily depend on less than all variables then one can always complete the integrations by introducing new functions (collected in a list F in line 38) that have to satisfy additional equations (collected in a list E in line 39). In order to minimize the number of additional functions and additional equations the lines 19 - 24 integrate terms that are xj -derivatives in P i (j = i) and lines 31 - 35 integrate terms by changing the explicit appearance of xj . This is shown in the following examples. Example: Independent variables: x, y, z, initial values: P x = A(y, z),y +B(y, z),z +C(y, z) + D(y) + G(z) P y = H(x, z),x +K(x, z),z +L(x) + M(x, z) + N(z) P z = R(x, y),x +S(x, y),y +T (x) + U(y) + W (x, y) Qxy = Qxz = Qyz = 0 containing undetermined functions A, B, C, D, G, H, K, L, M, N, R, S, T, U and W . After completing the program up to line 18 the values are Px Py Pz Qxy Qxz Qyz = = = = = = C(y, z) + D(y) + G(z) H(x, z),x +L(x) + M(x, z) + N(z) R(x, y),x +S(x, y),y +T (x) + U(y) + W (x, y) A(y, z) B(y, z) K(x, z).

After completing the program up to line 26 the values are P x = C(y, z) + D(y) + G(z) 24

Py Pz Qxy Qxz Qyz

= = = = =

L(x) + M(x, z) + N(z) T (x) + U(y) + W (x, y) A(y, z) ? H(x, z) B(y, z) ? R(x, y) K(x, z) ? S(x, y).

The loop beginning in line 27 will integrate the remaining terms in P i . The lines 32 - 35 will integrate the terms D, G, L, N, T, U and lines 37 - 42 the terms C, M, W to obtain Qxy Qxz Qyz Px = Py = Pz = 0 = A(y, z) ? H(x, z) + yG(z) ? xN(z) + F 1 (y, z) = B(y, z) ? R(x, y) + zD(y) ? xU(y) ? F 3 (x, y) = K(x, z) ? S(x, y) + zL(x) ? yT (x) + F 2 (x, z)

with a list F of new additional functions F 1 (y, z), F 2(x, z), F 3 (x, y) and list E of new additional equations F 1 (y, z),y = C(y, z) F 2 (x, z),z = M(x, z) F 3 (x, y),x = W (x, y) each in less than 3 variables.

References
[1] T. Becker and V. Weispfenning. Groebner bases. Springer Verlag, 1993. [2] F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Computing representations for radicals of ?nitely generated di?erential ideals. In Proceedings of ISSAC 95, pages 158–166. ACM Press, 1995. [3] E. Hubert. Essential components of algebraic di?erential equations. J. of Symb. Comp., 28(45):657–680, 1999. [4] E. Hubert. Factorisation free decomposition algorithms in di?erential algebra. J. of Symb. Comp., 29(4-5), 2000. [5] M. Kreuzer and L. Robbiano. Computational Commutative Algebra 1. Springer Verlag, 2000. [6] E.L. Mans?eld. The di?erential algebra package di?grob2. Mapletech, 3:33–37, 1996. [7] P. J. Olver. Applications of Lie Groups to Di?erential Equations, volume 107 of gtm. Springer Verlag, New York-Berlin-Heidelberg-Tokyo, 1986. [8] G.J. Reid, A.D. Wittkopf, and A. Boulton. Reduction of systems of nonlinear partial di?erential equations to simpli?ed involutive forms. Europ. J. of Appl. Math., 7:604–635, 1996. [9] T. Wolf. The program crack for solving PDEs in general relativity. In F.W. Hehl, R.A. Puntigam, and H. Ruder, editors, Relativity and Scienti?c Computing: Computer Algebra, Numerics, Visualization, pages 241–251. Springer Verlag, 1996. 25

[10] T. Wolf. A linearization of PDEs based on conservation laws. preprint, 1999. [11] T. Wolf. The symbolic integration of exact PDEs. J. Symb. Comp., 30(5):619–629, 2000. [12] T. Wolf. A comparison of four approaches to the calculation of conservation laws. Euro. Jnl of Applied Mathematics, 13 part 2:129–152, 2002. [13] T. Wolf, A. Brand, and M. Mohammadzadeh. Computer algebra algorithms and routines for the computation of conservation laws and ?xing of gauge in di?erential expressions. J. Symb. Comp., 27:221–238, 1999.

26