- Introduction:
- The Prelle-Singer Method
- An Extension To the Prelle-Singer Method
- PSsolver Package Summary and Examples
- Bibliography
- Conclusion:

`> `

**Title: An Extension of the
Prelle-Singer Method and a Maple Implementation**

**by L.G.S. Duarte, S.E.S. Duarte,
L.A.C.P. da Mota and J.E.F. Skea**

*Universidade do Estado do Rio de Janeiro
(UERJ), Brazil, *

*email: lduarte@dft.if.uerj.br,
eduarte@cbpf.br, damota@dft.if.uerj.br and jimsk@dft.if.uerj.br,*

*November, 22, 2001*

The Prelle-Singer method is a semi-decision
algorithm which can be used to solve analytically first order ordinary
differential equations (FOODEs) which have solutions in terms of elementary
functions. Here we present a software package in MapleV Release 5 (as far as we
could test, it works on release 7 as well) which implements both the
Prelle-Singer method in its original form and an extension of our own which
deals with first order ordinary differential equations whose solutions lie
outside the scope of the standard method.

The results presented here are
extracted from "L.G.S. Duarte, S.E.S. Duarte,
L.A.C.P. da Mota and J.E.F. Skea, *An Extension of
the Prelle-Singer Method and a Maple Implementation* " *in press on Computer Physics
Communications. *From now on we will reffer to
that paper as **[cpc].**

**Introduction: **

Before actualy introducing the ideas
concerning our program, let us first load it to the Maple section.
__(Please, put the library file into directory
`c:/DirectoryWhereIputtheLibrary`).__

`> `**restart;libname :=
`c:/DirectoryWhereIputtheLibrary`,libname;**

`> `**with(PSsolver);**

Warning, these names have been redefined: Darboux, EigenPval, PSBasis, PSIntFac, Signature, polygen

`> `

The problem of solving ordinary differential
equations (ODEs) has led, over the years, to a wide range of different methods
for their solution. Along with the many techniques for calculating tricky
integrals, these often occupy a large part of the mathematics syllabuses of
university courses in applied mathematics round the world. The layman often
imagines that behind computer algebra systems lies a large collection of
freshman tricks and techniques laboriously executed one by one until the correct
solution method is hit on. Computer algebra systems are `good at doing
integrals' because they are faster than humans at trying all these techniques.
Though, for reasons of speed, heuristic pattern-matching techniques are tried
initially by most computer algebra systems, it comes as a surprise that the best
computer algebra integration packages, when all else fails, use one fall-back
method --- the Risch algorithm **[2]**
. Given an integral the Risch algorithm tells you (in a
finite time) what the integral is in terms of elementary functions, if such an
expression exists. If the algorithm `fails', it is because no such closed-form
solution exists and the user can be content that no matter how many books of
tables of integrals he or she hunts in, the solution is not lurking in some
dusty corner of the library. The Risch algorithm is based on the fact that, if
the solution is elementary, we know its general form. It's just a matter of
calculating the correct combinations of functions, coefficients and powers that
appear. If we also know a limit on the degrees to which these functions can
appear in the solution (a degree bound), then we can guarantee that a closed
form integral does not exist if all possible combinations up to this degree have
been exhausted. It is the existence of this degree bound in Risch's method that
provides a fail safe terminating condition and turns the method into an
algorithm. The situation with ODEs is more complicated. One can regard the
problem of the analytic solution of an integral as a sub class of the problem of
solving ODEs analytically. One might then hope that the techniques used in the
Risch algorithm would also be applicable to ODEs. Unfortunately life is never
that simple. However a big step forward in constructing an algorithm for solving
first order ODEs (FOODEs) analytically was taken in a seminal paper by Prelle
and Singer (PS) **[3]** on autonomous systems of ODEs. Prelle and Singer's problem is
equivalent to asking when a FOODE of the form *y'=M(x,y)/N(x,y)* , with
*M* and
*N* polynomials in
their arguments, has an elementary solution (a solution which can be written in
terms of a combination of polynomials, logarithms, exponentials and radicals).
Prelle and Singer were not exactly able to construct an algorithm for solving
their problem, since they were not able to define a degree bound for the
polynomials which might enter into the solution. Though this is important from a
theoretical point of view, any computer implementation of the PS method will
have a practical degree bound imposed by the processing speed and/or memory
needed to handle the ever-more complex equations. With this in mind it is
possible to say that Prelle and Singer's original method is almost an algorithm,
awaiting a theoretical degree bound to turn it algorithmic. The purpose here is
to present an extension to the Prelle-Singer method allowing for the solution of
some FOODEs whose solutions contain a certain sub class of (non-elementary)
Liouvillian functions (this sub class includes the error function).

**The Prelle-Singer Method**

