CRACK: Solving Overdetermined Systems of ODEs or PDEs

REDUCE

20.15 CRACK: Solving Overdetermined Systems of ODEs or PDEs

CRACK is a package for solving overdetermined systems of diﬀerential equations. Examples of programs which make use of CRACK (ﬁnding symmetries of ODEs/PDEs, ﬁrst integrals, an equivalent Lagrangian or a “diﬀerential factorization” of ODEs) are included. The packages APPLYSYM and CONLAW use CRACK.

Authors: Andreas Brand, Thomas Wolf

20.15.1 Introduction

Purpose

The package CRACK attempts the solution of an overdetermined system of algebraic, ordinary or partial diﬀerential equations (ODEs/PDEs) with at most polynomial nonlinearities.

Under ‘normal circumstances’ diﬀerential equations (DEs) which describe physical processes are not overdetermined, i.e. the number of DEs matches the number of unknown functions which are involved. Although CRACK may be successful in such cases (e.g. for characteristic ODE-systems of ﬁrst order PDEs) this is not the typical application. It is rather the qualitative investigations of such diﬀerential equations, i.e. the investigation of their inﬁnitesimal symmetries (with LIEPDE and APPLYSYM) and conservation laws (with CONLAW) which result in over-determined systems which are the main application area of CRACK.

Interactivity

The package was originally developed to run automatically and eﬀort was made for the program to decide which computational steps are to be done next with a choice among integrations, separations, substitutions and investigation of integrability conditions. It is known from hand computations that the right sequence of operations with exactly the right equations at the right time is often crucial to avoid an explosion of the length of expressions. This statement keeps its truth for the computerized solution of systems of equations as they become more complex. As a consequence more and more interactive access has been provided to inspect data, to specify how to proceed with the computation and how to control it. This allows human intervention in critical stages of the computations (see the switch off batch_mode below).

General Structure

A problem consists of a system of equations and a set of inequalities. With each equation are associated a short name and numerous data, like size, which functions, derivatives and variables occur but also which investigations have already been done with this equation and which not in order to avoid unnecessary duplication of work. These data are constantly updated if the equation is modiﬁed in any way.

A set of about 30 modules is available to integrate, substitute, decouple, … equations. A complete list can be inspected in interactive mode with the command p2, which lists each operation with the number by which it is called. All modules can be called interactively or automatically. Automatic computation is organized by a priority list of modules (each represented by a number) where modules are invoked in the order they appear in the priority list, each module trying to ﬁnd equations in the system it can be applied to. The priority list can be inspected with the command p1. If a module is not successful then the next module in the list is tried; if any one is successful then execution starts again at the beginning of the priority list. See the Reference subsection below for further details.

Because each module has access to all the data, it is enough to call a module by its number. For example, inputting the number 2 in interactive mode will start the direct separation module (see below) to look for a directly separable equation and split it.

20.15.2 Syntax

The call

CRACK is called by

crack(	{equ$_1$, equ$_2$, …, equ$_m$},
	{ineq$_1$, ineq$_2$, …, ineq$_n$},
	{fun$_1$, fun$_2$, …, fun$_p$},
	{var$_1$, var$_2$, …, var$_q$});

where $m,n,p,q$ are arbitrary.

The equ$_i$ are identically vanishing partial diﬀerential expressions, i.e. they represent equations $0 = \mathit {equ}_i$, which are to be solved for the functions fun$_j$ as far as possible, thereby drawing only necessary conclusions and not restricting the general solution.
The ineq$_i$ are algebraic or diﬀerential expressions which must not vanish identically for any solution to be determined, i.e. only such solutions are computed for which none of the expressions ineq$_i$ vanishes identically in all independent variables.
The dependence of the (scalar) functions fun$_j$ on independent variables must be deﬁned beforehand with depend rather than declaring these functions as operators. Their arguments may themselves only be identiﬁers representing variables, not expressions. Also other unknown functions not in fun$_j$ must not be represented as operators but only declared using depend.
The functions $\textit {fun}_j$ and their derivatives may only occur polynomially.
The $\textit {var}_k$ are further independent variables, which are not already arguments of any of the $\textit {fun}_j$. If there are none then the fourth argument is the empty list {}, although it does no harm to include arguments of functions $\textit {fun}_j$.
The dependence of the $\textit {equ}_i$ on the independent variables and on constants and functions other than $\textit {fun}_j$ is arbitrary.
CRACK can be run in automatic batch mode (the default) or interactively with the switch setting off batch_mode.

The result

The result is a list of solutions

\[ \{\textit {sol}_1, \ldots \}, \]

where each solution is a list of 4 lists

\[ \begin {array}{r@{}l} \{ & \{\textit {con}_1, \textit {con}_2, \ldots , \textit {con}_q\}, \\ &\{\textit {fun}_a=\textit {ex}_a, \textit {fun}_b=\textit {ex}_b, \ldots , \textit {fun}_p=\textit {ex}_p\}, \\ &\{\textit {fun}_c, \textit {fun}_d, \ldots , \textit {fun}_r\}, \\ &\{\textit {ineq}_1, \textit {ineq}_2, \ldots , \textit {ineq}_s\} \}. \end {array} \]

For example, in the case of a linear system, the input consists of at most one solution $\textit {sol}_1$.

If CRACK ﬁnds a contradiction, e.g. $0=1$, then there exists no solution and it returns the empty list {}. If CRACK can factorize algebraically a non-linear equation then factors are set to zero individually and diﬀerent sub-cases are studied by CRACK calling itself recursively. If during such a recursive call a contradiction results, then this sub-case will not have a solution but other sub-cases still may have solutions. The empty list is also returned if no solution exists which satisﬁes the inequalities ineq$_i \neq 0$.

The expressions $\textit {con}_i$ (if there are any), are the remaining necessary and suﬃcient conditions for the functions $\textit {fun}_c,\ldots ,\textit {fun}_r$ in the third list. Those functions can be original functions from the equations to be solved (of the second argument of the call of CRACK) or new functions or constants which arose from integrations. The dependence of new functions on variables is declared with depend and to visualize this dependence the algebraic mode function fargs(fun$_i$) can be used. If there are no $\textit {con}_i$ then all equations are solved and the functions in the third list are unconstrained. The second list contains equations $\textit {fun}_i=\textit {ex}_i$ where each $\textit {fun}_i$ is an original function and $\textit {ex}_i$ is the computed expression for $\textit {fun}_i$. The elements of the fourth list are the expressions that have been assumed to be nonzero in the derivation of this solution.

Automatic versus Interactive

Under normal circumstances one will try to have problems solved automatically by CRACK. An alternative is to input off batch_mode; before calling CRACK and to solve problems interactively. In interactive mode it is possible to

inspect data, like equations and their properties, unknown functions, variables, identities, and statistics;
save, change, add or drop equations;
add inequalities;
inspect and change ﬂags and parameters which govern individual modules as well as their interplay;
pick a list of methods to be used out of about 30 diﬀerent ones and specify their priorities, and in this way very easily compose an automatic solving strategy;
or, for more interactive work, to specify how to proceed, i.e. which computational step to do and how often, like doing
- one automatic step,
- one speciﬁc step,
- a number of automatic steps,
- a speciﬁc step as often as possible or a speciﬁed number of times.

To get interactive help one enters h or ?.

Flags and parameters are stored as symbolic ﬂuid variables which means that they can be accessed by lisp(…), e.g. lisp( print_:=5 );, before calling CRACK. print_, for example, is a measure of the maximal length of expressions to be printed on the screen (the number of factors in terms). A complete list of ﬂags and parameters is given at the beginning of the ﬁle crinit.red (in the REDUCE packages/crack directory).

One more parameter shall be mentioned, which is the list of modules/procedures called proc_list_. In interactive mode this list can be looked at with p or changed with cp. This list deﬁnes the order in which the diﬀerent modules/procedures are tried whenever CRACK has to decide what to do next. Exceptions to this rule may be speciﬁed. For example, some procedure, say $P_1$, requires after its execution another speciﬁc procedure, say $P_2$, to be executed, no matter whether $P_2$ is next according to proc_list_ or not. This is managed by $P_1$ writing a task for procedure $P_2$ into a hot-list. Tasks listed in the global variable to_do_list are dealt with in the to_do step which should always come ﬁrst in proc_list_. A way to have the convenience of running CRACK automatically and still being able to break the ﬁxed rhythm prescribed by proc_list_ is to have the entry stop_batch in proc_list_ and have CRACK started in automatic batch mode. Then execution continues until none of the procedures which come before stop_batch are applicable any more so that stop_batch is executed next, which will stop automatic execution and go into interactive mode. This allows either to continue the computation interactively, or to change proc_list_ with cp and continue in automatic mode.

