1\documentclass[a4paper]{article} % LaTeX2e 2 3\usepackage{hyperref} 4 5\newcommand{\ODESolve}[1]{\texttt{ODESolve\,#1}} 6\newcommand{\odesolve}{\texttt{odesolve}} 7\newcommand{\REDUCE}{\textsc{Reduce}} 8 9\title{\ODESolve{1.065} : \\ An Enhanced \REDUCE{} ODE Solver} 10 11\author{Francis J. Wright \\ 12School of Mathematical Sciences \\ 13Queen Mary, University of London \\ 14Mile End Road, London E1 4NS, UK. \\ 15\texttt{F.J.Wright@qmw.ac.uk} \\ 16\href{http://centaur.maths.qmw.ac.uk/} 17{\texttt{http://centaur.maths.qmw.ac.uk/}}} 18 19\date{14 August 2001} 20 21\begin{document} 22\maketitle 23 24\tableofcontents 25 26\section{Introduction} 27 28\ODESolve{1+} is an experimental project to update and enhance the 29ordinary differential equation (ODE) solver (\odesolve{}) that has 30been distributed as a standard component of \REDUCE{} 31\cite{Hearn-manual,MacCallum-doc,MacCallum-ISSAC} for about 10 years. 32\ODESolve{1+} is intended to provide a strict superset of the 33facilities provided by \odesolve{}. This document describes a 34substantial re-implementation of previous versions of \ODESolve{1+} 35that now includes almost none of the original \odesolve{} code. This 36version is targeted at \REDUCE~3.7 or later, and will not run in 37earlier versions. This project is being conducted partly under the 38auspices of the European CATHODE project \cite{CATHODE}. Various test 39files, including three versions based on a published review of ODE 40solvers \cite{Zimmermann}, are included in the \ODESolve{1+} 41distribution. For further background see \cite{FJW1}, which describes 42version 1.03. See also \cite{FJW2}. 43 44\ODESolve{1+} is intended to implement some solution techniques itself 45(i.e.\ most of the simple and well known techniques \cite{Zwillinger}) 46and to provide an automatic interface to other more sophisticated 47solvers, such as PSODE \cite{Man,Man-MacCallum,Prelle-Singer} and 48CRACK \cite{CRACK-doc}, to handle cases where simple techniques fail. 49It is also intended to provide a unified interface to other special 50solvers, such as Laplace transforms, series solutions and numerical 51methods, under user request. Although none of these extensions is 52explicitly implemented yet, a general extension interface is 53implemented (see \S\ref{OEI}). 54 55The main motivation behind \ODESolve{1+} is pragmatic. It is intended 56to meet user expectations, to have an easy user interface that 57normally does the right thing automatically, and to return solutions 58in the form that the user wants and expects. Quite a lot of 59development effort has been directed toward this aim. Hence, 60\ODESolve{1+} solves common text-book special cases in preference to 61esoteric pathological special cases, and it endeavours to simplify 62solutions into convenient forms. 63 64 65\section{Installation} 66 67The file \texttt{odesolve.in} inputs the full set of source files that 68are required to implement \ODESolve{1+} \emph{assuming that the 69current directory is the \ODESolve{1+} source directory}. Hence, 70\ODESolve{1+} can be run without compiling it in any implementation of 71\REDUCE~3.7 by starting \REDUCE{} in the \ODESolve{1+} source 72directory and entering the statement 73\begin{verbatim} 741: in "odesolve.in"$ 75\end{verbatim} 76 77However, the recommended procedure is to compile it by starting 78\REDUCE{} in the \ODESolve{1+} source directory and entering the 79statements 80\begin{verbatim} 811: faslout odesolve; 822: in "odesolve.in"$ 833: faslend; 84\end{verbatim} 85In CSL-\REDUCE{}, this will work only if you have write access to the 86\REDUCE{} image file (\texttt{reduce.img}), so you may need to set up 87a private copy first. In PSL-\REDUCE{}, you may need to move the 88compiled image file \texttt{odesolve.b} to a directory in your PSL 89load path, such as the main fasl directory. Please refer to the 90documentation for your implementation of \REDUCE{} for details. Once 91a compiled version of \ODESolve{1+} has been correctly installed, it 92can be loaded by entering the \REDUCE{} statement 93\begin{verbatim} 941: load_package odesolve; 95\end{verbatim} 96 97A string describing the current version of \ODESolve{1+} is assigned 98to the algebraic-mode variable \verb|odesolve_version|, which can be 99evaluated to check what version is actually in use. 100 101In versions of \REDUCE{} derived from the development source after 22 102September 2000, use of the normal algebraic-mode \odesolve{} operator 103causes the package to autoload. However, the \ODESolve{1+} global 104switches are not declared, and the symbolic mode interface provided 105for backward compatibility with the previous version is not defined, 106until after the package has loaded. The former is not a huge problem 107because all \ODESolve{} switches can be accessed as optional 108arguments, and the backward compatibility interface should probably 109not be used in new code anyway. 110 111 112\section{User interface} 113 114The principal interface is via the operator \odesolve{}. (It also has 115a synonym called \texttt{dsolve} to make porting of examples from 116Maple easier, but it does not accept general Maple syntax!) For 117purposes of description I will refer to the dependent variable as 118``$y$'' and the independent variable as ``$x$'', but of course the 119names are arbitrary. The general input syntax is 120\begin{verbatim} 121odesolve(ode, y, x, conditions, options); 122\end{verbatim} 123All arguments except the first are optional. This is possible 124because, if necessary, \ODESolve{1+} attempts to deduce the dependent 125and independent variables used and to make any necessary 126\texttt{DEPEND} declarations. Messages are output to indicate any 127assumptions or dependence declarations that are made. Here is an 128example of what is probably the shortest possible valid input: 129\begin{verbatim} 130odesolve(df(y,x)); 131 132*** Dependent var(s) assumed to be y 133 134*** Independent var assumed to be x 135 136*** depend y , x 137 138{y=arbconst(1)} 139\end{verbatim} 140Output of \ODESolve{1+} messages is controlled by the standard 141\REDUCE{} switch \texttt{msg}. 142 143 144\subsection{Specifying the ODE and its variables} 145 146The first argument (\texttt{ode}) is \emph{required}, and must be 147either an ODE or a variable (or expression) that evaluates to an 148ODE\@. Automatic dependence declaration works \emph{only} when the 149ODE is input \emph{directly} as an argument to the \odesolve{} 150operator. Here, ``ODE'' means an equation or expression containing 151one or more derivatives of $y$ with respect to $x$. Derivatives of 152$y$ with respect to other variables are not allowed because 153\ODESolve{1+} does not solve \emph{partial} differential equations, 154and symbolic derivatives of variables other than $y$ are treated as 155symbolic constants. An expression is implicitly equated to zero, as 156is usual in equation solvers. 157 158The independent variable may be either an operator that explicitly 159depends on the independent variable, e.g.\ $y(x)$ (as required in 160Maple), or a simple variable that is declared (by the user or 161automatically by \ODESolve{1+}) to depend on the independent variable. 162If the independent variable is an operator then it may depend on 163parameters as well as the independent variable. Variables may be 164simple identifiers or, more generally, \REDUCE{} ``kernels'', e.g. 165\begin{verbatim} 166operator x, y; 167odesolve(df(y(x(a),b),x(a)) = 0); 168 169*** Dependent var(s) assumed to be y(x(a),b) 170 171*** Independent var assumed to be x(a) 172 173{y(x(a),b)=arbconst(1)} 174\end{verbatim} 175 176The order in which arguments are given must be preserved, but 177arguments may be omitted, except that if $x$ is specified then $y$ 178must also be specified, although an empty list \verb|{}| can be used 179as a ``place-holder'' to represent ``no specified argument''. 180Variables are distinguished from options by requiring that if a 181variable is specified then it must appear in the ODE, otherwise it is 182assumed to be an option. 183 184Generally in \REDUCE{} it is not recommended to use the identifier 185\verb|t| as a variable, since it is reserved in Lisp. However, it is 186very common practice in applied mathematics to use it as a variable to 187represent time, and for that reason \ODESolve{1+} provides special 188support to allow it as either the independent or a dependent variable. 189But, of course, its use may still cause trouble in other parts of 190\REDUCE! 191 192 193\subsection{Specifying conditions} 194 195If specified, the ``conditions'' argument must take the form of an 196(unordered) list of (unordered lists of) equations with either $y$, 197$x$, or a derivative of $y$ on the left. A single list of conditions 198need not be contained within an outer list. Combinations of 199conditions are allowed. Conditions within one (inner) list all relate 200to the same $x$ value. For example: 201\begin{description} 202\item[Boundary conditions:] ~ \\ 203\{\{y=y0, x=x0\}, \{y=y1, x=x1\}, ...\} 204 205\item[Initial conditions:] ~ \\ 206\{x=x0, y=y0, df(y,x)=dy0, ...\} 207 208\item[Combined conditions:] ~ \\ 209\{\{y=y0, x=x0\}, \{df(y,x)=dy1, x=x1\}, \{df(y,x)=dy2, y=y2, x=x2\}, ...\} 210\end{description} 211Here is an example of boundary conditions: 212\begin{verbatim} 213odesolve(df(y,x,2) = y, y, x, {{x = 0, y = A}, {x = 1, y = B}}); 214 215 2*x 2*x 2 216 - e *a + e *b*e + a*e - b*e 217{y=-----------------------------------} 218 x 2 x 219 e *e - e 220\end{verbatim} 221Here is an example of initial conditions: 222\begin{verbatim} 223odesolve(df(y,x,2) = y, y, x, {x = 0, y = A, df(y,x) = B}); 224 225 2*x 2*x 226 e *a + e *b + a - b 227{y=-------------------------} 228 x 229 2*e 230\end{verbatim} 231Here is an example of combined conditions: 232\begin{verbatim} 233odesolve(df(y,x,2) = y, y, x, {{x=0, y=A}, {x=1, df(y,x)=B}}); 234 235 2*x 2*x 2 236 e *a + e *b*e + a*e - b*e 237{y=--------------------------------} 238 x 2 x 239 e *e + e 240\end{verbatim} 241 242Boundary conditions on the values of $y$ at various values of $x$ may 243also be specified by replacing the variables by equations with single 244values or matching lists of values on the right, of the form 245\begin{center} 246y = y0, x = x0 247\end{center} 248or 249\begin{center} 250y = \{y0, y1, ...\}, x = \{x0, x2, ...\} 251\end{center} 252For example 253\begin{verbatim} 254odesolve(df(y,x) = y, y = A, x = 0); 255 256 x 257{y=e *a} 258 259odesolve(df(y,x,2) = y, y = {A, B}, x = {0, 1}); 260 261 2*x 2*x 2 262 - e *a + e *b*e + a*e - b*e 263{y=-----------------------------------} 264 x 2 x 265 e *e - e 266\end{verbatim} 267 268 269\subsection{Specifying options and defaults} 270 271The final arguments may be one or more of the option identifiers 272listed in the table below, which take precedence over the default 273settings. All options can also be specified on the right of equations 274with the identifier ``output'' on the left, e.g.\ ``output = basis''. 275This facility if provided mainly for compatibility with other systems 276such as Maple, although it also allows options to be distinguished 277from variables in case of ambiguity. Some options can be specified on 278the left of equations that assign special values to the option. 279Currently, only ``trode'' and its synonyms can be assigned the value 1 280to give an increased level of tracing. 281 282The following switches set default options -- they are all off by 283default. Options set locally using option arguments override the 284defaults set by switches. 285\begin{center} 286\begin{tabular}{lll} 287\bf Switch & \bf Option & \bf Effect on solution \\ 288\hline 289odesolve\_explicit & explicit & fully explicit \\ 290odesolve\_expand & expand & expand roots of unity \\ 291odesolve\_full & full & fully explicit and expanded \\ 292odesolve\_implicit & implicit & implicit instead of parametric \\ 293 & algint & turn on algint \\ 294odesolve\_noint & noint & turn off selected integrations \\ 295odesolve\_verbose & verbose & display ODE and conditions \\ 296odesolve\_basis & basis & output basis solution for linear ODE \\ 297 & trode \\ 298trode & trace & turn on algorithm tracing \\ 299 & tracing \\ 300odesolve\_fast & fast & turn off heuristics \\ 301odesolve\_check & check & turn on solution checking 302\end{tabular} 303\end{center} 304 305An ``explicit'' solution is an equation with $y$ isolated on the left 306whereas an ``implicit'' solution is an equation that determines $y$ as 307one or more of its solutions. A ``parametric'' solution expresses 308both $x$ and $y$ in terms of some additional parameter. Some solution 309techniques naturally produce an explicit solution, but some produce 310either an implicit or a parametric solution. The ``explicit'' option 311causes \ODESolve{1+} to attempt to convert solutions to explicit form, 312whereas the ``implicit'' option causes \ODESolve{1+} to attempt to 313convert parametric solutions (only) to implicit form (by eliminating 314the parameter). These solution conversions may be slow or may fail in 315complicated cases. 316 317\ODESolve{1+} introduces two operators used in solutions: 318\texttt{root\_of\_unity} and \texttt{plus\_or\_minus}, the latter 319being a special case of the former, i.e.\ a second root of unity. 320These operators carry a tag that associates the same root of unity 321when it appears in more than one place in a solution (cf.\ the 322standard \texttt{root\_of} operator). The ``expand'' option expands a 323single solution expressed in terms of these operators into a set of 324solutions that do not involve them. \ODESolve{1+} also introduces two 325operators \texttt{expand\_roots\_of\_unity} [which should perhaps be 326named \texttt{expand\_root\_of\_unity}] and 327\texttt{expand\_plus\_or\_minus}, that are used internally to perform 328the expansion described above, and can be used explicitly. 329 330The ``algint'' option turns on ``algebraic integration'' locally only 331within \ODESolve{1+}. It also loads the \texttt{algint} package if 332necessary. Algint allows \ODESolve{1+} to solve some ODEs for which 333the standard \REDUCE{} integrator hangs (i.e.\ takes an extremely long 334time to return). If the resulting solution contains unevaluated 335integrals then the algint switch should be turned on outside 336\ODESolve{1+} before the solution is re-evaluated, otherwise the 337standard integrator may well hang again! For some ODEs, the algint 338option leads to better solutions than the standard \REDUCE{} 339integrator. 340 341Alternatively, the ``noint'' option prevents \REDUCE{} from attempting 342to evaluate the integrals that arise in some solution techniques. If 343\ODESolve{1+} takes too long to return a result then you might try 344adding this option to see if it helps solve this particular ODE, as 345illustrated in the test files. This option is provided to speed up 346the computation of solutions that contain integrals that cannot be 347evaluated, because in some cases \REDUCE{} can spend a long time 348trying to evaluate such integrals before returning them unevaluated. 349This only affects integrals evaluated \emph{within} the \ODESolve{1+} 350operator. If a solution containing an unevaluated integral that was 351returned using the ``noint'' option is re-evaluated, it may again take 352\REDUCE{} a very long time to fail to evaluate the integral, so 353considerable caution is recommended! (A global switch called 354``noint'' is also installed when \ODESolve{1+} is loaded, and can be 355turned on to prevent \REDUCE{} from attempting to evaluate \emph{any} 356integrals. But this effect may be very confusing, so this switch 357should be used only with extreme care. If you turn it on and then 358forget, you may wonder why \REDUCE{} seems unable to evaluate even 359trivial integrals!) 360 361The ``verbose'' option causes \ODESolve{1+} to display the ODE, 362variables and conditions as it sees them internally, after 363pre-processing. This is intended for use in demonstrations and 364possibly for debugging, and not really for general users. 365 366The ``basis'' option causes \ODESolve{1+} to output the general 367solutions of linear ODEs in basis format (explained below). Special 368solutions (of ODEs with conditions) and solutions of nonlinear ODEs 369are not affected. 370 371The ``trode'' (or ``trace'' or ``tracing'') option turns on tracing of 372the algorithms used by \ODESolve{1+}. It reports its classification 373of the ODE and any intermediate results that it computes, such as a 374chain of progressively simpler (in some sense) ODEs that finally leads 375to a solution. Tracing can produce a lot of output, e.g.\ see the 376test log file ``\texttt{zimmer.rlg}''. The option ``\texttt{trode = 3771}'' or the global assignment ``\texttt{!*trode := 1}'' causes 378\ODESolve{1+} to report every test that it tries in its classification 379process, producing even more tracing output. This is probably most 380useful for debugging, but it may give the curious user further insight 381into the operation of \ODESolve{1+}. 382 383The ``fast'' option disables all non-deterministic solution techniques 384(including most of those for nonlinear ODEs of order $> 1$). It may 385be most useful if \ODESolve{1+} is used as a subroutine, including 386calling it recursively in a hook. It makes \ODESolve{1+} behave like 387the \odesolve{} distributed with \REDUCE{} versions up to and 388including 3.7, and so does not affect the \texttt{odesolve.tst} file. 389The ``fast'' option causes \ODESolve{1+} to return no solution fast in 390cases where, by default, if would return either a solution or no 391solution (perhaps much) more slowly. Solution of sufficiently simple 392``deterministically-solvable'' ODEs is unaffected. 393 394The ``check'' option turns on checking of the solution. This checking 395is performed by code that is largely independent of the solver, so as 396to perform a genuinely independent check. It is not turned on by 397default so as to avoid the computational overhead, which is currently 398of the order of 30\%. A check is made that each component solution 399satisfies the ODE and that a general solution contains at least enough 400arbitrary constants, or equivalently that a basis solution contains 401enough basis functions. Otherwise, warning messages are output. It 402is possible that \ODESolve{1+} may fail to verify a solution because 403the automatic simplification fails, which indicates a failure in the 404checker rather than in the solver. This option is not yet well 405tested; please report any checking failures to me (FJW). 406 407In some cases, in particular when an implicit solution contains an 408unevaluated integral, the checker may need to differentiate an 409integral with respect to a variable other than the integration 410variable. In order to do this, it turns on the differentiator switch 411``allowdfint'' globally. [I hope that this setting will eventually 412become the default.] In some cases, in particular in symbolic 413solutions of Clairaut ODEs, the checker may need to differentiate a 414composition of operators using the chain rule. In order to do this, 415it turns on the differentiator switch ``expanddf'' locally only. 416Although the code to support both these differentiator facilities has 417been in \REDUCE{} for a while, they both require patches that are 418currently only applied when \ODESolve{1+} is loaded. [I hope that 419these patches will eventually become part of \REDUCE{} itself.] 420 421 422\section{Output syntax} 423 424If \ODESolve{1+} is successful it outputs a list of sub-solutions that 425together represent the solution of the input ODE\@. Each sub-solution 426is either an equation that defines a branch of the solution, 427explicitly or implicitly, or it is a list of equations that define a 428branch of the solution parametrically in the form $\{y = G(p), x = 429F(p), p\}$. Here $p$ is the parameter, which is actually represented 430in terms of an operator called \texttt{arbparam} which has an integer 431argument to distinguish it from other unrelated parameters, as usual 432for arbitrary values in \REDUCE{}. 433 434A general solution will contain a number of arbitrary constants 435represented by an operator called \texttt{arbconst} with an integer 436argument to distinguish it from other unrelated arbitrary constants. 437A special solution resulting from applying conditions will contain 438fewer (usually no) arbitrary constants. 439 440The general solution of a linear ODE in basis format is a list 441consisting of a list of basis functions for the solution space of the 442reduced ODE followed by a particular solution if the input ODE had a 443$y$-independent ``driver'' term, i.e.\ was not reduced (which is 444sometimes ambiguously called ``homogeneous''). The particular 445solution is normally omitted if it is zero. The dependent variable 446$y$ does not appear in a basis solution. The linear solver uses basis 447solutions internally. 448 449Currently, there are cases where \ODESolve{1+} cannot solve a linear ODE 450using its linear solution techniques, in which case it will try 451nonlinear techniques. These may generate a solution that is not 452(obviously) a linear combination of basis solutions. In this case, if 453a basis solution has been requested, \ODESolve{1+} will report that it 454cannot separate the nonlinear combination, which it will return as the 455default linear combination solution. 456 457If \ODESolve{1+} fails to solve the ODE then it will return a list 458containing the input ODE (always in the form of a differential 459expression equated to 0). At present, \ODESolve{1+} does not return 460partial solutions. If it fails to solve any part of the problem then 461it regards this as complete failure. (You can probably see if this 462has happened by turning on algorithm tracing.) 463 464 465\section{Solution techniques} 466 467The \ODESolve{1+} interface module pre-processes the problem and applies 468any conditions to the solution. The other modules deal with the 469actual solution. 470 471\ODESolve{1+} first classifies the input ODE according to whether it 472is linear or nonlinear and calls the appropriate solver. An ODE that 473consists of a product of linear factors is regarded as nonlinear. The 474second main classification is based on whether the input ODE is of 475first or higher degree. 476 477Solution proceeds essentially by trying to reduce nonlinear ODEs to 478linear ones, and to reduce higher order ODEs to first order ODEs. 479Only simple linear ODEs and simple first-order nonlinear ODEs can be 480solved directly. This approach involves considerable recursion within 481\ODESolve{1+}. 482 483If all solution techniques fail then \ODESolve{1+} attempts to 484factorize the derivative of the whole ODE, which sometimes leads to a 485solution. 486 487 488\subsection{Linear solution techniques} 489 490\ODESolve{1+} splits every linear ODE into a ``reduced ODE'' and a 491``driver'' term. The driver is the component of the ODE that is 492independent of $y$, the reduced ODE is the component of the ODE that 493depends on $y$, and the sign convention is such that the ODE can be 494written in the form ``reduced ODE = driver''. The reduced ODE is then 495split into a list of ``ODE coefficients''. 496 497The linear solver now determines the order of the ODE\@. If it is 1 498then the ODE is immediately solved using an integrating factor (if 499necessary). For a higher order linear ODE, \ODESolve{1+} considers a 500sequence of progressively more complicated solution techniques. For 501most purposes, the ODE is made ``monic'' by dividing through by the 502coefficient of the highest order derivative. This puts the ODE into a 503standard form and effectively deals with arbitrary overall algebraic 504factors that would otherwise confuse the solution process. (Hence, 505there is no need to perform explicit algebraic factorization on linear 506ODEs.) The only situation in which the original non-monic form of the 507ODE is considered is when checking for exactness, which may depend 508critically on otherwise irrelevant overall factors. 509 510If the ODE has constant coefficients then it can (in principle) be 511solved using elementary ``D-operator'' techniques in terms of 512exponentials via an auxiliary equation. However, this works only if 513the polynomial auxiliary equation can be solved. Assuming that it can 514and there is a driver term, \ODESolve{1+} tries to use a method based 515on inverse ``D-operator'' techniques that involves repeated 516integration of products of the solutions of the reduced ODE with the 517driver. Experience (by Malcolm MacCallum) suggests that this normally 518gives the most satisfactory form of solution if the integrals can be 519evaluated. If any integral fails to evaluate, the more general method 520of ``variation of parameters'', based on the Wronskian of the solution 521set of the reduced ODE, is used instead. This involves only a single 522integral and so can never lead to nested unevaluated integrals. 523 524If the ODE has non-constant coefficients then it may be of Euler 525(sometimes ambiguously called ``homogeneous'') type, which can be 526trivially reduced to an ODE with constant coefficients. A shift in 527$x$ is accommodated in this process. Next it is tested for exactness, 528which leads to a first integral that is an ODE of order one lower. 529After that it is tested for the explicit absence of $y$ and low order 530derivatives, which allows trivial order reduction. Then the monic ODE 531is tested for exactness, and if that fails and the original ODE was 532non-monic then the original form is tested for exactness. 533 534Finally, pattern matching is used to seek a solution involving special 535functions, such as Bessel functions. Currently, this is implemented 536only for second-order ODEs satisfied by Bessel and Airy-integral 537functions. It could easily be extended to other orders and other 538special functions. Shifts in $x$ could also be accommodated in the 539pattern matching. [Work to enhance this component of \ODESolve{1+} is 540currently in progress.] 541 542If all linear techniques fail then \ODESolve{1+} currently calls the 543variable interchange routine (described below), which takes it into 544the nonlinear solver. Occasionally, this is successful in producing 545some, although not necessarily the best, solution of a linear ODE. 546 547 548\subsection{Nonlinear solution techniques} 549 550In order to handle trivial nonlinearity, \ODESolve{1+} first 551factorizes the ODE algebraically, solves each factor that depends on 552$y$ and then merges the resulting solutions. Other factors are 553ignored, but a warning is output unless they are purely numerical. 554 555If all attempts at solution fail then \ODESolve{1+} checks whether the 556original (unfactored) ODE was exact, because factorization could 557destroy exactness. Currently, \ODESolve{1+} handles only first and 558second order nonlinear exact ODEs. 559 560A version of the main solver applied to each algebraic factor branches 561depending on whether the ODE factor is linear or nonlinear, and the 562nonlinear solver branches depending on whether the order is 1 or 563higher and calls one of the solvers described in the next two 564sections. If that solver fails, \ODESolve{1+} checks for exactness 565(of the factor). If that fails, it checks whether only a single order 566derivative is involved and tries to solve algebraically for that. If 567successful, this decomposes the ODE into components that are, in some 568sense, simpler and may be solvable. (However, in some cases these 569components are algebraically very complicated examples of simple types 570of ODE that the integrator cannot in practice handle, and it can take 571a very long time before returning an unevaluated integral.) 572 573If all else fails, \ODESolve{1+} interchanges the dependent and 574independent variables and calls the top-level solver recursively. It 575keeps a list of all ODEs that have entered the top-level solver in 576order to break infinite loops that could arise if the solution of the 577variable-interchanged ODE fails. 578 579 580\subsubsection{First-order nonlinear solution techniques} 581 582If the ODE is a first-degree polynomial in the derivative then 583\ODESolve{1+} represents it in terms of the ``gradient'', which is a 584function of $x$ and $y$ such that the ODE can be written as ``$dy/dx = 585\textit{gradient}$''. It then checks \emph{in sequence} for the 586following special types of ODE, each of which it can (in principle) 587solve: 588\begin{description} 589\item[Separable] The gradient has the form $f(x)g(y)$, leading 590immediately to a solution by quadrature, i.e.\ the solution can be 591immediately written in terms of indefinite integrals. (This is 592considered to be a solution of the ODE, regardless of whether the 593integrals can be evaluated.) The solver recognises both explicit and 594implicit dependence when detecting separable form. 595 596\item[Quasi-separable] The gradient has the form $f(y+kx)$, which is 597(trivially) separable after a linear transformation. It arises as a 598special case of the ``quasi-homogeneous'' case below, but is better 599treated earlier as a case in its own right. 600 601\item[Homogeneous] The gradient has the form $f(y/x)$, which is 602algebraically homogeneous. A substitution of the form ``$y = vx$'' 603leads to a first-order linear ODE that is (in principle) immediately 604solvable. 605 606\item[Quasi-homogeneous] The gradient has the form $f(\frac{a_1x + 607b_1y + c_1}{a_2x + b_2y + c_2})$, which is homogeneous after a linear 608transformation. 609 610\item[Bernoulli] The gradient has the form $P(x) y + Q(x) y^n$, in 611which case the ODE is a first-order linear ODE for $y^{1-n}$. 612 613\item[Riccati] The gradient has the form $a(x)y^2 + b(x)y + c(x)$, in 614which case the ODE can be transformed into a \emph{linear} 615second-order ODE that may be solvable. 616\end{description} 617 618If the ODE is not first-degree then it may be linear in either $x$ or 619$y$. Solving by taking advantage of this leads to a parametric 620solution of the original ODE, in which the parameter corresponds to 621$y'$. It may then be possible to eliminate the parameter to give 622either an implicit or explicit solution. 623 624An ODE is ``solvable for $y$'' if it can be put into the form $y = 625f(x,y')$. Differentiating with respect to $x$ leads to a first-order 626ODE for $y'(x)$, which may be easier to solve than the original ODE. 627The special case that $y = xF(y') + G(y')$ is called a Lagrange (or 628d'Alembert) ODE\@. Differentiating with respect to $x$ leads to a 629first-order linear ODE for $x(y')$. The even more special case that 630$y = x y' + G(y')$, which may arise in the equivalent implicit form 631$F(xy'-y) = G(y')$, is called a Clairaut ODE\@. The general solution is 632given by replacing $y'$ by an arbitrary constant, and it may be 633possible to obtain a singular solution by differentiating and solving 634the resulting factors simultaneously with the original ODE. 635 636An ODE is ``solvable for $x$'' if it can be put into the form $x = 637f(y,y')$. Differentiating with respect to $y$ leads to a first-order 638ODE for $y'(y)$, which may be easier to solve than the original ODE. 639 640Currently, \ODESolve{1+} recognises the above forms only if the ODE 641manifestly has the specified form and does not try very hard to 642actually solve for $x$ or $y$, which perhaps it should! 643 644 645\subsubsection{Higher-order nonlinear solution techniques} 646 647The techniques used here are all special cases of Lie symmetry 648analysis, which is not yet applied in any general way. 649 650Higher-order nonlinear ODEs are passed through a number of 651``simplifier'' filters that are applied in succession, regardless of 652whether the previous filter simplifies the ODE or not. Currently, the 653first filter tests for the explicit absence of $y$ and low order 654derivatives, which allows trivial order reduction. The second filter 655tests whether the ODE manifestly depends on $x+k$ for some constant 656$k$, in which case it shifts $x$ to remove $k$. 657 658After that, \ODESolve{1+} tests for each of the following special 659forms in sequence. The sequence used here is important, because the 660classification is not unique, so it is important to try the most 661useful classification first. 662\begin{description} 663\item[Autonomous] An ODE is autonomous if it does not depend 664explicitly on $x$, in which case it can be reduced to an ODE in $y'$ 665of order one lower. 666 667\item[Scale invariant or equidimensional in $x$] An ODE is scale 668invariant if it is invariant under the transformation $x \to ax, y \to 669a^py$, where $a$ is an arbitrary indeterminate and $p$ is a constant 670to be determined. It can be reduced to an autonomous ODE, and thence 671to an ODE of order one lower. The special case $p = 0$ is called 672equidimensional in $x$. It is the nonlinear generalization of the 673(reduced) linear Euler ODE. 674 675\item[Equidimensional in $y$] An ODE is equidimensional in $y$ if it 676is invariant under the transformation $y \to ay$. An exponential 677transformation of $y$ leads to an ODE of the same order that 678\emph{may} be ``more linear'' and so easier to solve, but there is no 679guarantee of this. All (reduced) linear ODEs are trivially 680equidimensional in $y$. 681\end{description} 682 683The recursive nature of \ODESolve{1+}, especially the thread described 684in this section, can lead to complicated ``arbitrary constant 685expressions''. Arbitrary constants must be included at the point 686where an ODE is solved by quadrature. Further processing of such a 687solution, as may happen when a recursive solution stack is unwound, 688can lead to arbitrary constant expressions that should be re-written 689as simple arbitrary constants. There is some simple code included to 690perform this arbitrary constant simplification, but it is rudimentary 691and not entirely successful. 692 693 694\section{Extension interface}\label{OEI} 695 696The idea is that the ODESolve extension interface allows any user to 697add solution techniques without needing to edit and recompile the main 698source code, and (in principle) without needing to be intimately 699familiar with the internal operation of \ODESolve{1+}. 700 701The extension interface consists of a number of ``hooks'' at various 702critical places within \ODESolve{1+}. These hooks are modelled in 703part on the hook mechanism used to extend and customize the Emacs 704editor, which is a large Lisp-based system with a structure similar to 705that of \REDUCE\@. Each \ODESolve{1+} hook is an identifier which can 706be defined to be a function (i.e.\ a procedure), or have assigned to 707it (in symbolic mode) a function name or a (symbolic mode) list of 708function names. The function should be written to accept the 709arguments specified for the particular hook, and it should return 710either a solution to the specified class of ODE in the specified form 711or nil. 712 713If a hook returns a non-nil value then that value is used by 714\ODESolve{1+} as the solution of the ODE at that stage of the solution 715process. [If the ODE being solved was generated internally by 716\ODESolve{1+} or conditions are imposed then the solution will be 717re-processed before being finally returned by \ODESolve{1+}.] If a 718hook returns nil then it is ignored and \ODESolve{1+} proceeds as if 719the hook function had not been called at all. This is the same 720mechanism that it used internally by \ODESolve{1+} to run sub-solvers. 721If a hook evaluates to a list of function names then they are applied 722in turn to the hook arguments until a non-nil value is returned and 723this is the value of the hook; otherwise the hook returns nil. The 724same code is used to run all hooks and it checks that an identifier is 725the name of a function before it tries to apply it; otherwise the 726identifier is ignored. However, the hook code does not perform any 727other checks, so errors within functions run by hooks will probably 728terminate \ODESolve{1+} and errors in the return value will probably 729cause fatal errors later in \ODESolve{1+}. Such errors are user 730errors rather than \ODESolve{1+} errors! 731 732Hooks are defined in pairs which are inserted before and after 733critical stages of the solver, which currently means the general ODE 734solver, the nonlinear ODE solver, and the solver for linear ODEs of 735order greater than one (on the grounds that solving first order linear 736ODEs is trivial and the standard \ODESolve{1+} code should always 737suffice). The precise interface definition is as follows. 738 739A reference to an ``algebraic expression'' implies that the \REDUCE{} 740representation is a prefix or pseudo-prefix form. A reference to a 741``variable'' means an identifier (and never a more general kernel). 742The ``order'' of an ODE is always an explicit positive integer. The 743return value of a hook function must always be either nil or an 744algebraic-mode list (which must be represented as a prefix form). 745Since the input and output of hook functions uses prefix forms (and 746never standard quotient forms), hook functions can equally well be 747written in either algebraic or symbolic mode, and in fact \ODESolve{1+} 748uses a mixture internally. (An algebraic-mode procedure can return 749nil by returning nothing. The integer zero is \emph{not} equivalent 750to nil in the context of \ODESolve{1+} hooks.) 751 752\noindent\hrulefill 753 754\begin{description} 755\item[Hook names:] \verb|ODESolve_Before_Hook|, 756\verb|ODESolve_After_Hook|. 757\item[Run before and after:] The general ODE solver. 758\item[Arguments:] 3 759\begin{enumerate} 760\item The ODE in the form of an algebraic expression with no 761denominator that must be made identically zero by the solution. 762\item The dependent variable. 763\item The independent variable. 764\end{enumerate} 765\item[Return value:] A list of equations exactly as returned by 766\ODESolve{1+} itself. 767\end{description} 768 769\noindent\hrulefill 770 771\begin{description} 772\item[Hook names:] \verb|ODESolve_Before_Non_Hook|, 773\verb|ODESolve_After_Non_Hook|. 774\item[Run before and after:] The nonlinear ODE solver. 775\item[Arguments:] 4 776\begin{enumerate} 777\item The ODE in the form of an algebraic expression with no 778denominator that must be made identically zero by the solution. 779\item The dependent variable. 780\item The independent variable. 781\item The order of the ODE. 782\end{enumerate} 783\item[Return value:] A list of equations exactly as returned by 784\ODESolve{1+} itself. 785\end{description} 786 787\noindent\hrulefill 788\pagebreak 789 790\begin{description} 791\item[Hook names:] \verb|ODESolve_Before_Lin_Hook|, 792\verb|ODESolve_After_Lin_Hook|. 793\item[Run before and after:] The general linear ODE solver. 794\item[Arguments:] 6 795\begin{enumerate} 796\item A list of the coefficient functions of the ``reduced ODE'', 797i.e.\ the coefficients of the different orders (including zero) of 798derivatives of the dependent variable, each in the form of an 799algebraic expression, in low to high derivative order. [In general 800the ODE will not be ``monic'' so the leading (i.e.\ last) coefficient 801function will not be 1. Hence, the ODE may contain an essentially 802irrelevant overall algebraic factor.] 803\item The ``driver'' term, i.e.\ the term involving only the 804independent variable, in the form of an algebraic expression. The 805sign convention is such that ``reduced ODE = driver''. 806\item The dependent variable. 807\item The independent variable. 808\item The (maximum) order ($> 1$) of the ODE. 809\item The minimum order derivative present. 810\end{enumerate} 811\item[Return value:] A list consisting of a basis for the solution 812space of the reduced ODE and optionally a particular integral of the 813full ODE\@. This list does not contain any equations, and the dependent 814variable never appears in it. The particular integral may be omitted 815if it is zero. The basis is itself a list of algebraic expressions in 816the independent variable. (Hence the return value is always a list 817and its first element is also always a list.) 818\end{description} 819 820\noindent\hrulefill 821 822\begin{description} 823\item[Hook names:] \verb|ODESolve_Before_Non1Grad_Hook|, \\ 824\verb|ODESolve_After_Non1Grad_Hook|. 825\item[Run before and after:] The solver for first-order first-degree 826nonlinear (``gradient'') ODEs, which can be expressed in the form 827$dy/dx = \mathrm{gradient}(y,x)$. 828\item[Arguments:] 3 829\begin{enumerate} 830\item The ``gradient'', which is an algebraic expression involving (in 831general) the dependent and independent variables, to which the ODE 832equates the derivative. 833\item The dependent variable. 834\item The independent variable. 835\end{enumerate} 836\item[Return value:] A list of equations exactly as returned by 837\ODESolve{1+} itself. (In this case the list should normally contain 838precisely one equation.) 839\end{description} 840 841\noindent\hrulefill 842\bigskip 843 844The file \texttt{extend.tst} contains a very simple test and 845demonstration of the operation of the first three classes of hook. 846 847This extension interface is experimental and subject to change. 848Please check the version of this document (or the source code) for the 849version of \ODESolve{1+} you are actually running. 850 851 852\section{Change log} 853 854\begin{description} 855\item[27 February 1999] Version 1.06 frozen. 856\item[13 July 2000] Version 1.061 added an extension interface. 857\item[8 August 2000] Version 1.062 added the ``fast'' option. 858\item[21 September 2000] Version 1.063 added the ``trace'', ``check'' 859 and ``algint'' options, the ``Non1Grad'' hooks, handling of implicit 860 dependence in separable ODEs, and handling of the general class of 861 quasi-homogeneous ODEs. 862\item[28 September 2000] Version 1.064 added support for using `t' as 863 a variable and replaced the version identification output by the 864 \verb|odesolve_version| variable. 865\item[14 August 2001] Version 1.065 fixed obscure bugs in the 866 first-order nonlinear ODE handler and the arbitrary constant 867 simplifier, and revised some tracing messages slightly. 868 869\end{description} 870 871 872\section{Planned developments} 873 874\begin{itemize} 875 876\item 877Extend special-function solutions and allow shifts in $x$. 878 879\item 880Improve solution of linear ODEs, by (a) using linearity more generally 881to solve as ``CF + PI'', (b) finding at least polynomial solutions of 882ODEs with polynomial coefficients, (c) implementing non-trivial 883reduction of order. 884 885\item 886Improve recognition of exact ODEs, and add some support for more 887general use of integrating factors. 888 889\item 890Add a ``classify'' option, that turns on trode but avoids any actual 891solution, to report all possible (\@?) top-level classifications. 892 893\item 894Improve arbconst and arbparam simplification. 895 896\item 897Add more standard elementary techniques and more general techniques 898such as Lie symmetry, Prelle-Singer, etc. 899 900\item 901Improve integration support, preferably to remove the need for the 902``noint'' option. 903 904\item 905Solve systems of ODEs, including under- and over-determined ODEs and 906systems. Link to CRACK (Wolf) and/or DiffGrob2 (Mansfield)? 907 908\item 909Move more of the implementation to symbolic-mode code. 910 911\end{itemize} 912 913 914\begin{thebibliography}{99} 915 916\bibitem{CATHODE} CATHODE (Computer Algebra Tools for Handling 917Ordinary Differential Equations) 918\href{http://www-lmc.imag.fr/CATHODE/}% 919{\texttt{http://www-lmc.imag.fr/CATHODE/}}, 920\href{http://www-lmc.imag.fr/CATHODE2/}% 921{\texttt{http://www-lmc.imag.fr/CATHODE2/}}. 922 923\bibitem{Hearn-manual} A. C. Hearn and J. P. Fitch (ed.), 924\textit{REDUCE User's Manual 3.6}, RAND Publication CP78 (Rev. 7/95), 925RAND, Santa Monica, CA 90407-2138, USA (1995). 926 927\bibitem{MacCallum-ISSAC} M. A. H. MacCallum, An Ordinary Differential 928Equation Solver for REDUCE, \textit{Proc.\ ISSAC~'88, ed.\ P. Gianni, 929Lecture Notes in Computer Science} \textbf{358}, Springer-Verlag 930(1989), 196--205. 931 932\bibitem{MacCallum-doc} M. A. H. MacCallum, ODESOLVE, \LaTeX{} file 933\texttt{reduce/doc/odesolve.tex} distributed with \REDUCE~3.6. The 934first part of this document is included in the printed REDUCE User's 935Manual 3.6 \cite{Hearn-manual}, 345--346. 936 937\bibitem{Man} Y.-K. Man, \textit{Algorithmic Solution of ODEs and 938Symbolic Summation using Computer Algebra}, PhD Thesis, School of 939Mathematical Sciences, Queen Mary and Westfield College, University of 940London (July 1994). 941 942\bibitem{Man-MacCallum} Y.-K. Man and M. A. H. MacCallum, A Rational 943Approach to the Prelle-Singer Algorithm, \textit{J. Symbolic 944Computation}, \textbf{24} (1997), 31--43. 945 946\bibitem{Zimmermann} F. Postel and P. Zimmermann, A Review of the ODE 947Solvers of \textsc{Axiom}, \textsc{Derive}, \textsc{Maple}, 948\textsc{Mathematica}, \textsc{Macsyma}, \textsc{MuPAD} and 949\textsc{Reduce}, \textit{Proceedings of the 5th Rhine Workshop on 950Computer Algebra, April 1-3, 1996, Saint-Louis, France.} 951Specific references are to the version dated April 11, 1996. 952The latest version of this review, together with log files for each of 953the systems, is available from 954\href{http://www.loria.fr/~zimmerma/ComputerAlgebra/}% 955{\texttt{http://www.loria.fr/\textasciitilde zimmerma/ComputerAlgebra/}}. 956 957\bibitem{Prelle-Singer} M. J. Prelle and M. F. Singer, Elementary 958First Integrals of Differential Equations, \textit{Trans.\ AMS} 959\textbf{279} (1983), 215--229. 960 961\bibitem{CRACK-doc} T. Wolf and A. Brand, The Computer Algebra Package 962\texttt{CRACK} for Investigating PDEs, \LaTeX{} file 963\texttt{reduce/doc/crack.tex} distributed with \REDUCE~3.6. A shorter 964document is included in the printed REDUCE User's Manual 3.6 965\cite{Hearn-manual}, 241--244. 966 967\bibitem{FJW1} F. J. Wright, An Enhanced ODE Solver for REDUCE. 968\textit{Programmirovanie} No 3 (1997), 5--22, in Russian, and 969\textit{Programming and Computer Software} No 3 (1997), in English. 970 971\bibitem{FJW2} F. J. Wright, Design and Implementation of 972\ODESolve{1+} : An Enhanced REDUCE ODE Solver. CATHODE Workshop 973Report, Marseilles, May 1999, CATHODE (1999). \\ 974\href{http://centaur.maths.qmw.ac.uk/Papers/Marseilles/}% 975{\texttt{http://centaur.maths.qmw.ac.uk/Papers/Marseilles/}}. 976 977\bibitem{Zwillinger} D. Zwillinger, \textit{Handbook of Differential 978Equations}, Academic Press. (Second edition 1992.) 979 980\end{thebibliography} 981 982\end{document} 983