Differential Algebra

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.