The default value of proc_list_ does not include all possible modules because not all are suitable for every kind of overdetermined system to be solved. The complete list is shown in interactive mode by cp. A few basic modules are described in the following subsection. The eﬃciency of CRACK in automatic mode is very much dependent on the content of proc_list_ and the sequence of its elements. Optimizing proc_list_ for a given task needs experience which cannot be formalized in a few simple rules and will therefore not be explained in more detail here. The following remarks are only guidelines.

20.15.3 Modules

The following modules are represented by numbers in the priority list. Each module can appear with modiﬁcations under diﬀerent numbers. For example, integration is available under 7, 24 and 25. Here 7 encodes an integration of short equations $0=\partial ^n f/\partial x^n$. 7 has highest priority of the three integrations. 24 encodes the integration of an equation that leads to the substitution of a function and 25 refers to any integration and has lowest priority.

Integration and Separation

An early feature in the development of the package CRACK was the ability to integrate exact diﬀerential equations and some generalizations of them (see [Wol00]). As a consequence of integrations 7, 24, 25 an increasing number of functions of fewer variables is introduced which sooner or later produces equations with some independent variables occuring only explicitly and not as variables in functions. Such equations are split by the separation module 2. Another possibility is equations in which each independent variable occurs in at least one function in the equation but no function depends on all variables. In this case so-called indirect separations are appropriate: for linear problems 10, 26 and for non-linear problems 48.

Substitutions

Substitutions can have a dramatic eﬀect on the size and complexity of systems. Therefore it is possible to have them not only done automatically but also controlled tightly, either by specifying exactly what equation should be used to substitute which unknown and where, or by picking a substitution out of a list of substitutions oﬀered by the program {cs}. Substitutions to be performed automatically can be controlled with a number of ﬁlters, for example, by

limiting the size of the equation to be used for substitution; {length_limit}
limiting the size of equations in which the substitution is to be done; {target_limit_}
allowing only linear equations to be used for substitutions; {lin_subst}
allowing equations to increase in size only up to some factor in order for a substitution to be performed in that equation; {cost_limit}
allowing a substitution for a function through an expression only if that expression involves exclusively functions of fewer variables; {less_vars}
allowing substitutions only that do not lead to a case distinction coeﬃcient = 0 or not;
specifying whether extra eﬀort should be spent to identify the substitution with the lowest bound on growth of the full system. {min_growth}

Substitution types are represented by diﬀerent numbers (3–6,15–21) depending on the subset of the above ﬁlters to be used. If a substitution type is to be done automatically then from all possible substitutions passing all ﬁlters of this type that substitution is selected that leads to no sub-cases (if available) and that uses the shortest equation.

Factorization

It is very common that big algebraic systems contain equations that can be factorized. Factorizing an equation and setting the factors individually to zero simpliﬁes the whole task because factors are simpler expressions than the whole equation and setting them to zero may lead to substitutions and thereby further simpliﬁcations. The downside is that if problems with, say 100 unknowns, would need 40 case distinctions in order to be able to solve automatically for the remaining 60 unknowns then this would require $2^{40}$ cases to be investigated which is impractical. The problem is to ﬁnd the right balance between delaying case distinctions in order not to generate too many cases and introducing case distinctions as early as necessary in order to simplify the system. This simpliﬁcation may be necessary to solve the system but in any case it will speed up its solution (although at the price of having to solve a simpliﬁed system at least twice, depending on the number of factors).

For large systems with many factorizable equations the careful selection of the next equation to be factorized is important to gain the most from each factorization and to succeed with as few factorizations as possible. Some of the criteria which give factors and therefore equations a higher priority are

the number of equations in which this factor occurs,
if the factor is a single unknown function or constant, then the number of times this unknown turns up in the whole system,
the total degree of the factor,
the number of factors of an equation.

It also matters in which order the factors are set to zero. For example, the equation $0=ab$ can be used to split into the 2 cases: $1.\ a=0, \ 2.\ a\neq 0, b=0$ or to split into the 2 cases $1.\ b=0, \ 2.\ b\neq 0, a=0$. If one of the 2 factors, say $b$, involves functions which occur only linearly then this property is to be preserved and these functions should be substituted as such substitutions preserve their linearity. But to have many such substitutions available, it is useful to know of many non-linearly occuring functions to be non-zero as they occur as coeﬃcients of the linearly occuring functions. In the above situation it is therefore better to do the ﬁrst splitting $1.\ a=0, \ 2.\ a\neq 0, b=0$ because $a\neq 0$ will be more useful for substitutions of linear functions than $b\neq 0$ would be.

An exception of this plausible rule occurs towards the end of all the substitutions of all the linearly occurring $b_i$ when some $b_i$ is an overall factor to many equations. If one would then set, say, $b_{22}=0$ as the second case in a factorization, the ﬁrst case would generate as subcases factorizations of other equations where $b_{22}=0$ would be the second case again and so on. To avoid this one should investigate $b_{22}=0$ as the ﬁrst case in the ﬁrst factorization.

The only purpose of that little thought experiment was to show that simple questions, like ‘Which factored equation should be used ﬁrst for case-distinctions and in which order to set factors to zero?’ can already be diﬃcult to answer in general.

CRACK currently oﬀers two factorization steps: (8) and (47).

Elimination (Gröbner Basis) Steps

To increase safety and avoid excessive expression swell one can apart from the normal call (30) request to do Gröbner basis computation steps only if they are simpliﬁcation steps replacing an equation by a shorter equation. (27)

In a diﬀerent version only steps are performed in which equations are included which do not contain more than 3 unknowns. This helps to focus on steps which are more likely to solve small sub-systems with readily available simple results. (57)

Often the computationally cheapest way to obtain a consistent (involutive) system of equations is to change the ordering during the computation. This is the case when substitutions of functions are performed which are not ranked highest in a lexicographical ordering of functions. But CRACK also oﬀers an interactive way to

change the lexicographical ordering of variables, {ov}
change the lexicographical ordering of functions, {of}
give the diﬀerential order of derivatives a higher or lower priority in the total ordering than the lexicographical ordering of functions, {og}
give either the total diﬀerential order of a partial derivative a higher priority than the lexicographical ordering of the derivative of that function or to take the lexicographical ordering of derivatives as the only criterion. {of}

Solution of an Under-Determined Diﬀerential Equation

When solving an over-determined system of linear diﬀerential equations where the general solution involves free functions, in the last computational step often a single equation for more than one function remains to be solved. Examples are the computation of symmetries and conservation laws of non-linear diﬀerential equations which are linearizable. In CRACK two procedures are available, one for under-determined linear ODEs (22) and one for linear PDEs, (23) both with non-constant coeﬃcients.

Indirect Separation

Integrations introduce new functions of fewer variables. As equations are used to substitute functions of all variables it is only a question of time that equations are generated in which no function depends on all variables. If at least one variable occurs only explicitly then the equation can be split, which we call direct separation. But sometimes all variables appear as variables of unknown functions, e.g. $0=f(x)+g(y)$ although usually much more complicated with 10 or 20 independent variables and many functions that depend on diﬀerent combinations of these variables. Because no variable occurs only explicitly, direct separations mentioned above are not possible. Two diﬀerent algorithms, one for linear indirectly separable equations (10), (26) and one for non-linear directly separable equations (48) provide systematic ways of dealing with such equations.

Indirectly separable equations always result when an equation is integrated with respect to diﬀerent variables, like $0=f_{xy}$ to $f=g(x)+h(y)$ and a function, here $f(x,y)$, is substituted.

Function and Variable Transformations

In the interactive mode one can specify a transformation of the whole problem with pt in which old functions and variables are expressed as a mix of new functions and variables.

Solution of First Order Linear PDE

If a system contains a single linear ﬁrst-order PDE for just one function then in an automatic step characteristic ODE-systems are generated, integrated if possible, a variable transformation for the whole system of equations is performed to have in the ﬁrst-order PDE only one single derivative and to make this PDE integrable for the integration modules. (39)

Length Reduction of Equations

An algorithm designed originally to length-reduce diﬀerential equations proved to be essential in length-reducing systems of bi-linear algebraic equations or homogeneous equations which resulted from bi-linear equations during the solution process.

The aim of the method (11) is to ﬁnd out whether one equation $0=E_1$ can length-reduce another one $0=E_2$ by replacing $E_2$ through an appropriate linear combination $\alpha E_1 - \beta E_2,\ \ \beta \neq 0$. To ﬁnd $\alpha , \beta $ one can divide each term of $E_2$ through each term of $E_1$ and count how often each quotient occurs. If a quotient $\alpha /\beta $ occurs $m$ times then $\alpha E_1 - \beta E_2$ will have $\leq n_1+n_2-2m$ terms because $2m$ terms will cancel each other. A length reduction is found if $n_1+n_2-2m\leq \max (n_1,n_2)$. The method becomes eﬃcient after a few algorithmic reﬁnements discussed in [Wol02b]. Length-reduced equations

are more likely to length-reduce other equations,
are much more likely to be factorizable,
are more suited for substitutions as the substitution induces less growth of the whole systems and introduces fewer new occurrences of functions in equations,
are more likely to be integrable by being exact or being an ODE if the system consists of diﬀerential equations,
involve on average fewer unknowns and make the whole system more sparse. This sparseness can be used to plan better a sequence of eliminations.