Despite its usefulness in solving FOODEs, the
Prelle-Singer procedure is not very well known outside mathematical circles, and
so we present

a brief overview of the main ideas of the procedure.

**Rational FOODEs** :

Consider the class of FOODEs which can be written as:

**y' = dy/dx = M(x,y)/N(x,y) (1)**

where M(x,y) and N(x,y) are polynomials with coefficients in the field of complex numbers, C.

In **[3]** , Prelle and Singer proved
that, if an elementary first integral of **(1)** exists, it is possible to find
an integrating factor with in C[x,y] (the ring of polynomials over x and
y with complex coefficients) for some integer n, such that

**= 0** **(2)**

The ODE can then be solved by quadrature. From
**(2)** we see that

**(3)**

Thus

**(4)**

where

**(5)**

Letting

**(6)**

where are irreducible polynomials
and are non-zero rational numbers, we
have from **(5)**

**(7)**

From **(4)** , plus the fact that M and N
are polynomials, we conclude that is a polynomial. Therefore, from
**(7)** , we see that
must divide . We thus have a criterion for
finding candidates for . Then, using **(4) **and **(7)** , we must have that

**= ** **(8)**

If we can find a set of and which solve **(8)** , we can construct the
integrating factor of the ODE and the solution of the ODE is reduced to a
quadrature. Risch's algorithm **[2]** can then be applied to this quadrature to determine whether a
solution exists in terms of elementary functions. Written in the form \

**= ** **, (9)**

for some polynomial , we see that the equation for the
has aspects similar to an eigenvalue
equation, and for that reason are sometimes called eigenpolynomials
**[6]** . However
current usage seems to prefer the term *Darboux
polynomials *(DPs), and we shall refer to the
as such.

**Algebraic and Transcendental
FOODEs**

In the standard PS procedure described above
it is assumed that the M(x,y) and N(x,y) which appear in **[3]** belong to C[x,y]. Of course,
many FOODEs which we want to solve do not fall into this class. However
Shtokhamer **[4] **has
extended the PS method to cover FOODEs with transcendental functions
(exponential and logarithmic functions of the variables, with complex
coefficients) and algebraic terms. To allow the PS method to treat
transcendental and algebraic terms appearing in M(x,y) and N(x,y), the original
variables of the ODE are initially supplemented by a basis of potentially
independent functions **(** **,** **,...,** **)** which appear in the ODE. A new function is considered potentially independent
if it is not a rational power of an element already in U. Therefore = sin(x) and = cos(x) are considered potentially
independent functions *for the purposes of
constructing U* , even though they are
algebraically dependent via the relation **= 1-** .

Since part of the PS method depends on the
construction of polynomials in the , any implementation of the PS method
must take into account this algebraic dependence at some point. Of course, if
this recognition of the dependence fails, the implementation of the PS-approach
can not assure to find the integrating factor up to the order considered. So, we
can only assure that our program will find integrating factors of given degrees
provided that no such dependencies are missed. For details please see
**[4] **and
**[cpc].**

**An Extension To the Prelle-Singer
Method**

Our aim in this section is to offer a brief
introduction to the ideas behind an extension to the Prelle-Singer method
**[1,8]** which
increases its scope of applicability to FOODEs with a class of non-elementary
solutions.

As has been mentioned, given sufficient time, the standard PS
method guarantees to find a solution for a FOODE of the form **y'=M(x,y)/N(x,y)** ( **M** and **N** polynomials in their arguments)
if this solution is expressible in terms of elementary functions. However the
method can also be used to solve some FOODEs whose solutions are not elementary.
The question therefore arises of what distinguishes those FOODEs with
non-elementary solutions which are solvable by the PS method from those that are
not. In what follows we study this question and show how this allows us to
extend the class of equations solvable by the PS method.

The following
two ODEs are examples I.211 and I.21 respectively of the standard testing ground
for ODE solvers by Kamke **[5]**

**(10)**

and

**(11)**

These ODEs have, respectively, the general
solutions

**, (12)**

and

**. (13)**

We note that neither solution is expressible in terms of
elementary functions. However, in the case of FOODE **(10)** , the PS method can be used to
find the solution **(12)** while the same is not true for FOODE **(11)** . To find out why, we look at
the integrating factor, **R** , for the ODEs which are, respectively,

**(14)**

and

**. (15)**

In both cases **R** is a product of elementary
functions, which we may write as

**(16)**

For **(10)
**the set of elementary functions is **{
** **}** , while for **(11) **this set is **{** **, ** **}** . Now the in **(16)** are all polynomials over the
building blocks which appear in the ODE **(10)** , but this is not the case for
**(11)** . Since the
standard PS procedure constructs integrating factor candidates from polynomials,
algebraic functions and logarithms in the functions which appear in the ODE,
exponentials of the type that appears in the factor are never considered and the solution
to **(11) **eludes the
standard PS method. However the above discussion points the way to a method
which extends the original PS procedure to deal with cases similar to
**(11)** . This method
is fully explained in **[cpc]** and **[7].**

