** Next:** Applications to linear overdetermined
** Up:** Background and Motivation
** Previous:** Buchberger's algorithm for polynomially

Ritt [70] introduced differential algebra, the algebraic study of
systems of polynomially nonlinear PDEs, and this
work was extensively developed by Kolchin [40].
Attempts to develop differential analogues of Buchberger's
algorithm for systems of polynomially nonlinear PDEs have encountered
considerable difficulties.
Carrà-Ferro [11] and Ollivier [51]
gave definitions of such differential Gröbner Bases (DGBs)
and methods (differential
Buchberger algorithms) for their attempted construction.
It was also shown that these bases could be infinite (unlike the
case for polynomial algebraic equations and linear PDE
systems).
Ollivier [51] gave a finite-step method which
could construct a DGB up to a given
order of derivative (even when the DGB was infinite). But criteria
were not given for determining when the DGB had been
constructed up to the given order.
In a breakthrough work, Mansfield [47] gave an
algorithm (and a computer-algebra implementation)
which used pseudo-reduction instead of reduction to attempt
to construct DGBs. Her algorithm always
terminates but not necessarily with the output system as a DGB.
She initiated the systematic study of the conditions for
obtaining a DGB.
These conditions entail the analysis of the coefficients which
may have to be inverted in the pseudo-division and pseudo-differential
reduction used by her algorithm.
Her algorithm has proved valuable in applications [21].
Recently, Boulier et. al. [5] gave an algorithm
which performs binary branching on the coefficients above.
In breakthrough work, they interpreted and rigorously proved that
the resulting system of cases, gives a representation of the
*radical of the differential ideal* generated by the system
(but not the differential ideal).
Besides the theoretical difficulties mentioned above,
there are the practical difficulties of designing efficient algorithms.
Buchberger's Algorithm, has been shown to be
of high (double-exponential) complexity [8],
in comparison to the low
polynomial complexity of the Gauss Algorithm. Since new unknowns
are continually introduced in the differential analogues of such
algorithms, their complexity is even worse. Thus practical implementation
is a vital concern.

In summary, the above methods aim to reduce systems of
algebraic equations or
PDEs to desirable forms using algorithmically executable operations.
Such operations include
differentiation and rational operations, but not integration.
Desirable forms include normal or standard forms
that can solve membership problems
(recognise when a given expression is a consequence of a system).
Such forms should be easier to solve using numerical or analytical methods.
Desirable features include being able
to apply existence and uniqueness theorems to such forms and
determine bounds on the number of their solutions.
These are key goals in our development of algorithms
for PDEs.

** Next:** Applications to linear overdetermined
** Up:** Background and Motivation
** Previous:** Buchberger's algorithm for polynomially
Greg Reid
2003-11-24