This concludes the listing of modules. Other aspects of CRACK follow.

20.15.4 Features

Flexible Process Control

Diﬀerent types of over-determined systems are more or less suited for an automatic solution. With the currrent version it is relatively safe to try solving large bi-linear algebraic problems automatically. Another well-suited area concerns over-determined systems of linear PDEs. In contrast, non-linear systems of PDEs most likely require a tighter interactive control. Diﬀerent modes of operation are possible. One can

perform one {a} or more computational steps {g} automatically, where each step tries modules in the order deﬁned by the current priority list {p1} until one module succeeds in its purpose;
perform one module a speciﬁc number of times or as long as it is successful; {l}
set a time limit for how long the program should run automatically; {time_limit, limit_time}
interrupt an on-going automatic computation and continue the computation interactively by copying the ﬁle _stop_crack into the directory where the ongoing computation was started and re-naming it _stop_ (and by deleting _stop_ to resume automatic computation);
arrange the priority list of module changes at a certain point in the computation when the system of equations has changed its character;
induce a case distinction whether a user-given expression is zero or not; {44}
have a module that changes the priority list proc_list_ dynamically, depending essentially on the size and diﬃculty of the system but also on the success rate of previous steps. {61, 62, 63}

Apart from ﬂexible control over what kind of steps to do, the steps themselves can be controlled more or less too, e.g. whether equations are selected by the module or the user.

So-called to-do steps have highest priority in the priority list. The list of to-do steps is usually empty but can be ﬁlled by any successful step if it requires another speciﬁc step to follow instantly. For example, if a very simple equation $0=f_x$ is integrated then the substitution of $f$ should follow straight away, even if substitutions would have a low priority according to the current priority list.

Total Data Control

To make wise decisions of how to continue the computation in an interactive session one needs tools to inspect large systems of equations. Helpful commands in CRACK print

equations, inequalities, functions and variables {e, pi, f};
the occurence of all derivatives of selected functions in any equation; {v}
a statistics summary of the equations of the system; {s}
a matrix display of occurences of unknowns in all equations; {pd}
the value of any LISP variable; {pv}
the value of algebraic expressions that can be speciﬁed using equation names (e.g. coeffn(e_5,df(f,x,y),2)); {pe}
not under-determined subsystems. {ss}

Inspecting a computation which already goes on for hours or a day and has performed many thousand steps is time consuming. The task is made easier with the possibility to plot graphically as a function of time: the type of steps performed, the number of unknowns, the number of remaining equations, the number of terms in these equations and the memory usage. {ps}

When non-linear systems are considered and many case distinctions and sub-(sub-…)case distinctions are made in a long computation, one easily loses track. With one command one can list all cases that have been considered so far with their assumption, the number of steps made until they are solved or until the next sub-case distinction was made and the number of solutions contained in each completed case. {ls}

Safety

When working on large problems, a stage may come where computational steps are necessary, like substitution, which are risky in the sense that they may simplify the problem or complicate it by increasing its size. To avoid this risk a few safety features have been implemented.

At any time during the computation one can save a backup of the complete current situation in a ﬁle and also load a backup. The command sb "file_name" saves all global variables and data into an ASCII ﬁle and the command rb "file_name" reads these data from a ﬁle. The format is independent of the computer used and independent of the underlying Lisp version. Apart from reading in a backup ﬁle during an interactive computation with rb one can also start a computation with a backup ﬁle. After loading CRACK one makes in REDUCE the call crackshell()$ followed by the ﬁle name of the backup.
All key strokes are automatically recorded in a list which is available after each interactive step with ph, or when the computation has ﬁnished through lisp reverse history_;. This list can be fed into CRACK at the beginning of a new computation so that the same operations are performed automatically that were performed interactively before. The purpose is to be able to do an interactive exploration ﬁrst and to repeat it afterwards automatically without having to note with pen or pencil all steps that had been done.
By assigning this list to the Lisp variable old_history before calling CRACK with off batch_mode the same steps as in the previous run are performed ﬁrst as CRACK ﬁrst reads input from old_history and then reads from the keyboard.
During an automatic computation the program might start a computational step which turns out to take far too long. It would be better to stop this computation and try something else instead. But in computer algebra with lots of global variables involved it is not straightforward to stop a computation in the middle. If one used time as a criterion then it could happen that time is up during a garbage collection and to stop would be deadly for the session. CRACK allows to set a limit of garbage collections for any computations that have the potential to last forever, like algebraic factorizations of large expressions. With such an arrangement an automatic computation cannot get stuck due to lengthy factorizations, searches for length reductions or elimination steps. {max_gc_elimin, max_gc_fac, max_gc_red_len, max_gc_short, max_gc_ss}
Due to an initiative by Winfried Neun the parallel version of REDUCE has been re-activated (and was running on the Beowulf cluster at Brock University [MN02]). This allows conveniently (with {pp}) to duplicate the current status of a CRACK computation to another computer, to try out there diﬀerent operations (e.g. risky ones) until a viable way to continue the computation is found without endangering the original session.

Managing Solutions

Non-linear problems can have many solutions. The number of solutions found by CRACK can even be higher because to make progress CRACK may have factorized an equation and considered the two cases $a=0$ and $a \neq 0$ whereas solutions in both cases could be merged to only one solution without any restriction for $a$. This merging of solutions can be accomplished with a separate program merge_sol() after the computation.

Another form of post-processing is the production of a web page for each solution, like lie.math.brocku.ca/twolf/bl/v/v1l05o35-s1.html.

If in the solution of over-determined diﬀerential equations the program performs integrations of equations before the diﬀerential Gröbner basis was computed then in the ﬁnal solution there may be redundant constants or functions of integration. Redundant constants or functions in a solution are not an error but they make solutions appear unnecessarily complicated. In a postprocessing step these functions and constants can be eliminated. {adjust_fnc, drop_const(), dropredundant()}

Parallelization

The availability of a parallel version of CRACK was mentioned above allowing to try out diﬀerent ways to continue an ongoing computation. A diﬀerent possibility to make use of a cluster of computers with CRACK is to export automatically the investigation of sub-cases and sub-sub-cases to diﬀerent computers to be solved in parallel.

It was explained above how factorizations may be necessary to make any progress but also their potential of exploding the time requirements. By running the computation on a cluster and being able to solve many more cases one can give factorizations a higher priority and capitalize on the beneﬁt of factorizations, i.e. the simpliﬁcation of the problem.

Relationship to Gröbner Basis Algorithms

For systems of equations in which the unknown constants or functions turn up only polynomially a well-known method is able to check the consistency of the system. For algebraic systems this is the Gröbner Basis method and for systems of diﬀerential equations this is the diﬀerential Gröbner Basis method. To guarantee the method will terminate a total ordering of unknowns and their derivatives has to be introduced. This ordering determines which highest powers of unknowns are to be eliminated next or which highest-order derivatives have to be eliminated next using integrability conditions. Often such eliminations lead to exponential growth of the generated equations. In the package CRACK such computations are executed with only a low priority. Operations have a higher priority which reduce the length of equations, irrespective of any orderings. Violating any ordering a ﬁnite number of times still guarantees a ﬁnite algorithm. The potential gain is large as described next.

Exploiting Bi-Linearity

In bi-linear algebraic problems we have 2 sets of variables, $a_1,\ldots ,a_m$ and $b_1,\ldots ,b_n$, such that all equations have the form $0=\sum _{k=1}^l \gamma _k a_{i_k}b_{j_k}, \ \gamma _k \in G$. Although the problem is linear in the $a_i$ and linear in the $b_j$ it still is a non-linear problem. A guideline which helps keep the structure of the system during computation relatively simple is to preserve the linearity of either the $a_i$ or the $b_j$ as long as possible. In classiﬁcation problems of integrable systems the ansatz for the symmetry/ﬁrst integral usually involves more terms and therefore more constants (called $b_j$ in applications of CRACK) than the ansatz for the integrable system (with constants $a_i$). A good strategy therefore is to keep the system linear in the $b_j$ during the computation, i.e. to

substitute only a $b_j$ in terms of $a_i, b_k$, or an $a_i$ in terms of an $a_k$ but not an $a_i$ in terms of any $b_k$;
do elimination steps for any $b_j$ or for an $a_i$ if the involved equations do not contain any $b_k$.

The proposed measures are eﬀective not only for algebraic problems but for ODEs/PDEs too (i.e. to preserve linearity of a subset of functions as long as possible). {ﬂin_}

Occurrence of sin, cos or Other Special Functions

If the equations to be solved involve special functions, like $\sin $ and $\cos $, then one is inclined to add let-rules for simplifying expressions. Before doing this the simpliﬁcation rules at the end of the ﬁle crinit.red (in the REDUCE packages/crack directory) should be inspected such that new rules do not lead to cycles with existing rules. One possibility is to replace existing rules, for example to substitute the existing rule

     trig1_ := {sin(~x)**2 => 1-cos(x)**2}$