**PSsolver Package Summary and
Examples**

**Summary**

A brief sumary of the commands of the package is as follows:

**PSsolve -
**solves FOODEs using the Prelle-Singer approach.
In addition to dealing with rational FOODEs (the scope of the standard PS
procedure), it also deals with FOODEs which contain elementary (algebraic and
transcendental) functions.

**PSIntFac -** returns an integrating factor for the FOODE.

**PSDop -** constructs the **D **operator associated with the FOODE.

**PSBasis -** builds a list of equations which define the basis of potentially
independent functions, **= f(x,y), ... **, used to construct the integrating factor for the FOODE.
**dPSBasis -** calculates the list of partial derivatives of the basis of
potentially independent functions **(e.g.,
** **)** .**Darboux -** calculates the DPs, i.e. the polynomials satisfying **D** = .**PSEigenval -** calculates the
polynomials that are the ``eigenvalues'' for the
equation **D** = .

A complete description of the commands in the
*PSsolver *package is
available in the on-line help. Please note that the on-line help must be
installed according to the instructions found on readme.mws. Here we have
described the commands that are implemented.

**Examples**

`> `**eq := diff(y(x),x) =
y(x)^2*(y(x)^2*ln(x)^5+4*y(x)*ln(x)^3+4*ln(x)+y(x)^2)/((y(x)*ln(x)^2+2)^2*x);**

`> `**dsolve(eq);**

`> `**PSIntFac(eq,1);**

`> `**PSsolve(eq,1);**

`> `**eq := diff(y(x),x) =
(-cos(x)*x*y(x)-cos(x)*x-cos(x)*1+y(x)+1+x*exp(y(x)))/(1+x*y(x));**

`> `**dsolve(eq);**

`> `**PSIntFac(eq,1,Extended);**

`> `**PSsolve(eq,1,Extended);**

**Bibliography**

[1] - M. Singer, Liouvillian First Integrals
of Differential Equations, Trans. Amer. Math. Soc., **333** , 673--688
(1992).

[2] - R.H. Risch, The Problem of Integration
in Finite Terms, *Trans. Amer. Math. Soc*
., **139** , 167--189, (1969).

[3] - M. Prelle and M. Singer,
Elementary first integrals of differential equations, *Trans. Amer. Math. Sol.* ,
**279,** 215,
(1983).

[4] - R. Shtokhamer, *Solving first
order differential equations using the Prelle-Singer algorithm* , **Technical report 88-09**
, Center for Mathematical Computation, University of
Delaware (1988).

[5] E. Kamke, *Differentialgleichungen: Lösungsmethoden und Lösungen*
. Chelsea Publishing Co, New York (1959).

[6] - Y.K.
Man and M.A.H. MacCallum, A Rational Approach to the Prelle-Singer Algorithm. J.
Symbolic Computatio, **11** , 1--11 (1996)

[7] - L.G.S. Duarte, S.E.S. Duarte, L.A.C.P.
da Mota and J.E.F. Skea, *Analyzing the Structure
of the Integrating Factors for First Order Ordinary Differential Equations with
Liouvillian Functions in the Solution* ., in Press
on J. Phys. A: Mathematical, Nuclear and General.

[8] - L.G.S. Duarte,
S.E.S. Duarte, L.A.C.P. da Mota and J.E.F. Skea, *A
Method to Tackle First Order Ordinary Differential Equations with Liouvillian
Functions in the Solution* , submitted to J. Phys.
A: Mathematical, Nuclear and General.

**Conclusion: **

The aim here has been to present the computer
package PSsolver which, as well as implementing the Prelle-Singer method for
solving first order ODEs, includes the implementation of an extension to the
method also described in the paper, which allows for the solutions of some
FOODEs with non-elementary solutions. The PS method is radically different from
other solution methods in that it is almost algorithmic and applicable to any
FOODE which has a solution in terms of elementary functions, *regardless of the form of the ODE* .
To help study the PS procedure in action, PSsolver comes with a set of commands
which allow the user to study all the intermediate steps of the PS-procedure,
from the construction of the basis of potentially independent functions and the
* D* operator
to the calculation of the DPs and the building of the integrating factor.
Because of its different approach we would expect that the PS method solves
FOODEs which elude other solvers. In our case the natural comparison is with
Maple's standard ODE solver,

* Disclaimer:* While every effort has been made to validate the solutions
in this worksheet, Waterloo Maple Inc. and the contributors are not responsible
for any errors contained and are not liable for any damages resulting from the
use of this material.