reduce-historical/r38/packages/crack/crack.tex

\documentclass[12pt]{article}

%Sets size of page and margins
\oddsidemargin 10mm  \evensidemargin 10mm
\topmargin 0pt   \headheight 0pt   \headsep 0pt
\textwidth 15cm
 
\title{The computer algebra package {\sc Crack}
       for solving over-determined systems of equations}
 
\author{Thomas Wolf \\                        
        Department of Mathematics \\
        Brock University \\
        St.Catharines \\
        Ontario, Canada L2S 3A1 \\
        twolf@brocku.ca}

\begin{document}
\maketitle
\tableofcontents                                  
\section{Online help} 

\subsection{Help to help} 
\begin{tabbing}
  {\bf hd} \ \= Help to inspect data \\
  {\bf hp}   \> Help to proceed \\
  {\bf hf}   \> Help to change flags \& parameters \\
  {\bf hc}   \> Help to change data of equations \\
  {\bf hi}   \> Help to work with identities \\
  {\bf hb}   \> Help to trace and debug
\end{tabbing}

\subsection{Help to inspect data} 
\begin{tabbing}
  {\bf e}\ \ \ \ \= Print equations          \\
  {\bf eo}   \> Print overview of functions in equations  \\
  {\bf pi}   \> Print inequalities  \\ 
  {\bf f}    \> Print functions and variables        \\
  {\bf v}    \> Print all derivatives of all functions  \\
  {\bf s}    \> Print statistics                  \\
  {\bf fc}   \> Print no of free cells  \\
  {\bf pe}   \> Print an algebraic expression \\
  {\bf ph}   \> Print history of interactive input \\
  {\bf pv}   \> Print value of any lisp variable \\
  {\bf pd}   \> Plot the occurence of functions in equations \\
  {\bf ss}   \> Find and print sub-systems \\
  {\bf w}    \> Write equations into a file
\end{tabbing}

