Algorithms and Implementations for Differential Elimination

Allan Wittkopf, Ph.D. defense

October 5th, 2004, at 11:00am in K9509.

Abstract: The primary focus of this work is the design and implementation 
of efficient differential elimination algorithms. Such algorithms use a 
finite number of differentiations and eliminations to simplify over
determined systems of ordinary and partial differential equations
(ODE and PDE) to a more tractable form. They can be used in exact solution
methods for ODE and PDE systems, as a preprocessor for numerical solution
of these systems, and for reduction of nonlinear PDE to linear PDE.

Differential elimination algorithms have been implemented to date in a 
number of symbolic languages, and although these algorithms are finite 
in theory, in practice, their complexity puts many interesting problems
out of reach.

We enlarge the class of problems which can be completed, by which we 
mean simplified to a form satisfying certain theoretical properties 
(canonical form in the linear case, and a form that yields an existence 
and uniqueness theorem in the nonlinear case). Additionally we provide 
means of obtaining partial information (in some cases the most relevant 
information) for many problems that cannot be completed.

Differential elimination relies heavily on other algorithms, such as
computation of multivariate polynomial greatest common divisors (GCDs).
As a result, significant contributions have also been made in this
area. These include enhanced versions of known algorithms for computing
multivariate polynomial GCDs for both dense (many terms for the given
degree) and sparse (few terms for the given degree) polynomials.

The differential elimination algorithms have been implemented in the
symbolic mathematics language Maple}, and one in the compiled language
C. We demonstrate their effectiveness on problems from symmetry 
analysis. The GCD algorithms have been implemented in Maple, and we 
provide a detailed asymptotic comparison of these algorithms with
Maple's primary GCD algorithm, and a well known algorithm for dense
polynomial problems.