by the new rule

     trig1_ := {cos(~x)**2 => 1-sin(x)**2}$

These rules are switched oﬀ when integrations are performed in order not to interfere with the REDUCE integrator.

Apart from an initial customization of let-rules to be used during the whole run one can also specify and clear let-rules during a computation using the interactive commands lr,cr.

Exchanging Time for Memory

The optimal order of applying diﬀerent methods to the equations of a system is not ﬁxed. It does depend, for example, on the distributions of unknown functions in the equations and on what the individual method would produce in the next step. For example, it is possible that the decoupling module which applies integrability conditions through cross diﬀerentiations of equations is going well up to a stage when it suddenly produces huge equations. They not only occupy much memory, they also are slow to handle. Right before this explosion started other methods should have been tried (shortening of equations, any integrations, solution of under-determined ODEs if there are any, …). These alternative methods are normally comparatively slow or unfavourable as they introduce new functions but under the current circumstances they may be perfect to avoid any growth and to complete the calculation. How could one have known beforehand that some method will lead to an explosion? One does not know. But one can regularly make a backup with the interactive sb command and restart at this situation if necessary.

Customization

The addition of new modules to perform new specialized computations is easy. Only the input and output of any new module are ﬁxed. The input consists of the system of equations, the list of inequalities and the list of unknowns to be computed. The output includes the new system of equations and new intermediate results. The module name has to be added to a list of all modules and a one line description has to be added to a list of descriptions. This makes it easy for users to add special techniques for the solution of systems with extra structure. A dummy template module {58} is already added and has only to be ﬁlled with content.

Debugging

A feature, useful mainly for debugging is that in the middle of an ongoing interactive computation the program can be changed by loading a diﬀerent version of CRACK procedures. Thus one could advance quickly close to the point in the execution where an error occurs, load a version of the faulty procedure that gives extensive output and watch how the fault happens before ﬁxing it.

The possibility to interrupt REDUCE itself temporarily and to inspect the underlying LISP environment {br} or to execute LISP commands and to continue with the CRACK session afterwards {pc} led to a few improvements and ﬁxes in REDUCE itself.

20.15.5 Technical issues

System Requirements

PSL REDUCE is faster whereas CSL REDUCE seems to be more stable under Microsoft Windows. Also it provides portable compiled code.

Memory requirements depend crucially on the application. The crack.rlg ﬁle can be produced by running crack.tst in a 4MB session running REDUCE under LINUX (the ﬁles are in the REDUCE packages/crack directory). On the other hand it is not diﬃcult to formulate problems that consume any amount of memory.

Availability

The package CRACK together with LIEPDE, CONLAW and APPLYSYM are included with REDUCE. Publications related to CRACK itself and to applications based on it can be found under lie.math.brocku.ca/twolf/home/publications.html.

The ﬁles

The following ﬁles are provided with CRACK (in the REDUCE packages/crack directory):

`crack.red`	contains read-in statements for a number of ﬁles `cr*.red`
`crack.tst`	contains test examples
`crack.rlg`	contains the output of `crack.tst`
`crack.tex`	the original version of this manual.

20.15.6 Reference

Elements of proc_list_

The interactive command p1 shows proc_list_. This list deﬁnes the order in which procedures are tried if a step is to be performed automatically. Command p2 shows the complete list as it is shown below. To select any one procedure of the complete list interactively, one simply inputs the number shown in (). The numbering of procedures grew historically. Each number has only little or no connection with the priority of the procedure it is labelling.

to_do (1):

hot list of steps to be taken next. Should always come ﬁrst.

subst_level_? (3-6,15-21):

substitutions of functions by expressions. Substitutions diﬀer by their maximal allowed size and other properties. To ﬁnd out which function has which properties one currently has to inspect the procedure deﬁnitions of subst_level_? in the ﬁle crmain.red.

separation (2):

what is described as direct separation in the next subsection.

gen_separation (26):

what is described as indirect separation in the next subsection. Only to be used for linear problems.

quick_gen_separation (10):

generalized separation of equations with an upper size limit.

quick_integration (7):

integration of very speciﬁc short equations.

full_integration (24):

integration of equations which lead to a substitution.

integration (25):

any integration.

factorize_to_substitute (8):

splitting the computation into the investigation of diﬀerent sub-cases resulting from the algebraic factorization of an equation. Only useful for non-linear problems, and applied only if each one of the factors, when individually set to zero, would enable the substitution of a function.

factorize_any (47):

splitting into sub-cases based on a factorization even if not all factors set to zero lead to substitutions.

change_proc_list (37):

reserved name of a procedure to be written by the user that does nothing else but changing proc_list_ in a ﬁxed manner. This is to be used if the computation splits naturally into diﬀerent parts and if it is clear from the beginning what the computational methods (proc_list_) have to be.

stop_batch (38):

If the ﬁrst steps to simplify or partially solve a system of equations are known and should be done automatically and afterwards CRACK should switch into interactive mode then stop_batch is added to proc_list with a priority just below the steps to be done automatically.

drop_lin_dep (12):

module to support solving big linear systems (still experimental).

find_1_term_eqn (13):

module to support solving big linear systems (still experimental).

trian_lin_alg (14):

module to support solving big linear systems (still experimental).

undetlinode (22):

parametric solution of single under-determined linear ODE (with non-constant coeﬃcients). Only applicable for linear problems. (Too many redundant functions resulting from integrations may prevent further integrations. If they are involved in single ODEs then the parametric solution of such ODEs treated as single under-determined equations is useful. Danger: new generated equations become very big if the minimal order of any function in the ODE is high.)

undetlinpde (23):

parametric solution of single under-determined linear PDE (with non-constant coeﬃcients). Only applicable for linear problems (still experimental).

alg_length_reduction (11):

length reduction by algebraic combination. Only for linear problems. One has to be careful when combining it with decoupling as inﬁnite loops may occur when shortening and lowering order reverse each other.

diff_length_reduction (27):

length reduction by diﬀerential reduction.

decoupling (30):

steps towards the computation of a diﬀerential Gröbner Basis.

add_differentiated_pdes (31):

only useful for non-linear diﬀerential equations with leading derivative occurring non-linearly.

add_diff_ise (32):

for the treatment of non-linear indirectly separable equations.

multintfac (33):

to ﬁnd integrating factors for a system of equations. Should have very low priority if used at all.

alg_solve_single (34):

to be used for equations quadratic in the leading derivative.

alg_solve_system (35):

to be used if a (sub-)system of equations shall be solved for a set of functions or their derivatives algebraically.

subst_derivative (9):

substitution of a derivative of a function everywhere by a new function if such a derivative exists.

undo_subst_derivative (36):

undo the above substitution.

del_redundant_fc (40):

drop redundant functions and constants. For that an over-determined PDE system is formulated and solved to set redundant constants and functions of integration to zero. This may take longer if many functions occur.

find_trafo (39):

ﬁnding a ﬁrst-order linear PDE. By solving it the program ﬁnds a variable transformation that transforms the PDE to a single derivative and makes the PDE integrable for the integration modules. Because a variable transformation was performed the solution contains only new functions of integration which depend on single (new) variables and not on expressions of them, like sums of them. Therefore the result of the integration can be used for substitutions in other equations. If the transformation had not been made then the solution of the PDE would involve arbitrary functions of expressions and could not be used for the other equations using the current modules of CRACK. A general transformation can be done interactively with the command cp.

sub_problem (41):

solve a subset of equations ﬁrst (still experimental).

del_redundant_de (28):

delete redundant equations.

idty_integration (29):

integrate an identity.

gen_separation2 (48):

indirect separation of a PDE. This is a second version for non-linear PDEs.

find_and_use_sub_systems12 (49):

ﬁnd sub-systems of equations with at least as many equations as functions. In this case ﬁnd systems with at most 2 functions, none of them a function of the set flin_. (These are functions which occur initially only linearly in a non-linear problem; flin_ is assigned initially by the user.)

find_and_use_sub_systems13 (50):

like above only with at most 3 functions, none from flin_.

find_and_use_sub_systems14 (51):

like above only with at most 4 functions, none from flin_.

find_and_use_sub_systems15 (52):

like above only with at most 5 functions, none from flin_.

find_and_use_sub_systems22 (53):

like above only with at most 2 functions. Only flin_ are considered, all others ignored.

find_and_use_sub_systems23 (54):

like above only with at most 3 functions. Only flin_ are considered, all others ignored.

find_and_use_sub_systems24 (55):

like above only with at most 4 functions. Only flin_ are considered, all others ignored.

find_and_use_sub_systems25 (56):

like above only with at most 5 functions. Only flin_ are considered, all others ignored.

high_prio_decoupling (57):

do a decoupling step with two equations that in total involve at most 3 diﬀerent functions of all independent variables in these equations.

