\chapter[CRACK: Overdetermined systems of DEs]%
        {CRACK: Solving overdetermined systems of PDEs or ODEs}
\label{CRACK}
\typeout{[CRACK: Overdetermined systems of DEs]}

{\footnotesize
\begin{center}
Thomas Wolf \\
School of Mathematical Sciences, Queen Mary and Westfield College \\
University of London \\
London E1 4NS, England \\[0.05in]
e--mail: T.Wolf@maths.qmw.ac.uk \\ [0.10in]
%%WWW: http://www.zib-berlin.de/Symbolik/crack.html \\[0.10in]
Andreas Brand \\ 
Institut f\"{u}r Informatik \\
Friedrich Schiller Universit\"{a}t Jena \\
07740 Jena, Germany \\[0.05in]
e--mail: maa@hpux.rz.uni-jena.de
\end{center}
}

\ttindex{CRACK}
The package CRACK aims at solving or at least partially
integrating single ordinary differential equations or partial
differential equations (ODEs/PDEs), and systems of them, exactly and in full 
generality.  Calculations done with input DEs include the
\begin{itemize}
\item integration of exact DEs and generalised exact DEs 
\item determination of monomial integrating factors
\item direct and indirect separation of DEs
\item systematic application of integrability conditions
\item solution of single elementary ODEs by using the REDUCE 
      package ODESOLVE (chapter~\ref{ODESOLVE}).
\end{itemize}
%More details are given in the manual CRACK.TEX.
Input DEs may be polynomially non-linear in the unknown functions
and their derivatives and may depend arbitrarily on the independent
variables.

Suitable applications of CRACK are the solution of
\begin{itemize}
\item overdetermined ODE/PDE-systems (overdetermined here just means
that the number of unknown functions of all independent variables
is less than the number of given equations for these functions).
\item simple non-overdetermined DE-systems (such as characteristic 
ODE-systems of first order quasilinear PDEs). 
\end{itemize}

The strategy is to have {\bf one} universal program (CRACK) which 
is as effective as possible for solving overdetermined PDE-systems 
and many application programs (such as LIEPDE) which merely generate an 
overdetermined PDE-system depending on what is to be investigated 
(for example, symmetries or conservation laws).

Examples are:
\begin{itemize}
\item the investigation of infinitesimal symmetries of DEs (LIEPDE),
\item the determination of an equivalent Lagrangian for second order 
      ODEs (LAGRAN)
\item the investigation of first integrals of ODEs which are polynomial
      in their highest derivative (FIRINT)
\item the splitting of an $n^{th}$ order ODE into a first order ODE and
      an $(n-1)^{th}$ order problem (DECOMP)
%%\item the search for conservation laws of PDEs (-systems) (CONLAW, not
%%      yet added to the library (Sep.\ 1995) but obtainable from T.W.)
\end{itemize}
Other applications where non-overdetermined problems are treated are
\begin{itemize}
\item the application of infinitesimal symmetries ({\em e.g.\
      }calculated by LIEPDE) in the package APPLYSYM (chapter~\ref{APPLYSYM}),
\item the program QUASILINPDE (also in the package APPLYSYM) 
      for solving single first order quasilinear PDEs.
\end{itemize}
The kernel package for solving overdetermined or simple non-overdetermined
DE-systems is accessible through a call to the program CRACK
in the package CRACK.  All the application programs (LIEPDE, LAGRAN,
FIRINT, DECOMP except APPLYSYM) are contained in the package CRACKAPP.
The programs APPLYSYM and QUASILINPDE are contained in the package
APPLYSYM (described in chapter~\ref{APPLYSYM}).

%%A short description of all the applications mentioned above including 
%%examples are given in an paper to be published in a special issue of
%%"Mathematical and Computer Modelling", ed. B.\ Fuchssteiner, V.\ Gerdt
%%and W.\ Oevel which also is available through ftp from
%%euclid.maths.qmw.ac.uk as preprint file pub/crack/demo.ps. More details are 
%%given in the files CRACK.TEX and APPLYSYM.TEX and input examples are available 
%%in the test files CRACK.TST and APPLYSYM.TST.

%%The latest versions of the programs, manuals and test files 
%%are available through ftp
%%from euclid.maths.qmw.ac.uk and the directory /pub/crack.

Details of the CRACK applications can be found in the example file.

{\tt 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, 
{\em 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 expressions which must not vanish identically for
any solution to be determined, {\em i.e.\ }only such solutions are
computed for which none of the {\it ineq}$_i$ vanishes identically in
all independent variables. 
\item
The dependence of the (scalar) functions ${\it fun}_j$ on possibly a
number of variables is assumed to have been defined with DEPEND rather
than declaring these functions as operators.  Their arguments may
themselves only be independent variables and not expressions.
\item
The functions ${\it fun}_j$ and their derivatives may only occur
polynomially.  Other unknown functions in ${\it equ}_i$ may be
represented as operators. 
\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 third argument is the empty list \{\}.
\item 
The dependence of the ${\it equ}_i$ on the independent variables and on
constants and functions other than ${\it fun}_j$ is arbitrary.
\end{itemize}

The result is a list of solutions 
\[      \{{\it sol}_1, \ldots \}  \]
where each solution is a list of 3 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$\} \>\}
\end{tabbing}
with integer $a, b, c, d, p, q, r.$
If {\tt CRACK} finds a contradiction as $0=1$ then there exists no
solution and it returns the empty list \{\}.
The empty list is also returned if no solution exists 
which does not violate the inequalities
{\it ineq}$_i \neq 0.$ 
For example, in the case of a linear system as input, there is
at most one solution ${\it sol}_1$.

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 {\tt CRACK}) or new
functions or constants which arose from integrations. 
The dependence of new functions on variables is declared with {\tt DEPEND}
and to visualise 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 exact behaviour of {\tt CRACK} can be modified by internal
variables, and there is a help system particularly associated with
{\tt CRACK}.  Users are referred to the detailed documentation for
more information.

