Algorithms and implementations for differential elimination

The 1)rimary 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.