user_defined (58):

This is an empty procedure which can be ﬁlled by the user with a very speciﬁc computational step that is needed in a special user application. Template:

     symbolic procedure user_defined(arglist)$
        % arglist is a Lisp list {pdes,forg,vl_} where
        %   pdes is the list of names of all equations
        %   forg is the list of original functions +
        %     their values as far as known
        %   vl_ is the list of independent variables
     begin
        ...
        return if successful then list(pdes,forg)
           % new pdes + functions and their value
           else nil
     end$

alg_groebner (59):

call of the REDUCE procedure groebnerf trying to solve the whole system under the assumption that it is a completely algebraic polynomial system. All resulting solutions are considered individually further.

solution_check (60):

this procedure tests whether a solution that is deﬁned in an external procedure sol_define() is still contained in the general solution of the system currently under investigation. This procedure is useful to ﬁnd the place in a long computation where a special solution is either lost or added to the general solution of the system to be solved. Template:

     algebraic procedure sol_define$
     << % This procedure contains the statements
        % that specify a solution
        % Example: Test whether s=h_-y**2/t**2, u=y/t
        % is a solution, where h_=h_(t)
        depend h_,t$
        % Return a list of expressions that vanish for
        % the solution to be tested, in this example:
        {s-(h_-y**2/t**2), u-y/t}
     >>$

Online Help

The following commands and their one line descriptions appear in the same order as in the online help.

Help for Help

`hd`	Help to inspect data
`hp`	Help to proceed
`hf`	Help to change ﬂags and parameters
`hc`	Help to change data of equations
`hi`	Help to work with identities
`hb`	Help to trace and debug

Help to Inspect Data

`e`	Print equations
`eo`	Print overview of functions in equations
`pi`	Print inequalities
`f`	Print functions and variables
`v`	Print all derivatives of all functions
`s`	Print statistics
`fc`	Print no of free cells
`pe`	Print an algebraic expression
`ph`	Print history of interactive input
`pv`	Print value of any Lisp variable
`pf`	Print no of occurences of each function
`pr`	Print active substitution rules
`pd`	Plot the occurence of functions in equations
`ps`	Plot a statistical history
`lc`	List all case distinctions
`ws`	Write statistical history in ﬁle
`sn`	Show name of session
`ss`	Find and print sub-systems
`w`	Write equations into a ﬁle

Help to Proceed

`a`	Do one step automatically
`g`	Go on for a number of steps automatically
`t`	Toggle between automatic and user selection of equations
	(`expert_mode=nil/t`)
`p1`	Print a list of all modules in batch mode
`p2`	Print a complete list of all modules
`#`	Execute the module with the number ‘#’ once
`l`	Execute a speciﬁc module repeatedly
`sb`	Save complete backup to ﬁle
`rb`	Read backup from ﬁle
`ep`	Enable parallelism
`dp`	Disable parallelism
`pp`	Start an identical parallel process
`kp`	Kill a parallel process
`x`	Exit interactive mode for good
`q`	Quit current level or crack if in level 0

Help to Change Flags and Parameters

`pl`	Maximal length of an expression to be printed
`pm`	Toggle to print more or less information about PDEs (`print_more`)
`pa`	Toggle to print all or not all information about the PDEs (`print_all`)
`cp`	Change the priorities of procedures
`og`	Toggle ordering between ‘lexicographical ordering of functions having
	a higher priority than any ordering of derivatives’ and the opposite
	(`lex_fc=t`) resp. (`lex_fc=nil`)
`od`	Toggle ordering between ‘the total order of derivatives having a higher
	priority than lexicographical ordering’ (`lex_df=nil`) or not
	(`lex_df=t`)
`oi`	Interactive change of ordering on variables
`or`	Reverse ordering on variables
`om`	Mix randomly ordering on variables
`of`	Interactive change of ordering on functions
`op`	Print current ordering
`ne`	Root of the name of new generated equations (default: `e_`)
`nf`	Root of the name of new functions and constants (default: `c_`)
`ni`	Root of the name of new identities (default: `id_`)
`na`	Toggle for the `nat` output switch (`!*nat`)
`as`	Input of an assignment
`kp`	Toggle for keeping a partitioned copy of each equation (`keep_parti`)
`fi`	Toggle for allowing or not allowing integrations of equations which
	involve unresolved integrals (`freeint_`)
`fa`	Toggle for allowing or not allowing solutions of ODEs involving the
	`abs` function (`freeabs_`)
`cs`	Switch on/oﬀ the conﬁrmation of intended substitutions and of the
	order of the investigation of subcases resulting in a factorization
`fs`	Enforce direct separation
`ll`	change of the line length
`re`	Toggle for allowing to re-cycle equation names (`do_recycle_eqn`)
`rf`	Toggle for allowing to re-cycle function names (`do_recycle_fnc`)
`st`	Setting a CPU time limit for un-interrupted run
`cm`	Adding a comment to the `history_` list
`lr`	Adding a LET-rule
`cr`	Clearing a LET-rule

Help to Change Data of Equations

`r`	Replace or add one equation
`rd`	Reduce an equation modulo LET rules
`n`	Replace one inequality
`de`	Delete one equation
`di`	Delete one inequality
`c`	Change a ﬂag or property of one PDE
`pt`	Perform a transformation of functions and variables

Help to Work with Identities

`i`	Print identities between equations
`id`	Delete redundand equations
`iw`	Write identities to a ﬁle
`ir`	Remove list of identities
`ia`	Add or replace an identity
`ih`	Start recording histories and identities
`ip`	Stop recording histories and identities
`ii`	Integrate an identity
`ic`	Check the consistency of identity data
`iy`	Print the history of equations

Help to Trace and Debug

`tm`	Toggle for tracing the main procedure (`tr_main`)
`tg`	Toggle for tracing the generalized separation (`tr_gensep`)
`ti`	Toggle for tracing the generalized integration (`tr_genint`)
`td`	Toggle for tracing the decoupling process (`tr_decouple`)
`tl`	Toggle for tracing the decoupling length reduction process
	(`tr_redlength`)
`ts`	Toggle for tracing the algebraic length reduction process (`tr_short`)
`to`	Toggle for tracing the ordering procedures process (`tr_orderings`)
`tr`	Trace an arbitrary procedure
`ut`	Untrace a procedure
`br`	Lisp break
`pc`	Do a function call
`in`	Reading in a REDUCE ﬁle

Global variables

The following is a complete list of identiﬁers used as global Lisp variables (to be precise, symbolic ﬂuid variables) within CRACK. Some are ﬂags and parameters, others are global variables; some of them can be accessed after the CRACK run.

!*allowdfint_bak !*dfprint_bak !*exp_bak !*ezgcd_bak !*fullroots_bak !*gcd_bak !*mcd_bak !*nopowers_bak !*ratarg_bak !*rational_bak !*batch_mode abs_ adjust_fnc allflags_ batchcount_ !*backup_ collect_sol confirm_subst cont_ contradiction_ cost_limit5 current_dir default_proc_list_ do_recycle_eqn do_recycle_fnc done_trafo eqname_ expert_mode explog_ facint_ flin_ force_sep fname_ fnew_ freeabs_ freeint_ ftem_ full_proc_list_ gcfree!* genint_ glob_var global_list_integer global_list_ninteger global_list_number high_gensep homogen_ history_ idname_ idnties_ independence_ ineq_ inter_divint keep_parti last_steps length_inc level_ lex_df lex_fc limit_time lin_problem lin_test_const logoprint_ low_gensep max_gc_counter max_gc_elimin max_gc_fac max_gc_red_len max_gc_short max_gc_ss max_red_len maxalgsys_ mem_eff my_gc_counter nequ_ new_gensep nfct_ nid_ odesolve_ old_history orderings_ target_limit_0 target_limit_1 target_limit_2 target_limit_3 target_limit_4 poly_only potint_ print_ print_all print_more proc_list_ prop_list pvm_able quick_decoup record_hist recycle_eqns recycle_fcts recycle_ids reducefunctions_ repeat_mode safeint_ session_ simple_orderings size_hist size_watch sol_list solvealg_ stepcounter_ stop_ struc_dim struc_eqn subst_0 subst_1 subst_2 subst_3 subst_4 time_ time_limit to_do_list tr_decouple tr_genint tr_gensep tr_main tr_orderings tr_redlength tr_short trig1_ trig2_ trig3_ trig4_ trig5_ trig6_ trig7_ trig8_ userrules_ vl_

Global Flags and Parameters

The list below gives a selection of ﬂags and global parameters that are available, for example, to ﬁne tune the performance according to speciﬁc needs of the system of equations that is studied. Usually they are not needed and very few are used regularly by the author. The interactive command that changes the ﬂag/parameter is given in [ ], default values of the ﬂags/parameters are given in (). All values can be changed interactively with the as command. The values of the ﬂags and parameters can either be set after loading CRACK and before starting it with a Lisp assignment, for example,

     lisp(print_ := 8)$

