A ranking is essentially an ordering of all indeterminates in a system. To introduce rankings, we must first introduce some related concepts.

Dependent variable

This term describes any unknown function that is present in the input system. As an example, consider a system involving f(x,y) and its derivatives, g(x,y) and its derivatives, and exp(x). In a calculation, you may want to view f(x,y) as the solving variable, and g(x,y) as a parameter. Even in this case, these are both considered to be dependent variables. Because exp(x) is a known function, it is not considered to be a dependent variable.

Independent variable

For a problem containing f(x,y) and its derivatives, g(x,y) and its derivatives, and exp(x), x and y are the independent variables.

Constants

Any unknown not having a dependency, and not occurring in a dependency, is considered to be a constant. This is true even if it appears in a known function. For example, in the equation a*f(x,y)+sin(c)*g(x,y), both a and c are considered to be constants.

Note: The distinction between independent variables and constants is vital, since mistaking one for the other will not give a valid result for a system. For information on the specification of independent variables, please see rifsimp[options].

Indeterminate

An indeterminate can be any constant, dependent variable, or derivative of a dependent variable. This does not include any known functions or independent variables. This is exactly the group of items that a ranking is defined for.

With these definitions, a more precise definition of ranking for a system is now possible:

Ranking

A ranking is a strict ordering of all indeterminates appearing in a system in the course of a calculation. Note that it is necessary to define a ranking that works for more than just the indeterminates appearing in the initial system, because higher derivatives may appear in the course of the algorithm. For example, if the initial system contains only second order derivatives in the dependent variables, the specified ranking may need to be able to rank much higher order derivatives, as these may appear in a run of the algorithm.

Leading Indeterminate

The leading indeterminate of an equation is defined as the indeterminate in that equation that is of the highest rank (maximal with respect to the ranking).

The concept of a leading indeterminate is important for understanding how the rifsimp algorithm works, because any equation in which the leading indeterminate appears linearly is solved with respect to that indeterminate.

Rankings have a number of properties, some of which are required for the proper performance and termination of the algorithm, others of which may be helpful in tackling specific systems.

In any of the descriptions below, v1 and v2 are indeterminates that may depend on some of x1, x2, x3, ...

Preservation of ranking under differentiation

Given a ranking v1 > v2, this ranking also holds after equal differentiation of both v1 and v2 with respect to any independent variable, for all v1, v2 where v1 and v2 are indeterminates.

Note: You must restrict yourself to non-vanishing indeterminates (for example, for h(x) > g(x,y), differentiation with respect to y makes h(x) vanish, so the rule does not apply).

This property is required for the proper running of rifsimp. Once an equation is solved for the leading indeterminate, any differentiation of that equation (assuming that the leading indeterminate does not vanish) is also in solved form with respect to its new leading indeterminate (the derivative of the prior leading indeterminate).

Positive ranking

Given a ranking >, it must be true that diff(v1,x1) > v1 for all indeterminates v1 and all independent variables x1, as long as diff(v1,x1) is nonzero.

This property is required for the proper running of rifsimp, because it prevents any infinite chain of differential substitutions from occurring.

As an example, consider the solved form of the equation u[t]-u[tt] = 0 under a non-positive ranking u[t] = u[tt]. Differential elimination of the derivative u[xt] with respect to this equation will give u[xtt], then u[xttt], then u[xtttt], and so on. It will never terminate.

Total-degree ranking

Let dord() give the total differential order of an indeterminate with respect to all independent variables. Then for v1 and v2 derivatives of the same dependent variable, given a ranking >, then dord(v1) larger than dord(v2) implies v1 > v2.

For rifsimp to run correctly, a ranking does not have to be total degree. In some cases this does allow rifsimp to run faster, however. For those familiar with Groebner basis theory, a total degree ranking is similar to a total degree Groebner basis ordering, because calculations usually terminate more quickly than they would with a lexicographic ordering.

Orderly ranking

A ranking is said to be orderly if, for any indeterminate, no infinite sets of indeterminates that are lower in the ordering exist.

As an example of a ranking that is not orderly, we consider a ranking of f(x), g(x), and of all derivatives. If we choose to solve a system using rifsimp for f(x) in terms of g(x) (by specification of only f(x) in the solving variables), then this is not an orderly ranking, because g(x) and all of its derivatives are of lower rank than f(x) and any of its derivatives.

For rifsimp to run correctly,  using the defaults for nonlinear equations, a ranking is not required to be orderly (see rifsimp[nonlinear].)

The Default ranking

