Effective representation of rankings on partial derivatives
Oleg Golubitsky, University of Western Ontario
Friday, October 13, 2006, at U. of Waterloo.
Abstract:
Admissible term orders play an important role in computations with
multivariate polynomials and are well understood. Every term order admits a
canonical representation by a real matrix. Rankings on partial derivatives
play a similar role in computations with differential polynomials. Term
orders and permutations of a finite set are special cases of rankings.
Rewriting methods in differential algebra, from Riquier's algorithm to the
RosenfeldGroebner algorithm, rely on rankings.
Riquier introduced a particular type of rankings, which have been completely
described by Thomas in terms of matrices; these are the rankings implemented
in the Diffalg library in Maple. Kolchin gave an axiomatic definition of
rankings, more general than that of Riquier. Carra Ferro and Sit
characterized rankings as transitive families of generalized Dedekind cuts.
Rust and Reid proposed a representation of rankings by finitely many Riquier
prerankings and another one in terms of finitely many real parameters. Both
representations are not unique.
First, we show how to make Rust and Reid's representation by Riquier
prerankings unique, thus providing a canonical representation of rankings.
Second, we propose an efficient algorithm that, given a finite relation on
partial derivatives, determines whether it is contained in a ranking and, if
so, constructs such a ranking. This algorithm provides a convenient way to
specify rankings and plays a key role in transformation of differential
characteristic sets from one ranking to another, computation of universal
characteristic sets and differential Groebner fan.