or after starting CRACK in interactive mode with speciﬁc commands, like pl to change speciﬁcally the print length determining parameter print_, or the command as to do an assignment. The values of parameters/ﬂags can be inspected interactively using pv and changed with as.

!*batch_mode [x] (t) :: running CRACK in interactive mode (!*batch_mode=nil) or automatically (!*batch_mode=t). It can also be set in algebraic mode before starting CRACK by on/off batch_mode. Interactive mode can be left and automatic computation be started by the interactive command x.
!*iconic (nil) :: whether new processes in parallelization should appear as icons (t) or windows (nil).
adjust_fnc (nil) :: if t then free constants/functions are scaled and redundant ones are dropped to simplify the result after the computation has been completed.
collect_sol (t) :: whether solutions found shall be collected and returned together at the end or not (to save memory); it matters only for non-linear problems with very many special solutions. If a computation has to be performed with any solution that is found, then these commands can be put into an algebraic procedure crack_out(eqns, assigns, freef, ineq) which is currently empty in ﬁle crmain.red but which is called for each solution.
confirm_subst [cs] (nil) :: whether substitutions have to be conﬁrmed interactively.
cont_ (nil) :: interactive user control for integration or substitution of large expressions (enabled = t).
cost_limit5 (100) :: maximal number of extra terms generated by a substitution.
do_recycle (nil) :: whether function names shall be recycled or not (saves memory but computation is less clear to follow).
done_trafo (nil) :: an (algebraic mode) list of back-transformations that would invert done transformations; this list is useful after CRACK completed to invert transformations if needed.
eqname_ [ne] (’e_) :: name of new equations.
expert_mode [t] (nil) :: For expert_mode=t the equations that are involved in the next computational step are selected by CRACK, for expert_mode=nil the user is asked to select one or two equations which are to be worked with in the next computational step.
facint_ (1000) :: if nil then no search for integrating factors, otherwise sets the maximum of product terms * kernels when searching for an integrating factor.
flin_ (nil) :: a list of functions occuring only linearly in an otherwise non-linear problem; must be assigned before calling CRACK. During execution CRACK tries to preserve the linearity of these functions as long as possible.
fname_ [nf] (’c_) :: name of new functions and constants (integration).
force_sep (nil) :: whether direct separation should be forced even if functions occur in the supposedly linear independent explicit expressions (for non-linear problem).
freeabs_ [fi] (t) :: Do not use solutions of ODEs that involve the abs function.
freeint_ [fi] (t) :: Do integrations only if explicit part is integrable.
genint_ (15) :: if nil then generalized integration disabled else sets the maximal number of new functions and extra equations due to the generalized integration of one equation.
high_gensep (300) :: minimum size of expressions to separate in a generalized way by quick_gen_separation.
homogen_ (nil) :: test for homogeneity of each equation (for debugging).
idname_ [ni] (’id_) :: name of new equations.
idnties_ (nil) :: list of identities resulting from reductions and integrability conditions.
independence_ (nil) :: interactive control of linear independence (enabled = t).
inter_divint (nil) :: whether the integration of divergence identities with more than 2 diﬀerentiation variables shall be conﬁrmed interactively.
keep_parti [kp] (nil) :: whether for each equation a copy in partitioned form is to be stored to speed up several simpliﬁcations but which needs more memory.
last_steps (nil) :: a list of the last steps generated and updated automatically in order to avoid cycles.
length_inc (1.0) :: factor by which the length of an expression may grow when performing diff_length_reduction.
lex_df [od] (nil) :: if t then use lexicographical instead of total degree ordering of derivatives.
lex_fc [og] (t) :: if t then lexicographical ordering of functions has higher priority than any ordering of derivatives.
limit_time (nil) :: = time() + how many more seconds allowed in batch mode.
logoprint_ (t) :: print logo after CRACK call.
low_gensep (6) :: maximum size of expressions to be separated in a generalized way by quick_gen_separation.
max_gc_counter (100000000) :: maximal total number of garbage collections.
max_gc_elimin (15) :: maximal number of garbage collections during elimination in decoupling.
max_gc_fac (15) :: maximal number of garbage collections during factorization.
max_gc_red_len (30) :: maximal number of garbage collections during length reduction.
max_gc_short (40) :: maximal number of garbage collections during shortening.
max_gc_ss (10) :: maximal number of garbage collections during search of sub-systems.
max_red_len (1000000) :: maximal product of lengths of two equations to be combined with length-reducing decoupling.
maxalgsys_ (20) :: maximum number of equations to be solved in specialsol.
mem_eff (t) :: whether to be memory eﬃcient even if slower.
my_gc_counter (0) :: initial value of my_gc_counter.
nequ_ (1) :: index of the next new equation.
new_gensep (nil) :: whether or not a newer (experimental) form of gensep should be used.
nfct_ (1) :: index of the next new function or constant.
nid_ (1) :: index of the next new identity.
odesolve_ (100) :: maximal length of a DE (number of terms) to be integrated as ODE.
old_history (nil) :: old_history is interactive input to be read from this list.
poly_only (nil) :: all equations are polynomials only.
potint_ (t) :: allowing ‘potential integration’.
print_ [pl] (12) :: maximal length of an expression to be printed.
print_all [pa] (nil) :: print all information about the PDEs.
print_more [pm] (t) :: print more informations about the PDEs.
quick_decoup (nil) :: whether decoupling should be done faster with less care for saving memory.
record_hist (nil) :: whether the history of equations is to be recorded.
safeint_ (t) :: use only solutions of ODEs with non-vanishing denominator.
session_ (“bu”+random number+date) :: when loading CRACK or executing.
size_watch (nil) :: whether before each computational step the size of the system shall be recorded in the global variable size_hist.
solvealg_ (nil) :: Use SOLVE for algebraic equations.
struc_eqn (nil) :: whether the equations have the form of structural equations (an application is Killing vector and Killing tensor computations).
subst_* :: maximal length of an expression to be substituted, used with diﬀerent values for diﬀerent procedures subst_level_*.
target_limit_* (nil) :: maximum of product length(PDE) * length(substituted expression) for a PDE which is to be used for a substitution. If target_limit_* = nil then no length limit, used with diﬀerent values for diﬀerent procedures subst_level_*.
time_ (nil) :: print the time needed for running CRACK.
time_limit (nil) :: whether a time limit is active after which batch-mode is interrupted to interactive mode.
tr_decouple [td] (nil) :: trace decoupling process.
tr_genint [ti] (nil) :: trace generalized integration.
tr_gensep [ts] (nil) :: trace generalized separation.
tr_main [tm] (nil) :: trace main procedure.
tr_orderings [to] (nil) :: trace orderings stuﬀ.
tr_redlength [tr] (nil) :: trace length reduction.

20.15.7 A More Detailed Description of Some of the Modules

The package CRACK contains a number of modules. The basic ones are for computing a pseudo-diﬀerential Gröbner Basis (using integrability conditions in a systematic way), integrating exact PDEs, separating PDEs, solving DEs containing functions of only a subset of all variables and solving standard ODEs (of Bernoulli or Euler type, linear, homogeneous and separable ODEs). These facilities will be described brieﬂy together with examples. The test ﬁle crack.tst (in the REDUCE packages/crack directory) demonstrates these and others.

Pseudo Diﬀerential Gröbner Basis

This module (called ‘decoupling’ in proc_list_) reduces derivatives in equations by using other equations and it applies integrability conditions to formulate additional equations which are subsequently reduced, and so on.

A general algorithm to bring a system of PDEs into a standard form where all integrability conditions are satisﬁed by applying a ﬁnite number of additions, multiplications and diﬀerentiations is based on the general theory of involutive systems [Riq10, Tho37, Jan29].

Essential to this theory is a total ordering of partial derivatives which allows assignment to each PDE of a Leading Derivative (LD) according to a chosen ordering of functions and derivatives. Examples for possible orderings are

lex. order of functions > lex. order of variables,
lex. order of functions > total diﬀerential order > lex. order of variables,
total order > lex. order of functions > lex. order of variables,

or mixtures of them by giving weights to individual functions and variables. Above, the “>” indicate “before” in priority of criteria. The principle is then to

1.: take two equations at a time and diﬀerentiate them as often as necessary to get equal LDs,
2.: regard these two equations as algebraic equations in the common LD and calculate the remainder w.r.t. the LD, i.e. to generate an equation without the LD by the Euclidean algorithm, and
3.: add this equation to the system.

Usually pairs of equations are taken ﬁrst, such that only one of the equations must be diﬀerentiated. If in such a generation step one of the equations is not diﬀerentiated then it is called a simpliﬁcation step and this equation will be replaced by the new equation.

The algorithm ends when each combination of two equations yields only equations which simplify to an identity modulo the other equations. A more detailed description is given e.g. in [BB89, Rei90].

Other programs implementing this algorithm are described e.g. in [Sch85b, BB89, FK89, Rei90, RWB96, RLW01] and [Man96].

