Understanding Rankings and Related Concepts in DEtools[rifsimp]

Ranking Defined



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


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.


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.


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].


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:


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.


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.



Properties of a Ranking



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 nonvanishing 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).


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 nonpositive 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.


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.


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 rifsimp default ranking is an orderly, totaldegree 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).

rankgreater(v1,v2)

# Criterion 1: Solving variables

If v1 is a solving variable, and v2 is not, then

return(true)

If v2 is a solving variable, and v1 is not, then

return(false)

# Criterion 2: Total Degree

If dord(v1) is larger than dord(v2), then

return(true)

If dord(v2) is larger than dord(v1), then

return(false)

# Criterion 3: Independent Variable Differential Order

Loop i := each independent variable in sorted order

If diff. order of v1 in i is larger than order of v2 in i, then

return(true)

If diff. order of v2 in i is larger than order of v1 in i, then

return(false)

end loop

# Criterion 4: Dependent Variable

If dependent var for v1 occurs before v2, then

return(true)

If dependent var for v2 occurs before v1, then

return(false)

end



•

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):

Dependent Variables


Independent Variables


Constants





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:

Criterion 1


Criterion 2


Criterion 3


Criterion 4





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:


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.


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:


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.


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 is less than 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:

ranking = [

,

# This corresponds to criterion 1


,

# This corresponds to criterion 2


,

# These three lines are criterion 3


,



,



]

# This corresponds to criterion 4




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.


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.



Examples


For examples we will take as input single equations or a system of decoupled equations and observe their solved form in the output. They will be solved for their leading indeterminate.
>


>


 (1) 
By default, the above will be solved for the g derivative, as f and g have equal weight (criterion 1). The equation is differential order 2, so this narrows it down to the three second order derivatives (criterion 2), but x derivatives are of greater weight than y derivatives (criterion 3), so the equation will be solved for g[xx]:
>


 (2) 
So how can we solve for f instead? The obvious way is to give f more weight than g by declaring it as the solving variable by using vars (alter criterion 1):
>


 (3) 
What if we wanted to solve for the y derivative of f? Well, we could then also weight y derivatives greater using indep:
>


 (4) 
Good, but what if we want to solve for the t derivative of f. This is an unusual example because we are solving for a lower order derivative in terms of higher order derivatives. We could specify a new ranking that weights t derivatives higher than everything else:
>


>


>


With the above ranking, f is always greater than g, and t derivatives are always greater than x or y derivatives of any order. We have to declare the order of occurrence in the command line arguments so that we can match the independent and dependent variables to the sample_rank table. (These are typed in above for visualization.)
>


 (5) 
Note: We did not specify a full ranking, but instead specified as much as we required, then let the default ranking take over.
Note that a ranking like the one above is natural for certain classes of equations. As an example, consider the heat equation u[t] = u[xx]+u[yy]+u[zz] where the form of the solved equation is only physically meaningful when solving for the time derivatives in terms of the space derivatives, even when the space derivatives are of higher differential order.
As a final example, we construct a strange ranking that weights t derivatives twice as heavily as x derivatives. This is done for the following:
>


 (6) 
>


>


>


>


 (7) 

