rifsimp[ranking] - understanding rankings and related concepts

• What is a ranking?

• 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 rank more than just the indeterminates appearing in the initial system, because higher derivatives may appear in the course 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.

• 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 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

{a, b} < {f, g, h, f[x], f[y], f[z], g[x], g[y], h[x], h[z],

 f[xx], f[xy], `...`}}

• Criterion 2: Rank by differential order

{f, g, h} < {f[x], f[y], f[z], g[x], g[y], h[x], h[z]}

 < {f[xx], f[xy], `...`} < ...}

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

{f, g, h} < {f[x], g[x], h[x]} < {f[y], g[y]} < {f[z], h[z]}

 < {f[xx], g[xx], h[xx]} < {f[xy], g[xy]} < ...}

• Criterion 4: Rank by dependent variable or constant name

{b} < {a} < {h, h[x], h[z], h[xx], h[xz], `...`}

 < {g, g[x], g[y], g[xx], g[xy], `...`}

 < {f, f[x], f[y], f[z], f[xx], `...`}}

• 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

{a, b} < {g, g[x], g[y], g[xx], `...`}

 < {f, b, h, f[x], f[y], f[z], h[x], h[z], f[xx], f[xy], `...`}

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

{b} < {a} < {g, g[x], g[y], g[xx], g[xy], `...`}

< {h, h[x], h[z], h[xx], h[xz], `...`} < {c}

< {f, f[x], f[y], f[z], f[xx], `...`}

• 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

{a, b} < {h, h[x], h[z], h[xx], `...`} <

 {g, c, g[x], g[y], g[xx], `...`} < {f, f[x], f[y], f[z], f[xx], f[xy], `...`}

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

{b} < {a} < {h, h[x], h[z], h[xx], h[xz], `...`} < {c}

< {g, g[x], g[y], g[xx], g[xy], `...`} < {f, f[x], f[y], f[z], f[xx], `...`}

• 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 weight(f[xyz]) = 1 is less than weight(g[xxz]) = 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

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.

> with(Rif):
sys:=[diff(g(x,y,t),x,x)+diff(f(x,y,t),x,y)+
diff(f(x,y,t),y,y)+diff(f(x,y,t),t)=0];

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

> rifsimp(sys);

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

> rifsimp(sys,[f]);

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

> rifsimp(sys,[f],indep=[y,x]);

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:

> sample_rank:=[[0,0,0,1,0], # Solve for f over g
[0,0,1,0,0]]:# t derivs are greatest
ivars:= [x,y,t]:
dvars:= [f,g]:

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

> rifsimp(sys,dvars,indep=ivars,ranking=sample_rank);

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:

> sys:=[diff(f(x,t),x,x,x)+diff(f(x,t),t)+diff(f(x,t),x,x),
diff(g(x,t),t)+diff(g(x,t),x,x)];

> sample_rank:=[[1,2,0,0], # t derivs have 2* weight of x
[0,1,0,0]]:# t derivs are greatest
ivars:= [x,t]:
dvars:= [f,g]:
rifsimp(sys,dvars,indep=ivars,ranking=sample_rank);

checkrank , rifsimp , rifsimp[nonlinear] , rifsimp[options]