In the interactive mode of CRACK it is possible to change the lexicographical ordering of variables, of functions, to choose between ‘total diﬀerential order’ ordering of variables or lexicographical ordering of variables and to choose whether lexicographical ordering of functions should have a higher priority than the ordering of the variables in a derivative, or not.

An example of the computation of a diﬀerential Gröbner Basis is given in the test ﬁle crack.tst.

Integrating Exact PDEs

The technical term ‘exact’ is adapted for PDEs from exterior calculus and is a small abuse of language but it is useful to characterize the kind of PDEs under consideration.

The purpose of the integration module in CRACK is to decide whether a given diﬀerential expression $D$ which involves unknown functions $f^i(x^j),\; 1\leq i\leq m$ of independent variables $x^j,\; 1\leq j\leq n$ is a total derivative of another expression $I$ w.r.t. some variable $x^k,\; 1\leq k\leq n$

\[ D(x^i,\; f^j,\; f^j,_p,\; f^j,_{pq}, \ldots ) = \frac {d I(x^i,\; f^j,\; f^j,_p,\; f^j,_{pq}, \ldots )}{d x^k}. \]

The index $k$ is reserved in the following for the integration variable $x^k$. With an appropriate function of integration $c^r$, which depends on all variables except $x^k$, it is no loss of generality to replace $0 = D$ by $0 = I + c^r$ in a system of equations.

Of course there always exists a function $I$ with a total derivative equal to $D$ but the question is whether for arbitrary $f^i$ the integral $I$ is functionally dependent only on the $f^i$ and their derivatives, and not on integrals of $f^i$.

Preconditions: $D$ is a polynomial in the $f^i$ and their derivatives. The number of functions and variables is free. For deciding the existence of $I$ only, the explicit occurrence of the variables $x^i$ is arbitrary. In order to actually calculate $I$ explicitly, $D$ must have the property that all terms in $D$ must either contain an unknown function of $x^k$ or must be formally integrable w.r.t. $x^k.$ That means if $I$ exists then only a special explicit occurrence of $x^k$ can prevent the calculation of $I$ and furthermore only in those terms which do not contain any unknown function of $x^k$. If such terms occur in $D$ and $I$ exists then $I$ can still be expressed as a polynomial in the $f^i, f^i,_j, \ldots $ and terms containing indeﬁnite integrals with integrands explicit in $x^k$.

Algorithm: Successive partial integration of the term with the highest $x^k$-derivative of any $f^i$. By that the diﬀerential order w.r.t. $x^k$ is reduced successively. This procedure is always applicable because steps involve only diﬀerentiations and the polynomial integration ($\int h^n\frac {\partial h}{\partial x}dx = h^{n+1}/(n+1)$) where $h$ is a partial derivative of some function $f^i$. For a more detailed description see [Wol00].

Stop: Iteration stops if no term with any $x^k$-derivative of any $f^i$ is left. If any $f^i(x^k)$ occurs in the remaining un-integrated terms then $I$ is not expressible with $f^i$ and its derivatives only. In case no $f^i(x^k)$ occurs, any remaining terms can contain $x^k$ only explicitly. Whether they can be integrated or not depends on their formal integrability. For their integration the REDUCE integrator is applied.

Speed up: The partial integration as described above preserves derivatives with respect to other variables. For example, the three terms $f,_x, f f,_{xxx}, f,_{xxy}$ cannot combine somehow to the same terms in the integral because if one ignores $x$-derivatives then it is clear that $f, f^2$ and $f,_y$ are three functionally independent expressions with respect to $x$-integrations. This allows the following drastic speed up for large expressions. It is possible to partition the complete sum of terms into partial sums such that each of them has to be integrable on its own. That is managed by generating a label for each term and collecting terms with the same label into partial sums. The label is produced by dropping all $x$-derivatives from all functions to be computed and dropping all factors which are not powers of derivatives of functions to be computed.

The partitioning into partial sums has two eﬀects. Firstly, if the integration of one partial sum fails then the remaining sums do not have to be tried for integration. Secondly, doing partial integration for each term means doing many subtractions. It is much faster to subtract terms from small sums than from large sums.

Example: We apply the above algorithm to

\begin{equation*} D := 2f,_yg' + 2f,_{xy}g + gg'^3 + xg'^4 + 3xgg'^2g'' = 0 \end{equation*}

with $f = f(x,y), \; g = g(x), \; '\equiv d/dx$. Starting with terms containing $g$ and at ﬁrst with the highest derivative $g,_{xx},$ the steps are

\[ \begin {array}{rcccl} \int 3xgg,_x^2g,_{xx} dx & = & \int d(xgg,_x^3) & - & \int \left ( \partial _x(xg) g,_x^3\right ) dx \\ \\ & = & xgg,_x^3 & - & \int g,_x^3(g + xg,_x) dx, \end {array} \]

\[ I := I + xgg,_x^3 \]

\[ D := D - g,_x^3(g + xg,_x) - 3xgg,_x^2g,_{xx} \]

The new terms $- g,_x^3(g + xg,_x)$ are of lower order than $g,_{xx}$ and so in the expression $D$ the maximal order of $x$-derivatives of $g$ is lowered. The conditions that $D$ is exact are the following.

The leading derivative must occur linearly before each partial integration step.
After the partial integration of the terms with ﬁrst-order $x$-derivatives of $f$ the remaining $D$ must not contain $f$ or other derivatives of $f$, because such terms cannot be integrated w.r.t. $x$ without specifying $f$.

The result of $x$- and $y$-integration in the above example is (remember $g=g(x)$)

\[ 0 = 2fg + xygg,_x^3 + c_1(x) + c_2(y) \; \; (=I). \]

CRACK can now eliminate $f$ and substitute for it in all other equations.

Generalization: If after applying the above basic algorithm, terms are left which contain functions of $x^k$ but each of these functions depends only on a subset of all $x^i, \; 1\leq i\leq n$, then a generalized version of the above algorithm can still provide a formal expression for the integral $I$ (see [Wol00]). The price consists of additional diﬀerential conditions, but they are equations in fewer variables than occur in the integrated equation. Integrating for example

\begin{equation} \tilde {D} = D + g^2(y^2 + x\sin y + x^2e^y) \label {crack-Dnew} \end{equation}

by introducing as few new functions and additional conditions as possible gives for the integral $\tilde {I}$