The rifsimp default ranking is an orderly, total-degree ranking that is both positive and preserved under differentiation. Note that if the solving variables are specified, we may no longer be using the default ranking (since specification of solving variables alters the ranking. See "Specification of a ranking" below.

On input, rifsimp assumes that all dependent variables present in the input system are solving variables, and that all constants are to be viewed as parameters. The set of dependent variables is then sorted alphabetically, along with the set of constants. In contrast, the set of independent variables is ordered based on order of appearance in the dependency lists of the dependent variables.

A description of the sorting method for independent variables can be found in the "Specification of a ranking" section. Note that this sort is used to break ties for derivatives of equal differential order (under some circumstances).

Under the above restriction, the default ranking is defined by the following algorithm, which returns true if v1 is greater than v2 with respect to the default ordering (and false if v1 is less than v2).

The following examples are for a system containing f(x,y,z), g(x,y), and h(x,z), and derivatives with the constants a and b. The system is recognized with the following (already sorted):

So, by default, f, g, and h are considered solving variables, and a and b parameters.

When the criteria are considered in order, any pair of distinct indeterminates are ranked by exactly one of them (as the ranking process then stops and returns the result). Of course to reach, say, criterion 3, criteria 1 and 2 must not differentiate the inputs. The following is a list of examples of each criterion in action:

Equivalence classes

Any step of the ranking process can be viewed as separating all possible indeterminates into a sorted chain of equivalence classes. When considering all criterion simultaneously, the size of each equivalence class must be exactly one. Sometimes viewing the ranking from the point of view of equivalence classes helps visualize how ranking is performed. As an example, we illustrate the equivalence classes for the prior example for each criterion considered independently of the other criteria:

Criterion 1: Rank solving variables higher than parameters

Criterion 2: Rank by differential order

Criterion 3: Rank by differential degree in each independent variable in turn

Criterion 4: Rank by dependent variable or constant name

So the process is equivalent to determining in which equivalence class each indeterminate falls, and checking if this criterion distinguishes the two input indeterminates.

Specification of a ranking

Three options can be used to control the ranking in rifsimp. Two of these perform simple modifications to the default ranking, while the third allows complete control of the ranking.

Specification of solve variables

As mentioned in the "Default ranking" section, specification of solving variables in a manner or order different from the default order changes the ranking. The solving variables can be specified in two ways:

1. Simple List

When the vars parameter is entered as a simple list, it affects the ranking in the following ways:

Criterion 1 of the default ranking is changed to add an additional class of indeterminates, which is specified by the solving variables. Specifically, any indeterminate mentioned in vars is ranked higher than any indeterminate not in vars. Any dependent variables not mentioned in vars are still ranked higher than any constants not mentioned in vars.

As an example, suppose an input system contained f(x,y,z), g(x,y), h(x,z), a, b, and c. If vars had been specified as [f(x,y,z),b,h(x,y)], then f, h, any f or h derivatives, and the constant c would be ranked higher than g and any g derivatives, which would be ranked higher than the constants a and b. Using equivalence classes, criterion 1 becomes

where the new equivalence class is on the right.

Criterion 4 of the default ranking is changed to reflect the same order as the specified vars, so when criterion 4 is reached, f is ranked higher than b, which in turn is ranked higher than g, which in turn is ranked higher than h, and so on.

Using equivalence classes, we have the following:

This is an unusual ranking (since it allows for c to be solved in terms of h, g, and derivatives of g), but it was chosen to highlight the flexibility of rankings.

2. Nested List

This is just a variation of the simple list specification that allows multiple equivalence classes to be specified. It is activated by the presence of a list in the vars input. When this specification is used, every entry in the vars list is interpreted as an equivalence class (even if it is not a list itself). This is best illustrated by an example. Use the same system as the prior example. If vars is specified as [f(x,y,z),[g(x,y),c]], we notice that the second entry is a list, so the equivalence classes for criterion 1 become

An equivalence class has been added for f and its derivatives, then one for g and c, and g derivatives, then the two that are created by default.

We can interpret this as "solve for f in terms of all other indeterminates; if the expression does not contain an f, then solve for g or c in terms of all other indeterminates, and so on".

Criterion 4 is changed to reflect the order in which the entries of vars appear in their equivalence classes:

Option: indep=[...]

This option allows for specification of the independent variables, but modifies the ordering as well. Put simply, it specifies the order in which criterion 3 looks at the dependent variables.

First, recall how the default ordering works. To begin with, the set of independent variables is sorted alphabetically. Then, the set of independent variables is sorted based on their occurrence in the dependent variable lists, where the dependent variable lists are considered in the same order in which they are ranked. If the order of a dependency list disagrees with the order of another dependency list, only the one of higher rank one is used.

As an example, consider a system containing f(x,y), g(y,x). In this case the independent variables are sorted in the order [x,y] if f is ranked higher than g, but in the order [y,x] if the reverse is true.

For a system containing f(x,y), g(x,z), the independent variables are sorted [x,y,z], because ties are broken alphabetically.

The specification of indep=[...] enforces the order specified in the list, so if the input contains f(x,y,z) and h(x,y,z) and we specify [z,x,y], then the independent variables are ordered as specified.

These two ways of controlling the ordering of a system are sufficient for most purposes, but you can also fully specify the exact ordering to be used for a system.

Advanced specification of a ranking

This method requires a bit of description first:

Say that we have a system with n independent variables (we call these x1,...,xn), and m dependent variables (we call these V1,...,Vm). For each derivative, we can then construct a list of n+m elements, where the first n elements are the differentiations of the derivative with respect to the corresponding independent variable, and the remaining m elements are all zero, except for the one that corresponds to the dependent variable of the derivative.

Ranking examples:

Say that we have a system with independent variables indep = [x,y,z], and dependent variables [f,g,h,s]. Then the vector for g[xxz] can be constructed as [2,0,1, 0,1,0,0]. This vector then contains all the information required to identify the original derivative. From the last four items in the list, we see that our dependent variable is g (since the 1 corresponds to the placement of g in the dependent variable list). We can also see from the first three elements of the list that it is differentiated twice with respect to x, 0 times with respect to y, and once with respect to z (where we are matching up the first three elements of the list to the corresponding independent variables).

With the same system, we may obtain:

Now we have specified a way to turn each derivative into a list of integer values. Using this, we now can create a new list called a criterion, which must be of the same length and must be specified with integer values. The dot product of the derivative list and the criterion is called the weight of that derivative with respect to the criterion.

So for the above example, if we specified the criterion list to be [1,0,0, 0,0,0,0], then g[xxz] would have weight 2, f[xyz] would have weight 1, h[xxxxx] would have weight 5, and so on.

Now when two derivatives are being compared with respect to one of these list criteria, the ranking would be determined by their respective weights. So, for example, f[xyz] < g[xxz] with respect to [1,0,0, 0,0,0,0], because $\mathrm{weight}\left(f_{\mathrm{xyz}}\right)=1$ is less than $\mathrm{weight}\left(g_{\mathrm{xxz}}\right)=2$ with respect to [1,0,0, 0,0,0,0].

The new ranking can then be constructed as a list of these criteria which, during a comparison, are calculated and compared in order. The construction of a ranking in this way is called a Janet ranking.

As an example, we can construct the default ranking as a criterion list for the example system as:

So if we compared f[xyz] to f[xyy], the weights for the first entry would be 1 and 1, for the second entry 3 and 3, for the third entry 1 and 1, and for the fourth entry 1 and 2, at which point it is recognized that f[xyz] < f[xyy].

Specification of the ranking to rifsimp

The ranking is specified on the command line to rifsimp as ranking = list of criteria, where the criterion list is as described above. We recommend that you specify the dependent variables and independent variables so that the order is known and the ranking behaves as expected.

Additional notes

In the event that the input ranking does not fully specify a ranking (two different indeterminates are not ranked differently by the input ranking), the default ranking is then used (see examples). If the system contains constants, and any of the entries of the input ranking do not have corresponding entries for these constants, then the entries are padded with zeros.

$\mathrm{with}\left(\mathrm{DEtools}\right)\&colon;$

$\mathrm{sys}≔\left[\mathrm{diff}\left(g\left(x\&comma;y\&comma;t\right)\&comma;x\&comma;x\right)+\mathrm{diff}\left(f\left(x\&comma;y\&comma;t\right)\&comma;x\&comma;y\right)+\mathrm{diff}\left(f\left(x\&comma;y\&comma;t\right)\&comma;y\&comma;y\right)+\mathrm{diff}\left(f\left(x\&comma;y\&comma;t\right)\&comma;t\right)=0\right]$

$\mathrm{sys}≔\left[\frac{{\partial }^2}{\partial x^2}g\left(x\&comma;y\&comma;t\right)+\frac{{\partial }^2}{\partial x\partial y}f\left(x\&comma;y\&comma;t\right)+\frac{{\partial }^2}{\partial y^2}f\left(x\&comma;y\&comma;t\right)+\frac{\partial }{\partial t}f\left(x\&comma;y\&comma;t\right)=0\right]$

$\mathrm{rifsimp}\left(\mathrm{sys}\right)$

$table\left(\left[\mathrm{Solved}=\left[\frac{{\partial }^2}{\partial x^2}g\left(x\&comma;y\&comma;t\right)=-\frac{{\partial }^2}{\partial x\partial y}f\left(x\&comma;y\&comma;t\right)-\frac{{\partial }^2}{\partial y^2}f\left(x\&comma;y\&comma;t\right)-\frac{\partial }{\partial t}f\left(x\&comma;y\&comma;t\right)\right]\right]\right)$

$\mathrm{rifsimp}\left(\mathrm{sys}\&comma;\left[f\right]\right)$

$table\left(\left[\mathrm{Solved}=\left[\frac{{\partial }^2}{\partial x\partial y}f\left(x\&comma;y\&comma;t\right)=-\frac{{\partial }^2}{\partial x^2}g\left(x\&comma;y\&comma;t\right)-\frac{{\partial }^2}{\partial y^2}f\left(x\&comma;y\&comma;t\right)-\frac{\partial }{\partial t}f\left(x\&comma;y\&comma;t\right)\right]\right]\right)$

$\mathrm{rifsimp}\left(\mathrm{sys}\&comma;\left[f\right]\&comma;\mathrm{indep}=\left[y\&comma;x\right]\right)$

$table\left(\left[\mathrm{Solved}=\left[\frac{{\partial }^2}{\partial y^2}f\left(x\&comma;y\&comma;t\right)=-\frac{{\partial }^2}{\partial x^2}g\left(x\&comma;y\&comma;t\right)-\frac{{\partial }^2}{\partial x\partial y}f\left(x\&comma;y\&comma;t\right)-\frac{\partial }{\partial t}f\left(x\&comma;y\&comma;t\right)\right]\right]\right)$

$\mathrm{sample\_rank}≔\left[\left[0\&comma;0\&comma;0\&comma;1\&comma;0\right]\&comma;\left[0\&comma;0\&comma;1\&comma;0\&comma;0\right]\right]\&colon;$

$\mathrm{ivars}≔\left[x\&comma;y\&comma;t\right]\&colon;$

$\mathrm{dvars}≔\left[f\&comma;g\right]\&colon;$

$\mathrm{rifsimp}\left(\mathrm{sys}\&comma;\mathrm{dvars}\&comma;\mathrm{indep}=\mathrm{ivars}\&comma;\mathrm{ranking}=\mathrm{sample\_rank}\right)$

$table\left(\left[\mathrm{Solved}=\left[\frac{\partial }{\partial t}f\left(x\&comma;y\&comma;t\right)=-\frac{{\partial }^2}{\partial x^2}g\left(x\&comma;y\&comma;t\right)-\frac{{\partial }^2}{\partial x\partial y}f\left(x\&comma;y\&comma;t\right)-\frac{{\partial }^2}{\partial y^2}f\left(x\&comma;y\&comma;t\right)\right]\right]\right)$

$\mathrm{sys}≔\left[\mathrm{diff}\left(f\left(x\&comma;t\right)\&comma;x\&comma;x\&comma;x\right)+\mathrm{diff}\left(f\left(x\&comma;t\right)\&comma;t\right)+\mathrm{diff}\left(f\left(x\&comma;t\right)\&comma;x\&comma;x\right)\&comma;\mathrm{diff}\left(g\left(x\&comma;t\right)\&comma;t\right)+\mathrm{diff}\left(g\left(x\&comma;t\right)\&comma;x\&comma;x\right)\right]$

$\mathrm{sys}≔\left[\frac{{\partial }^3}{\partial x^3}f\left(x\&comma;t\right)+\frac{\partial }{\partial t}f\left(x\&comma;t\right)+\frac{{\partial }^2}{\partial x^2}f\left(x\&comma;t\right)\&comma;\frac{\partial }{\partial t}g\left(x\&comma;t\right)+\frac{{\partial }^2}{\partial x^2}g\left(x\&comma;t\right)\right]$

$\mathrm{sample\_rank}≔\left[\left[1\&comma;2\&comma;0\&comma;0\right]\&comma;\left[0\&comma;1\&comma;0\&comma;0\right]\right]\&colon;$

$\mathrm{ivars}≔\left[x\&comma;t\right]\&colon;$

$\mathrm{dvars}≔\left[f\&comma;g\right]\&colon;$

$\mathrm{rifsimp}\left(\mathrm{sys}\&comma;\mathrm{dvars}\&comma;\mathrm{indep}=\mathrm{ivars}\&comma;\mathrm{ranking}=\mathrm{sample\_rank}\right)$

$table\left(\left[\mathrm{Solved}=\left[\frac{{\partial }^3}{\partial x^3}f\left(x\&comma;t\right)=-\frac{\partial }{\partial t}f\left(x\&comma;t\right)-\frac{{\partial }^2}{\partial x^2}f\left(x\&comma;t\right)\&comma;\frac{\partial }{\partial t}g\left(x\&comma;t\right)=-\frac{{\partial }^2}{\partial x^2}g\left(x\&comma;t\right)\right]\right]\right)$