\subsection{Help to proceed} 
\begin{tabbing}
  {\bf a}\ \ \ \ \= Do one step automatically      \\        
  {\bf g}    \> Go on for a number of steps automatically    \\
  {\bf t}    \> Toggle between automatic and user selection of 
                equations ({\tt expert\_mode=nil/t}).  \\
  {\bf p1}   \> Print a list of all modules in batch mode \\
  {\bf p2}   \> Print a complete list of all modules \\
  {\bf \#}   \> Execute the module with the number `\#' once  \\
  {\bf l}    \> Execute a specific module repeatedly         \\
  {\bf sb}   \> Save complete backup to file \\
  {\bf rb}   \> Read backup from file \\
  {\bf ep}   \> Enable parallelism \\
  {\bf dp}   \> Disable parallelism \\
  {\bf pp}   \> Start an identical parallel process \\
  {\bf kp}   \> Kill a parallel process \\
  {\bf x}    \> Exit interactive mode for good            \\
  {\bf q}    \> Quit current level or crack if in level 0    \\        
\end{tabbing}

\subsection{Help to change flags \& parameters} 
\begin{tabbing}
  {\bf pl} \ \ \ \= Maximal length of an expression to be printed  \\
  {\bf pm}   \> Toggle to print more or less information about 
                        pdes ({\tt print\_more})    \\
  {\bf pa}   \> Toggle to print all or not all information 
                        about the pdes ({\tt print\_all}) \\
  {\bf cp}   \> Change the priorities of procedures   \\
  {\bf og}   \> Toggle ordering between `lexicographical 
                ordering of functions having\\
             \> a higher priority than any ordering of
                derivatives' and the opposite \\
             \> ({\tt lex\_fc=t}) resp.\ ({\tt lex\_fc=nil}) \\
  {\bf od}   \> Toggle ordering between `the total order
                of derivatives having a higher\\
             \> priority than lexicographical ordering' 
                ({\tt lex\_df=nil}) or not ({\tt lex\_df=t}) \\
  {\bf oi}   \> Interactive change of ordering on variables \\
  {\bf or}   \> Reverse ordering on variables \\
  {\bf om}   \> Mix randomly ordering on variables \\
  {\bf of}   \> Interactive change of ordering on functions     \\
  {\bf op}   \> Print current ordering  \\
  {\bf ne}   \> Root of the name of new generated equations
                        (default: e\_) \\
  {\bf nf}   \> Root of the name of new functions and constants
                        (default: c\_) \\
  {\bf ni}   \> Root of the name of new identities
                        (default: id\_) \\
  {\bf na}   \> Toggle for the NAT output switch ({\tt !*nat}) \\
  {\bf as}   \> Input of an assignment          \\
  {\bf kp}   \> Toggle for keeping a partitioned copy of each
                        equation ({\tt keep\_parti}) \\
  {\bf fi}   \> Toggle for allowing or not allowing
                        integrations of equations which \\
             \> involve unresolved integrals ({\tt freeint\_})  \\
  {\bf fa}   \> Toggle for allowing or not allowing solutions of ODEs
                        involving the \\
             \> {\tt abs} function ({\tt freeabs\_})  \\
  {\bf cs}   \> Switch on/off the confirmation of intended substitutions
                and of the \\
             \> order of the investigation of subcases 
                resulting in a factorization \\
  {\bf fs}   \> Enforce direct separation \\
  {\bf ll}   \> change of the line length \\
  {\bf re}   \> Toggle for allowing to re-cycle equation names
             ({\tt do\_recycle\_eqn})  \\
  {\bf rf}   \> Toggle for allowing to re-cycle function names
             ({\tt do\_recycle\_fnc}) \\
  {\bf st}   \> Setting a CPU time limit for un-interrupted run \\
  {\bf cm}   \> Adding a comment to the history\_ list \\
  {\bf lr}   \> Adding a LET-rule \\
  {\bf cr}   \> Clearing a LET-rule
\end{tabbing}

\subsection{Help to change data of equations} 
\begin{tabbing}
  {\bf r}\ \ \ \ \ \= Replace or add one equation \\
  {\bf n}    \> Replace one inequality      \\
  {\bf d}    \> Delete one equation         \\             
  {\bf c}    \> Change a flag or property of one pde  
\end{tabbing}

\subsection{Help to work with identities} 
\begin{tabbing}
  {\bf i}\ \ \ \ \ \= Print identities between equations \\
  {\bf id}   \> Delete redundand equations \\
  {\bf iw}   \> Write identities to a file \\
  {\bf ir}   \> Remove list of identities \\
  {\bf ia}   \> Add or replace an identity \\
  {\bf ih}   \> Start recording histories and identities \\
  {\bf ip}   \> Stop recording histories and identities \\
  {\bf ii}   \> Integrate an identity \\
  {\bf ic}   \> Check the consistency of identity data \\
  {\bf iy}   \> Print the history of equations
\end{tabbing}

\subsection{Help to trace and debug}
\begin{tabbing}
  {\bf tm}  \ \= Toggle for tracing the main procedure ({\tt tr\_main}) \\
  {\bf tg}    \> Toggle for tracing the generalized separation
                        ({\tt tr\_gensep}) \\
  {\bf ti}    \> Toggle for tracing the generalized integration  
                        ({\tt tr\_genint})  \\
  {\bf td}    \> Toggle for tracing the decoupling process
                        ({\tt tr\_decouple}) \\
  {\bf tl}    \> Toggle for tracing the decoupling length reduction
                        process ({\tt tr\_redlength}) \\
  {\bf ts}    \> Toggle for tracing the algebraic length reduction
                        process ({\tt tr\_short}) \\
  {\bf to}    \> Toggle for tracing the ordering procedures
                        process ({\tt tr\_orderings}) \\
  {\bf tr}    \> Trace an arbitrary procedure \\
  {\bf ut}    \> Untrace a procedure \\
  {\bf br}    \> Lisp break          \\                 
  {\bf pc}    \> Do a function call  \\
  {\bf in}    \> Reading in a REDUCE file
\end{tabbing}

\section{The purpose of  Crack}
The package {\sc Crack} attempts the solution of an overdetermined 
system of algebraic or ordinary or partial differential 
equations (ODEs/PDEs) with at most polynomial nonlinearities. 

Under `normal circumstances' differential 
equations (DEs) which describe physical
processes are not overdetermined, i.e.\ the number of DEs
matches the number of unknown functions which are involved.
Applying the package {\sc Crack} to such problems directly may be
successful, especially if these are ODEs, but the main type of
application is to investigate qualitative properties of such DEs/systems
of DEs and to solve the overdetermined PDE-systems that result in these
investigations.

Applications of {\sc Crack} include a program {\sc Conlaw}
for the computation of conservation laws of DEs, a program 
{\sc LiePDE} for the computation of infinitesimal symmetries of DEs
and a program {\sc ApplySym} for the computation of symmetry and 
similarity variables from infinitesimal symmetries.

\section{Technical details}  
\subsection{System requirements} 
The required system is {\sc Reduce}, version
3.6. or 3.7. (either the PSL version of {\sc Reduce} as distributed by
the Konrad Zuse Institut / Berlin or the CSL version of {\sc Reduce}
 as distributed by CODEMIST Ltd). The PSL version is faster whereas
the CSL version seems to be more stable under WINDOWS. Also it
provides a portable compiled code.

Memory requirements depend crucially on the
application. The {\tt crack.rlg} file is produced from running 
{\tt crack.tst} in a 4MB session running {\sc Reduce}, version 3.7 under
{\sc Linux}. On the other hand it is not difficult to formulate problems that 
consume any amount of memory.

\subsection{Installation}
In a running {\sc Reduce} session either do \\
\verb+    in "crack.red"$ + \\
or, in order to speed up computation, either compile it with 
\verb+    on comp$ + \\
before the above command, or, generate a fast-loading compiled 
file once with \\
\verb+    faslout "crack"$ + \\
\verb+    in "crack.red"$ + \\
\verb+    faslend$ + \\
and load that file to run {\sc Crack} with \\
\verb+    load crack$ + 

\subsection{Updates / web demos}
%%{\sc Crack} can be run from a web demo 
%A web demo under the address
%\verb+http://cathode.maths.qmw.ac.uk/demo.html+
%that was created by Francis Wright and Arrigo Triulzi
%allows to run problems of restricted size. 
The latest version of {\sc Crack} and related programs
is available from \\
\verb+http://lie.math.brocku.ca/twolf/crack/+.
Publications related to {\sc Crack} can be found under  \\
\verb+http://lie.math.brocku.ca/twolf/home/publications.html#1+.

\subsection{The files}
The following files are provided with {\sc Crack}
\begin{itemize}
\item {\tt crack.red} contains read-in statements of a number
of files {\tt cr*.red}.
\item {\tt crack.tst} contains test-examples.
\item {\tt crack.rlg} contains the output of {\tt crack.tst}.
\item {\tt crack.tex} is this manual.
\end{itemize}

\subsection{The call}
{\sc Crack} is called by
\begin{tabbing}
  {\tt crack}(\=\{{\it equ}$_1$, {\it equ}$_2$, \ldots , {\it equ}$_m$\},  \\
              \>\{{\it ineq}$_1$, {\it ineq}$_2$, \ldots , {\it ineq}$_n$\}, \\
              \>\{{\it fun}$_1$, {\it fun}$_2$, \ldots , {\it fun}$_p$\},  \\
              \>\{{\it var}$_1$, {\it var}$_2$, \ldots , {\it var}$_q$\});
\end{tabbing}     
        $m,n,p,q$ are arbitrary.
\begin{itemize}
\item
The {\it equ}$_i$ are identically vanishing partial differential expressions, 
i.e.\
they represent equations  $0 = {\it equ}_i$, which are to be solved for the 
functions ${\it fun}_j$ as far as possible, thereby drawing only necessary
conclusions and not restricting the general solution.
\item
The {\it ineq}$_i$ are algebraic or differential 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 {\it ineq}$_i$ vanishes identically in all independent 
variables.
\item
The dependence of the (scalar) functions ${\it fun}_j$ on independent 
variables must be defined beforehand with {\tt DEPEND} rather than
declaring these functions 
as operators. Their arguments may  themselves only be identifiers
representing variables, not expressions.
Also other unknown functions not in ${\it fun}_j$ must not be represented 
as operators but only using {\tt DEPEND}.
\item
The functions ${\it fun}_j$ and their derivatives may only occur polynomially.
\item
The ${\it var}_k$ are further independent variables, which are not
already arguments  
of any of the ${\it fun}_j$. If there are none then the fourth argument is 
the empty list \{\}, although it does no harm to include arguments of
functions ${\it fun}_j$.
\item 
The dependence of the ${\it equ}_i$ on the independent variables and on
constants and functions other than ${\it fun}_j$ is arbitrary.
\item
{\sc Crack} can be run in automatic batch mode (by default) or
interactively with the switch {\tt OFF BATCH\_MODE}.
\end{itemize}

\subsection{The result}  
The result is a list of solutions 
\[      \{{\it sol}_1, \ldots \}  \]
where each solution is a list of 4 lists:
\begin{tabbing}
    \{\=\{${\it con}_1, \; {\it con}_2, \ldots , \; {\it con}_q$\}, \\
      \>\{${\it fun}_a={\it ex}_a, \;\;
{\it fun}_b={\it ex}_b, \ldots , \;\; {\it fun}_p={\it ex}_p$\},\=  \\
      \>\{${\it fun}_c, \;\; {\it fun}_d, \ldots , \;\; {\it fun}_r$\}, \> \\
      \>\{{\it ineq}$_1$, {\it ineq}$_2$, \ldots , {\it ineq}$_s$\}. \>  \}
\end{tabbing}
For example, in the case of a linear system, the input consists of at
most one solution ${\it sol}_1$.

If {\sc Crack} finds a contradiction as e.g. $0=1$ then there exists no
solution and it returns the empty list \{\}. If {\sc Crack}
can factorize algebraically a non-linear equation then factors are set
to zero individually and different sub-cases are studied by
{\sc 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 satisfies the inequalities
{\it ineq}$_i \neq 0.$ 

The expressions ${\it con}_i$ (if there are any), are the
remaining necessary and sufficient conditions for the functions
${\it fun}_c,\ldots,{\it 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 {\sc Crack}) or new
functions or constants which arose from integrations. 
The dependence of new functions on variables is declared with {\tt DEPEND}
and to visualize this dependence the algebraic mode function
${\tt FARGS({\it fun}_i)}$ can be used.
If there are no ${\it con}_i$ then all equations are solved and the
functions in the third list are unconstrained. 
The second list contains
equations ${\it fun}_i={\it ex}_i$ where each ${\it fun}_i$ is an
original function and ${\it ex}_i$ is the computed expression
for ${\it fun}_i$.
The elements of the fourth
list are the expressions who have been assumed to be unequal zero
in the derivation of this solution.

\subsection{Interactive mode, flags, parameters and the list of procedures}
Under normal circumstances one will try to have problems solved
automatically by {\sc Crack}. An alternative is to input
{\tt OFF BATCH\_MODE;} before calling {\sc Crack} and to solve problems
interactively. In interactive mode it is possible to
\begin{itemize}
\item inspect data, like equations and their properties, unknown
functions, variables, identities, a statistics,
\item save, change, add or drop equations,
\item add inequalities,
\item inspect and change flags and parameters which govern individual
modules as well as their interplay,
\item pick a list of methods to be used out of about 30 different
ones, and specify their priorities and in this way very easily
compose an automatic solving strategy,
\item or, for more interactive work, to specify how to proceed, i.e.\
which computational step to do and how often, like doing
 \begin{description}
 \item one automatic step,
 \item one specific step,
 \item a number of automatic steps,
 \item a specific step as often as possible or a specified number of times.
 \end{description}
\end{itemize}
To get interactive help one enters `h' or `?'.

Flags and parameters are stored as symbolic fluid variables
which means that they can be accessed by {\tt lisp( ... )},
like {\tt lisp( print\_:=5 );} before calling {\sc Crack}.
{\tt 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 flags and parameters is given at the beginning of
the file {\tt crinit.red}. 

One more parameter shall be mentioned, which is the list of modules/procedures
called {\tt proc\_list\_}. In interactive mode this list can be looked
at with {\tt `p'} or be changed with {\tt `cp'}. This list defines
in which order the different modules/procedures are tried whenever
{\sc Crack} has to decide of what to do next. Exceptions
to this rule may be specified. For example, some procedure, say
$P_1$, requires after its execution another
specific procedure, say $P_2$, to be executed, no  matter whether
$P_2$ is next according to {\tt 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 {\tt `to\_do\_list'} are 
dealt with in the {\tt `to\_do'} step which should
always come first in {\tt proc\_list\_}. 
A way to have the convenience of running {\sc Crack} automatically
and still being able to break the fixed rhythm prescribed by {\tt
proc\_list\_} is to have the entry {\tt stop\_batch} in {\tt proc\_list\_}
and have {\sc Crack} started in automatic batch mode. Then execution
is continuing 
until none of the procedures which come before {\tt stop\_batch} are
applicable any more so that {\tt 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 the 
{\tt proc\_list\_} with {\tt `cp'} and to continue in automatic mode.

The default value of {\tt proc\_list\_} does not include all possible
modules because not all are suitable for any kind of overdetermined
system to be solved. The complete list is shown in interactive mode
under {\tt `cp'}. A few basic modules are described in the following
section. The efficiency of {\sc Crack} in automatic mode is very much
depending on the content of {\tt proc\_list\_} and the sequence of its
elements. Optimizing {\tt proc\_list\_} for a given task needs
experience which can not be formalized in a few simple rules and will
therefore not be explained in more detail here. The following remarks
are only guidelines.
\begin{description}    
\item[{\tt to\_do :}] hot list of steps to be taken next, should
always come first,
\item[{\tt subst\_level\_? :}] substitutions of functions by
expressions, substitutions differ by their maximal allowed size and other
properties,
\item[{\tt separation :}] what is described as direct separation in the
next section,
\item[{\tt gen\_separation :}] what is described as indirect separation in the
next section, only to be used for linear problems,
\item[{\tt quick\_gen\_separation :}] generalized separation of
equations with an upper size limit,
\item[{\tt quick\_integration :}] integration of very specific short equations,
\item[{\tt full\_integration :}] integration of equations which lead
to a substitution,
\item[{\tt integration :}] any integration,
\item[{\tt factorization :}] splitting the computation into the
investigation of different subcases resulting from the algebraic
factorization of an equation, only useful for non-linear problems,
\item[{\tt change\_proc\_list :}] reserved name of a procedure to be
written by the user that does nothing else but changing proc\_list\_ in
a fixed manner. This is to be used if the computation splits naturally
into different parts and if it is clear from the beginning what the
computational methods (proc\_list\_) have to be.
\item[{\tt stop\_batch :}] If the first steps to simplify or partially
solve a system of equations are known and should be done automatically
and afterwards {\sc Crack} should switch into interactive mode
then {\tt stop\_batch} is added to {\tt proc\_list} with a priority
just below the steps to be done automatically.
\item[{\tt drop\_lin\_dep :}] module to support
solving big linear systems (still experimental),
\item[{\tt find\_1\_term\_eqn :}] module to support
solving big linear systems (still experimental),
\item[{\tt trian\_lin\_alg :}] module to support
solving big linear systems (still experimental),
\item[{\tt undetlinode :}]  parametric solution of single under determined
linear ODE (with non-constant coefficients), 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 underdetermined equations is useful. Danger: new generated
equations become very big if the minimal order of any function in the ODE is high.),
\item[{\tt undetlinpde :}]  parametric solution of single under determined
linear PDE (with non-constant coefficients), only applicable for
linear problems (still experimental),
\item[{\tt alg\_length\_reduction :}] length reduction by algebraic
combination, only for linear problems, one has to be careful when
combining it with decoupling as infinite loops may occur when
shortening and lowering order reverse each other,
\item[{\tt diff\_length\_reduction :}] length reduction by differential
reduction,
\item[{\tt decoupling :}] steps towards the computation of a
differential Gr\"{o}bner Basis,
\item[{\tt add\_differentiated\_pdes :}] only useful for non-linear
differential equations with leading derivative occuring non-linearly,
\item[{\tt add\_diff\_star\_pdes :}] for the treatment of non-linear
indirectly separable equations,
\item[{\tt multintfac :}] to find integrating factors for a system
of equations, should have very slow priority if used at all,
\item[{\tt alg\_solve\_deriv :}] to be used for equations quadratic in
the leading derivative,
\item[{\tt alg\_solve\_system :}] to be used if a (sub-)system of
equations shall be solved for a set of functions or their derivatives
algebraically, 
\item[{\tt subst\_derivative :}] substitution of a derivative of a
function everywhere by a new function if such a derivative exists
\item[{\tt undo\_subst\_derivative :}] undo the above substitution.
\item[{\tt del\_redundant\_fc :}] Drop redundant functions and
constants. An overdetermined PDE-system is
formulated and solved to set
redundant constants / functions of integration to zero. This may take longer
if many functions occur.
\item[{\tt point\_trafo :}] An interactive point transformation not to
be used in automatic batch mode,
\item[{\tt sub\_problem :}] Solve a subset of equations first (still
experimental), 
\item[{\tt del\_redundant\_de :}] Delete redundant equations,
\item[{\tt idty\_integration :}] Integrate an identity (still experimental).
\end{description}

\subsection{Performing long computations}
\subsubsection{The backup facility}
If one does a long computation automatically then the computer or the
link to it may go down and the computation may have to be started again.
Even worse in a longer interactive session which is of an
exploring nature, i.e.\ where every step may blow up the size of
expressions or where a step (for example, decoupling, solving a subsystem,
searching for a length-reduction, dropping redundant functions,...) 
may just take too long and where
one would want to go back to the situation before this step and try
something else. For these situations there is an interactive command
for saving a bakup:
{\tt sb "file\_name"} which saves all global variables + data into an
ASCII file and a command {\tt rb "file\_name"} which reads these data from a file.
The format is independent of the computer used and independent
of the underlying {\sc Lisp} version. This has been used
by the author to set up long and complex computations on a small
computer and to continue the same interactive session on larger computers
later. To continue such a session one calls {\sc Crack} without data:
\verb+ CRACK({},{},{},{})$ +\\ %$
and loads the complete environment with {\tt rb "file\_name"}.
\subsubsection{The history facility}
Sometimes one does not only want to store an environment but also how one
got there in an interactive session, to repeat the same steps or only
some of them in a later session. 
In the global variable {\tt history\_} all interactive
input during one call of {\sc Crack} is recorded and can be looked at
during a {\sc Crack} run with the {\tt pv} (print-variable) command {\tt
pv history\_}. In order to save typing the same input in a later
session the program {\sc Crack} always tries to read any expected input
first from the global variable {\tt old\_history}. All that is needed
is to do is typing\\
{\tt lisp reverse history\_;}\\
after a run of {\sc Crack} and to assign the result to the {\sc Lisp}
variable {\tt old\_history}. The next run of {\sc Crack} will try to read
any expected interactive input first from {\tt old\_history} and only
if that is {\tt nil} then read it from the keyboard.

\subsection{Global variables}
The following is a complete list of identifiers used as global
lisp variables (to be precise symbolic fluid variables) 
within {\sc Crack}. Some are flags and parameters, others are glaboal
variables, some of them can be accessed after the {\sc Crack}
run. \vspace{6pt} \\
\noindent
{\tt !*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 \\
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\_}

\subsection{Global flags and parameters}
The list below gives a selection of
flags and global parameters that are available
to fine tune the performance according to specific 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
flag/parameter is given in [ ], default values of the flags/parameters
are given in (). The values of the flags and parameters can either be
set after loading {\sc Crack} and before starting {\sc Crack} with a
lisp assignment, for example,\\
\verb+lisp(print_:=8)$+ \\ %$
or after starting {\sc Crack} in interactive mode with specific commands, 
like {\tt pl} to change specifically the print length determining parameter
{\tt print\_}, or the command {\tt as} to do an assignment. The values of
parameters/flags can be inspected interactively using {\tt pv}.

\begin{description}    
\item[{\tt !*batch\_mode [x] (t) :}] running crack in interactive mode
({\tt !*batch\_mode=nil}) or not ({\tt !*batch\_mode=t}). It can also be 
set in algebraic mode before starting {\sc Crack}
by {\tt ON/OFF BATCH\_MODE}. Interactive mode can be left and automatic
computation be started by the interactive commant {\tt x}.
\item[{\tt expert\_mode [t] (nil) :}] For {\tt expert\_mode=t} the
equations that are involved in the next computational step are
selected by {\sc Crack}, for {\tt expert\_mode=nil} the user is asked
to select one or two equations which are to be worked with in the next
computational step. 
%\item[{\tt repeat\_mode [] () :}] 
\item[{\tt nfct\_ (1) :}] index of the next new function or constant
\item[{\tt nequ\_ (1) :}] index of the next new equation
\item[{\tt nid\_ (1) :}] index of the next new identity
\item[{\tt fname\_ [nf] ('c\_) :}] name of new functions and constants
                                   (integration)
\item[{\tt eqname\_ [ne] ('e\_) :}] name of new equations
\item[{\tt idname\_ [ni] ('id\_) :}] name of new equations
%\item[{\tt level\_ (nil) :}] actual level of crack recursion
\item[{\tt cont\_ (nil) :}] interactive user control for integration
 or substitution of large expressions (enabled = t)
\item[{\tt independence\_ (nil) :}] interactive control of linear 
                                    independence (enabled = t)
\item[{\tt genint\_ (15) :}]  if =nil then generalized integration disabled
                    else equal the maximal number of new functions and extra
                    equations due to the generalized integration of
                    one equation  
\item[{\tt facint\_ (1000) :}] if equal nil then no search for
                    integrating factors otherwise equal the  max
                    product terms*kernels for searching an integrating
                    factor
\item[{\tt potint\_ (t) :}] allowing `potential integration'
\item[{\tt safeint\_ (t) :}] uses only solutions of ODEs with
                    non-vanishing denominator
\item[{\tt freeabs\_ [fi] (t) :}] Do not use solutions of ODEs that
                    involve the {\tt abs} function
\item[{\tt freeint\_ [fi] (t) :}] Do only integrations if expl.\ part
                    is integrable 
\item[{\tt odesolve\_ (100) :}] maximal length of a de (number of terms) to be
                    integrated as ode
\item[{\tt max\_factor (400) :}] maximal number of terms to be factorized
\item[{\tt low\_gensep (6) :}] max.\ size of expressions to be separated in a 
                    generalized way by `quick\_gen\_separation'
\item[{\tt high\_gensep (300) :}] min. size of expressions to separate in a 
                    generalized way by `quick\_gen\_separation'
\item[{\tt new\_gensep (nil) :}] whether or not a newer (experimental)
                    form of gensep should be used
\item[{\tt subst\_* :}] maximal length of an expression to be substituted,
                    used with different values for different
                    procedures {\tt subst\_level\_*}
\item[{\tt cost\_limit5 (100) :}] maximal number of extra terms
                    generated by a subst.
\item[{\tt max\_red\_len (50000) :}] maximal product of lengths of two 
                    equations to be combined with length-reducing decoupling
\item[{\tt target\_limit\_* (nil) :}] maximal product
                    length(pde)*length(substituted expression) for
                    PDEs in which substitutions are to be made,
                    nil ==> no length limit,
                    used with different values for different
                    procedures {\tt subst\_level\_*}
\item[{\tt length\_inc (1.0) :}] factor by which the length of an 
                    expression may grow when performing 
                    {\tt diff\_length\_reduction}
\item[{\tt tr\_main [tm] (nil) :}] Trace main procedure
\item[{\tt tr\_gensep [ts] (nil) :}] Trace generalized separation
\item[{\tt tr\_genint [ti] (nil) :}] Trace generalized integration
\item[{\tt tr\_decouple [td] (nil) :}] Trace decoupling process
\item[{\tt tr\_redlength [tr] (nil) :}] Trace length reduction
\item[{\tt tr\_orderings [to] (nil) :}] Trace orderings stuff
\item[{\tt homogen\_ (nil) :}] Test for homogeneity of each equation 
                    (for debugging)
\item[{\tt solvealg\_ (nil) :}] Use SOLVE for algebraic equations
\item[{\tt print\_ [pl] (12) :}] maximal length of an expression to be printed
\item[{\tt print\_more [pm] (t) :}] Print more informations about the pdes
\item[{\tt print\_all [pa] (nil) :}] Print all informations about the pdes
\item[{\tt logoprint\_ (t) :}] print logo after crack call
\item[{\tt poly\_only (nil) :}] all equations are polynomials only 
\item[{\tt time\_ (nil) :}] print the time needed for running crack 
\item[{\tt dec\_hist (0) :}] length of pde history list during decoupling
\item[{\tt maxalgsys\_ (20) :}] max. number of equations to be solved
in specialsol 
\item[{\tt 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
%\item[{\tt orderings\_ (nil) :}] Stores the orderings list, nil initially   
%\item[{\tt simple\_orderings (t) :}] Turn off orderings support
%                   except for trivial case 
\item[{\tt lex\_df [od] (nil) :}] if t then use lexicographical
                    instead of total degree ordering of derivatives 
\item[{\tt lex\_fc [og] (t) :}] if t then lexicographical ordering of
                    functions has higher priority than any ordering of
                    derivatives 
\item[{\tt collect\_sol (t) :}] whether solutions found shall be collected and
                    returned together at the end or not (to save
                    memory), 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 a procedure
                 {\tt algebraic procedure crack\_out(eqns,assigns,freef,ineq)}
                    which is currently empty in file {\tt crmain.red}
                    but which is called for each solution.
\item[{\tt struc\_eqn (nil) :}] whether the equations has the form of
                    structural equations (an application are the
                    Killing vector and Killing tensor computations)
\item[{\tt quick\_decoup (nil) :}] whether decoupling should be done
                    faster with less care for saving memory
\item[{\tt idnties\_ (nil) :}] list of identities resulting from reductions and
                    integrability conditions
\item[{\tt record\_hist (nil) :}] whether the history of equations is
                    to be recorded 
\item[{\tt keep\_parti [kp] (nil) :}] whether for each equation a copy
                    in partitioned form is to be stored to speed up
                    several simplifications but which needs more memory
\item[{\tt size\_watch (nil) :}] whether before each computational step 
                   the size of the system shall be recorded in the
                   global variable size\_hist
\item[{\tt inter\_divint (nil) :}] whether the integration of divergence 
                   identities with more than 2 differentiation variables 
                   shall be confirmed interactively
\item[{\tt do\_recycle (nil) :}] whether function names shall be recycled 
                   or not (saves memory but computation is less clear to follow)
\item[{\tt old\_history (nil) :}] 
                   old\_history is interactive input to be read from
                   this list
\item[{\tt confirm\_subst [cs] (nil) :}] whether substitutions have to be 
                   confirmed interactively
\item[{\tt mem\_eff (t) :}] whether to be memory efficient even if slower
\item[{\tt force\_sep (nil) :}] whether direct separation should be forced even
                   if functions occur in the supposed to be linear
                   independent explicit expressions (for non-lin. prob.)
\end{description}

\section{Contents of the Crack package}
The package {\sc Crack} contains a number of modules. 
The basic ones are for computing a pseudo differential Gr\"{o}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 briefly together with examples. The test file
{\tt crack.tst} demonstrates these and others.

\subsection{Pseudo Differential Gr\"{o}bner Basis}
This module (called `decoupling' in {\tt 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 satisfied by applying
a finite number of additions, multiplications and differentiations
is based on the general theory of involutive systems \cite{Riq,Th,Ja}.

Essential to this theory is a total ordering of partial derivatives
which allows assignment to each PDE of a {\em Leading Derivative} 
(LD) according to a chosen ordering of functions
and derivatives. Examples for possible orderings are 
\begin{description}
\item lex.\ order of functions $>$ lex.\ order of variables,
\item lex.\ order of functions $>$ total differential order $>$ lex.\ 
      order of variables,
\item total order $>$ lex.\ order of functions $>$ lex.\ order of variables
\end{description}
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
\begin{description}
\item take two equations at a time and differentiate them as often as 
necessary to get equal LDs,
\item 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
\item add this equation to the system.
\end{description}
Usually pairs of equations are taken first, such that only one must be
differentiated. If in such a generation step one of both equations is not
differentiated then it is called a
simplification step and this equation will be replaced by the new equation.

The algorithm ends if 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 \cite{Alex,Reid1}.

Other programs implementing this algorithm are described e.g. in
\cite{FS,Alex,Fush,Reid1,Reid2,Reid3} and \cite{Mans}.

In the interactive mode of {\sc Crack} it is possible to change the
lexicographical ordering of variables, of functions, to choose between
`total differential 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 differential Gr\"{o}bner Basis is
given in the test file {\tt crack.tst}.

\subsection{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 {\sc Crack} is to  decide
whether a given differential
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 \underline{arbitrary} $f^i$ the integral
$I$ is functionally dependent only on the $f^i$ and their derivatives,
and \underline{not on integrals of $f^i.$} \\
\underline{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 
indefinite integrals with integrands explicit in $x^k.$ \\
\underline{Algorithm:} \\
Successive partial integration of the term with the highest
$x^k$-derivative of any $f^i.$ By that the 
differential order w.r.t. $x^k$ is reduced
successively. This procedure is always applicable because steps involve only
differentiations 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 \cite{WoInt}.\\
\underline{Stop:} \\
Iteration stops if no term with any $x^k$-derivative of any $f^i$ is left.
If in the remaining un-integrated terms any $f^i(x^k)$ itself occurs,
then $I$ is not expressible with $f^i$ and its derivatives only. In
case no $f^i(x^k)$ occurs then any remaining terms can contain $x^k$ only
explicitly. Whether they can be integrated depends on their formal
integrability. For their integration the {\sc Reduce} integrator is
applied. \\
\underline{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}$ can not 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 like three completely different expressions
from the point of view of $x$-integrations.
This allows the following drastic speed up
for large expressions. It is possible to partition the complete sum of
terms into partial sum such that each of the partial sum has to be
integrable on its own. That is managed by generating a label for each
term and collecting terms with equal 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 effects. 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.

\underline{Example :} \\
We apply the above algorithm to
\begin{equation}
D := 2f,_yg' + 2f,_{xy}g + gg'^3 + xg'^4 + 3xgg'^2g'' = 0
\label{D}
\end{equation}
with $f = f(x,y), \, g = g(x), \, '\equiv d/dx.$
Starting with terms containing $g$
and at first 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.
\begin{description}
\item The leading derivative must occur linearly before each partial
integration step. 
\item After the partial integration of the terms with first 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$.
\end{description}
The result of $x$- and $y$-integration in the above example is
(remember $g=g(x)$)
\begin{equation}
0 = 2fg + xygg,_x^3 + c_1(x) + c_2(y) \; \; (=I). \nonumber
\end{equation}
{\sc Crack} can now eliminate $f$ and substitute
for it in all other equations. \\
\underline{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 \cite{WoInt}). The price consists of
additional differential conditions, but they are equations in less 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{Dnew}
\end{equation}
by introducing as few 
new functions and additional conditions as possible gives as 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 (\ref{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*}
\underline{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 nonlinear increase of the number of different leading derivatives
and by that the number of equations generated intermediately by such
an algorithm. It therefore in general pays off 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
profitable if the replaced expression is short and 
contains only functions of less variables than $f^i.$ \\
\underline{Test:} \\
The corresponding test input is
\begin{verbatim}
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},{});
\end{verbatim}
The meaning of the {\sc Reduce} command {\tt depend} is to declare that $f$
depends in an unknown way on $x$ and $y$. For more details on the
algorithm see \cite{WoInt}.

\subsection{Direct separation of PDEs}
As a result of repeated integrations the functions in the 
remaining equations have less and less 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 coefficients of linearly independent expressions in this
variable can be set to zero individually. \\
{\em 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{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 (\ref{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 different treatment of unknown functions
makes it necessary to input explicitly the functions to be
calculated as the third argument to {\sc Crack}. The input
in this case would be
\begin{verbatim}
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});
\end{verbatim}
The fourth parameter for {\sc Crack} is necessary to make clear that
in addition to the variables of $f$ and $g$, $z$ is also an independent
variable.
 
If the flag {\tt independence\_} is not {\tt nil} then {\sc 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.

\subsection{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 
\begin{description}
 \item 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:
 \begin{description}
  \item 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.
  \item Identify all different 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 coefficients 
  of $P_{ik}$ and store them in a list.
  \item For each $C_{il}$ ($i$ fixed, $l=1,\ldots)$ choose a $z_{ij}$ and :
  \begin{description}
   \item 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 coefficients in the equation after the division,
   \item differentiate the equation and the $C_{im}, m>l$ w.r.t.\ $z_{ij}$
  \end{description}
 \end{description}
 \item 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
 \begin{description}
  \item 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,
  \item integration of these exact PDEs and the $C_{im}$ w.r.t.\ $z_{ij}$.
 \end{description}
 \item The equations originating that way are used to evaluate those
 functions which do not depend on $x_a$ and which survived in the above
 differentiations. Substituting these functions in the original equation,
 may enable direct separability w.r.t. variables on which the $f_i$
 do not depend on.
 \item 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.
\end{description}
The additional bookkeeping of coefficients $C_{ik}$ and their updating by
division, differentiation, 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{isep}
\end{equation}
The steps are (equal levels of indentation in the example correspond to
those in the algorithm given above)
\begin{description}
 \item $x_1:=x, \, F=\{f\}$
 \begin{description}
  \item Identify $f_1:=f, \; \; \; \; \; y_1:=x, \; \; \; \; \; z_{11}:=y$ 
  \item and $P_1=\{f',f\}, \; \; \; \; \; C_1=\{1,g\}$
  \begin{description}
   \item Divide $C_{12}$ and 
         (\ref{isep}) by $C_{11}=1$ and differentiate w.r.t. $z_{11}=y:$
         \begin{eqnarray}
         0 & = & fg' - g'' - (1+x^2)   \label{isep2}  \\
         C_{12} & = & g'    \nonumber
         \end{eqnarray}
 \item Divide (\ref{isep2}) by $C_{12}=g'$ and differentiate w.r.t. $z_{11}=y:$
\[ 0 = - (g''/g')' - (1+x^2)(1/g')' \]

  \end{description}
 \end{description}
 \item 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} \]
 \item 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 {\sc 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*}
\end{description}
We get the two solutions $f = 1 + x^2, g = 1 + y$ and 
$f = - 1 - x^2, g = 1 - y.$ The corresponding input to {\sc Crack} would be
\begin{verbatim}
depend f,x;
depend g,y;
crack({f*g-x*df(f,x)/2-df(g,y)-(1+x**2)*y},{},{f,g},{});
\end{verbatim}
 
\subsection{Solving standard ODEs}
For solving standard ODEs the package {\sc ODESolve} by Malcalm MacCallum and
Francis Wright  
\cite{Mal} is applied. This package is distributed with {\sc Reduce} 
and can be used independently of {\sc Crack}. The syntax of
{\sc ODESolve} is quite similar to that of {\sc Crack} \\
\verb+depend+ {\it function}, {\it variable}; \\
\verb+odesolve(+ODE, {\it function}, {\it variable});  \\
In the present form (1998) it solves standard first order ODEs
(Bernoulli and Euler type, with separable variables, $\ldots$) and linear
higher order ODEs with constant coefficients. 
An improved version is currently under preparation by Francis Wright.
The applicability of {\sc ODESolve} is 
increased by a {\sc 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 first order ODE in $y$ for $f,_{xxy}.$

\section{General hints}
\subsection{Problems involving $\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 {\tt let}-rules for simplifying
expressions. Before doing this the simplification rules at the end of
the file {\tt crinit.red} 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 \\
\verb+  trig1\_:={sin(~x)**2 => 1-cos(x)**2}$ + by the new rule \\
\verb+  trig1\_:={cos(~x)**2 => 1-sin(x)**2}$ +.
These rules are switched off when integrations are performed in order
not to interfere with the {\sc Reduce} Integrator.

\subsection{Exchanging time for memory}
The optimal order of applying different methods to the equations of a system
is not fixed. It does depend, for example, on the distributions of
unknown functions in the 
equations and on what the individual methods would produce in the next
step. For example, it is possible that the
decoupling module which applies integrability conditions through cross
differentiations 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 {\em before} this explosion started other methods should
have been tried (shortening of equations, any integrations, solution of
underdetermined 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 {\tt sb} command and
restart at this situation if necessary.

\section*{Acknowledgement}
Andreas Brand is the author of a number of core modules of {\sc
Crack}. The currently used data structure and program structure of the
kernel of {\sc Crack} are due to him. He contributed to the
development of {\sc Crack} until 1997.

Francis Wright contributed a module that provides simplifications
of expressions involving symbolic derivatives and integrals. Also, {\sc Crack}
makes extensive use of the {\sc Reduce} program {\sc ODESolve} written
by Malcolm MacCallum and Francis Wright.

Arrigo Triulzi contributed in supporting the use of different total
orderings of derivatives in doing pseudo differential Gr\"{o}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.

Anthony Hearn provided free copies of {\sc Reduce} to us as a
{\sc Reduce} developers group which also is thankfully acknowledged.

\begin{thebibliography}{99}
\bibitem{Riq} C. Riquier, Les syst\`{e}mes d'\'{e}quations aux d\'{e}riv\'{e}es
partielles, Gauthier--Villars, Paris (1910).
\bibitem{Th} J. Thomas, Differential Systems, AMS, Colloquium
publications, v. 21, N.Y. (1937).
\bibitem{Ja} M. Janet, Le\c{c}ons sur les syst\`{e}mes d'\'{e}quations aux 
d\'{e}riv\'{e}es, Gauthier--Villars, Paris (1929).
\bibitem{Topu} V.L. Topunov, Reducing Systems of Linear Differential
Equations to a Passive Form, Acta Appl. Math. 16 (1989) 191--206.
\bibitem{Alex} A.V. Bocharov and M.L. Bronstein, Efficiently
Implementing Two Methods of the Geometrical Theory of Differential
Equations: An Experience in Algorithm and Software Design, Acta. Appl.
Math. 16 (1989) 143--166.
\bibitem{Reid1} G.J. Reid, A triangularization algorithm which
determines the Lie symmetry algebra of any system of PDEs, J.Phys. A:
Math. Gen. 23 (1990) L853-L859.
\bibitem{Reid2} G. J. Reid, A. D. Wittkopf and A. Boulton, Reduction 
of systems of nonlinear partial differential equations to simplified
involutive forms, European Journal of Applied Mathematics,  
Vol 7. (1996) 604-635.
\bibitem{Reid3} G. J. Reid, A. D. Wittkopf and P. Lin, 
Differential-Elimination Completion Algorithms for Differential Algebraic
Equations and Partial Differential Algebraic Equations, to appear in
Studies in Applied Mathematics (Submitted July 1995).
\bibitem{FS} F. Schwarz, Automatically Determining Symmetries of Partial
Differential Equations, Computing 34, (1985) 91-106.
\bibitem{Fush} W.I. Fushchich and V.V. Kornyak, Computer Algebra
Application for Determining Lie and Lie--B\"{a}cklund Symmetries of
Differential Equations, J. Symb. Comp. 7, (1989) 611--619.
\bibitem{Mans} E.L. Mansfield,
The differential algebra package diffgrob2, Mapletech 3, (1996) 33-37 .
\bibitem{Ka} E. Kamke, Differentialgleichungen, L\"{o}sungsmethoden
und L\"{o}sungen, Band 1, Gew\"{o}hnliche Differentialgleichungen,
Chelsea Publishing Company, New York, 1959.
\bibitem{Wo} T. Wolf, An Analytic Algorithm for Decoupling and Integrating
systems of Nonlinear Partial Differential Equations, J. Comp. Phys.,
no. 3, 60 (1985) 437-446 and, Zur analytischen Untersuchung und exakten
L\"{o}sung von Differentialgleichungen mit Computeralgebrasystemen,
Dissertation B, Jena (1989).
\bibitem{WoInt} T. Wolf, The Symbolic Integration of Exact PDEs,
preprint, (1991).
\bibitem{WM} M.A.H. MacCallum, F.J. Wright, Algebraic Computing with REDUCE,
Clarendon Press, Oxford (1991).
\bibitem{Mal} M.A.H. MacCallum, An Ordinary Differential Equation
Solver for REDUCE, Proc. ISAAC'88, Springer Lect. Notes in Comp Sci.
358, 196--205.
\bibitem{Step} H. Stephani, Differential equations, Their solution using
symmetries, Cambridge University Press (1989).
\bibitem{LIEPDE} T. Wolf, An efficiency improved program {\sc LiePDE}
for determining Lie - symmetries of PDEs, Proceedings of the workshop on
Modern group theory methods in Acireale (Sicily) Nov. (1992)
\bibitem{Karp} V.I. Karpman, Phys. Lett. A 136, 216 (1989)
\bibitem{Cham} B. Champagne, W. Hereman and P. Winternitz, The computer
      calculation of Lie point symmetries of large systems of differential
      equation, Comp. Phys. Comm. 66, 319-340 (1991)

\end{thebibliography}
 
\end{document}