\begin{eqnarray*} \tilde {I} & = & 2fg + xygg,_{x}^{3} + c_1(x) + c_2(y) \\ & & + \frac {1}{3}y^3c_3'' - \cos y(xc_3'' - c_3) + e^y(x^2c_3'' - 2xc_3' + 2c_3) \end{eqnarray*}

with $c_3 = c_3(x), \; '\equiv d/dx$ and the single additional condition $g^2 = c_3'''$. The integration of the new terms of \eqref {crack-Dnew} is achieved by partial integration again, for example

\begin{eqnarray*} \int g^2x^2 dx & = & x^2\int g^2 dx - \int (2x\!\int g^2 dx) dx \\ & = & x^2\int g^2 dx - 2x\int \!\!\int g^2 dx + 2 \int \!\!\int \!\!\int g^2 dx \\ & = & x^2c_3'' - 2xc_3' + 2c_3. \end{eqnarray*}

Characterization: This algorithm is a decision algorithm which does not involve any heuristic. After integration, the new equation is still a polynomial in $f^i$ and in the new constant or function of integration. Therefore the algorithms for bringing the system into standard form can still be applied to the PDE-system after the equation $D = 0$ is replaced by $I = 0$.

The complexity of algorithms for bringing a PDE-system into a standard form depends nonlinearly on the order of these equations because of the nonlinearly increasing number of diﬀerent leading derivatives and by that the number of equations generated intermediately by such an algorithm. It therefore in general pays oﬀ to integrate equations during such a standard form algorithm.

If an $f^i$, which depends on all variables, can be eliminated after an integration, then depending on its length it is in general helpful to substitute $f^i$ in other equations and to reduce the number of equations and functions by one. This is especially proﬁtable if the replaced expression is short and contains only functions of fewer variables than $f^i$.

Test: The corresponding test input is

depend f,x,y;
depend g,x;
crack({2*df(f,y)*df(g,x)+2*df(f,x,y)*g+g*df(g,x)**3
       +x*df(g,x)**4+3*x*g*df(g,x)**2*df(g,x,2)
       +g**2*(y**2+x*sin y+x**2*e**y)},
      {}, {f,g}, {});

The meaning of the REDUCE command depend is to declare that $f$ depends in an unknown way on $x$ and $y$. For more details on the algorithm see [Wol00].

Direct Separation of PDEs

As a result of repeated integrations the functions in the remaining equations have fewer and fewer variables. It therefore may happen that after a substitution an equation results where at least one variable occurs only explicitly and not as an argument of an unknown function. Consequently all coeﬃcients of linearly independent expressions in this variable can be set to zero individually.

Example: $f = f(x,y), \;\; g = g(x), \;\; x,y,z$ are independent variables. The equation is

\begin{equation} 0 = f,_y + z(f^2+g,_x) + z^2(g,_x+yg^2) \label {crack-sep} \end{equation}

$x$-separation? $\rightarrow $ no
$y$-separation? $\rightarrow $ no
$z$-separation? $\rightarrow $ yes: $0 \,=\, f,_y \,=\, f^2+g,_x \,=\, g,_x+yg^2$
$y$-separation? $\rightarrow $ yes: $0 = g,_x = g^2$ (from the third equation from the $z$-separation)

If $z^2$ had been replaced in \eqref {crack-sep} by a third function $h(z)$ then direct separation would not have been possible. The situation changes if $h$ is a parametric function which is assumed to be independently given and which should not be calculated, i.e. $f$ and $g$ should be calculated for any arbitrary given $h(z)$. Then the same separation could have been done with an extra treatment of the special case $h,_{zz} = 0$, i.e. $h$ linear in $z$. This diﬀerent treatment of unknown functions makes it necessary to input explicitly the functions to be calculated as the third argument to CRACK. The input in this case would be

depend f,x,y;
depend g,x;
depend h,z;
crack({df(f,y)+z*f**2+(z+h)*df(g,x)+h*y*g**2}, {},
      {f,g}, {z});

The fourth parameter for CRACK is necessary to make clear that in addition to the variables of $f$ and $g$, $z$ is also an independent variable.

If the ﬂag independence_ is not nil then CRACK will stop if linear independence of the explicit expressions of the separation variable (in the example $1,z,z^2$) is not clear and ask interactively whether separation should be done or not.

Indirect Separation of PDEs

For the above direct separation a precondition is that at least one variable occurs only explicitly or as an argument of parametric functions. The situation where each variable is an argument of at least one function but no function contains all independent variables of an equation needs a more elaborate treatment.

The steps are these

A variable $x_a$ is chosen which occurs in as few functions as possible. This variable will be separated directly later which requires that all unknown functions $f_i$ containing $x_a$ are to be eliminated. Therefore, as long as $F:=\{f_i\}$ is not empty do the following:
- Choose the function $f_i(y_p)$ in $F$ with the smallest number of variables $y_p$ and with $z_{ij}$ as those variables on which $f_i$ does not depend.
- Identify all diﬀerent products $P_{ik}$ of powers of $f_i$-derivatives and of $f_i$ in the equation. Determine the $z_{ij}$-dependent factors $C_{ik}$ of the coeﬃcients of $P_{ik}$ and store them in a list.
- For each $C_{il}$ ($i$ ﬁxed, $l=1,\ldots $) choose a $z_{ij}$ and:
  - divide by $C_{il}$ the equation and all following elements $C_{im}$ with $m>l$ of this list, such that these elements are still the actual coeﬃcients in the equation after the division,
  - diﬀerentiate the equation and the $C_{im}, m>l$ w.r.t. $z_{ij}$.
The resulting equation no longer contains any unknown function of $x_a$ and can be separated w.r.t. $x_a$ directly in case $x_a$ still occurs explicitly. In both cases the equation(s) is (are) free of $x_a$ afterwards and inverting the sequence of integration and multiplication of all those equations (in case of direct separability) will also result in an equation(s) free of $x_a$. More exactly, the steps are
- multiplication of the equation(s) and the $C_{im}$ with $m<l$ by the elements of the $C_{ik}$-lists in exactly the inverse order,
- integration of these exact PDEs and the $C_{im}$ w.r.t. $z_{ij}$.
The equations originating that way are used to evaluate those functions which do not depend on $x_a$ and which survived in the above diﬀerentiations. Substituting these functions in the original equation may enable direct separability w.r.t. variables on which the $f_i$ do not depend on.
The whole procedure is repeated for another variable $x_b$ if the original DE could not be separated directly and still has the property that it contains only functions of a subset of all variables in the equation.

The additional bookkeeping of coeﬃcients $C_{ik}$ and their updating by division, diﬀerentiation, integration and multiplication is done to use them as integrating factors for the backward integration. The following example makes this clearer. The equation is

\begin{equation} 0 = f(x) g(y) - \frac {1}{2}xf'(x) - g'(y) - (1+x^2)y. \label {crack-isep} \end{equation}

The steps are (equal levels of indentation in the example correspond to those in the algorithm given above)

$x_1:=x, \, F=\{f\}$
- Identify $f_1:=f, \; \; \; \; \; y_1:=x, \; \; \; \; \; z_{11}:=y$
- and $P_1=\{f',f\}, \; \; \; \; \; C_1=\{1,g\}$
  - Divide $C_{12}$ and \eqref {crack-isep} by $C_{11}=1$ and diﬀerentiate w.r.t. $z_{11}=y:$
    \begin{eqnarray} 0 & = & fg' - g'' - (1+x^2) \label {crack-isep2} \\ C_{12} & = & g' \nonumber \end{eqnarray}
  - Divide \eqref {crack-isep2} by $C_{12}=g'$ and diﬀerentiate w.r.t. $z_{11}=y$:
    \[ 0 = - (g''/g')' - (1+x^2)(1/g')' \]
Direct separation w.r.t. $x$ and integration:
\[ \begin {array}{rclclcl} x^2: 0 & = & (1/g')' & \Rightarrow & c_1g' = 1 & \Rightarrow & g = y/c_1 + c_2 \\ x^0: 0 & = & (g''/g')' & \Rightarrow & c_3g' = g'' & \Rightarrow & c_3 = 0 \end {array} \]
Substitution of $g$ in the original DE
\[ 0 = (y/c_1+c_2)f - \frac {1}{2}xf' - 1/c_1 - (1+x^2)y \]
provides a form which allows CRACK standard methods to succeed by direct separation w.r.t. $y$
\[ \begin {array}{rclcl} y^1: 0 & = & f/c_1 - 1 - x^2 & \Rightarrow & f' = 2c_1x \\ y^0: 0 & = & c_2f - \frac {1}{2}xf' - 1/c_1 & \Rightarrow & 0 = c_2c_1(1+x^2) - c_1x^2 - 1/c_1 \end {array} \]
and direct separation w.r.t. $x$:
\begin{eqnarray*} x^0: 0 & = & c_2c_1 - c_1 \\ x^2: 0 & = & c_2c_1 - 1/c_1 \\ & \Rightarrow & 0 = c_1 - 1/c_1 \\ & \Rightarrow & c_1 = \pm 1 \Rightarrow c_2 = 1. \end{eqnarray*}

We get the two solutions $f = 1 + x^2, g = 1 + y$ and $f = - 1 - x^2, g = 1 - y$. The corresponding input to CRACK would be

depend f,x;
depend g,y;
crack({f*g-x*df(f,x)/2-df(g,y)-(1+x**2)*y},{},{f,g},{});

Solving Standard ODEs

For solving standard ODEs the package ODESOLVE by Malcolm MacCallum and Francis Wright [Mac89] is applied. This package is distributed with REDUCE and can be used independently of CRACK. The syntax of ODESOLVE is quite similar to that of CRACK:

depend function, variable;
odesolve(ODE, function, variable);

The applicability of ODESOLVE is increased by a CRACK-subroutine which recognizes such PDEs in which there is only one unknown function of all variables and all occurring derivatives of this function are only derivatives w.r.t. one variable of only one partial derivative. For example the PDE for $f(x,y)$

\[ 0 = f,_{xxy} + f,_{xxyy} \]

can be viewed as a ﬁrst order ODE in $y$ for $f,_{xxy}$.

Acknowledgement

Andreas Brand is the author of a number of core modules of CRACK. The currently used data structure and program structure of the kernel of CRACK are due to him. He contributed to the development of CRACK until 1997.

Francis Wright contributed code to REDUCE that provides simpliﬁcations of expressions involving symbolic derivatives and integrals. Also, CRACK makes extensive use of the REDUCE program ODESOLVE written by Malcolm MacCallum and Francis Wright.

Arrigo Triulzi contributed in supporting the use of diﬀerent total orderings of derivatives in doing pseudo-diﬀerential Gröbner Basis computations.

Work on this package has been supported by the Konrad Zuse Institute / Berlin through a fellowship of T.W.. Winfried Neun and Herbert Melenk are thanked for many discussions and constant support. Many of the low level control features have been provided by Winfried Neun. He ported Parallel REDUCE to a Linux PC Beowulf cluster and helped in adapting CRACK to it.

Anthony Hearn provided free copies of REDUCE to us as a REDUCE developers group which also is thankfully acknowledged.

PrevTail

Front

Hosted by

crack(	{equ\(_1\), equ\(_2\), …, equ\(_m\)},
	{ineq\(_1\), ineq\(_2\), …, ineq\(_n\)},
	{fun\(_1\), fun\(_2\), …, fun\(_p\)},
	{var\(_1\), var\(_2\), …, var\(_q\)});