Symbolic Computation Group

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 Rosenfeld-Groebner 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 pre-rankings 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 pre-rankings 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.