rifsimp[cases] - case splitting and related options

• What is a Case Split?

• If an input system is nonlinear with respect to any of its indeterminates (including constants), case splitting may occur.
• As an example, consider the ODE in u(t) : u'-a u'' = 0 . rifsimp can only isolate the leading indeterminate u'' when a <> 0 . Unfortunately, we do not know if this condition holds, so two possibilities result; either a <> 0 or a = 0 .
• Consider as a second example the equation u'^2 a-u'-u^2=0 . rifsimp needs to isolate the highest power of the leading derivative, u'^2 which introduces the same two possibilities as for the first example. This second type of pivot is called the initial of the equation.
• This prompts the following definitions:
• Pivot
• The coefficient of the highest power of the leading indeterminate in an unsolved equation. It is not known whether this coefficient is nonzero or whether it vanishes with respect to the resulting system.
• Case Split
• A case split in the rifsimp algorithm is the separate handling of the cases of nonzero or zero pivot during the solution of an equation in the system. By default (without casesplit on), only the nonzero case is explored.
• In the u[t]-a u[tt] = 0 example, the pivot is a , and the generic a <> 0 case is handled by default.

• Exploring All Cases

• For some systems, a simplified result for all cases is required. To obtain this, use the casesplit option. Specification of casesplit in the arguments to rifsimp tells it to examine all cases in the following way:
• Proceed to find the generic solution by assuming that all pivots are nonzero. After each solution is found, back up to the most recent nonzero assumption, change to a zero assumption, and proceed to find the solution under this new restriction. The process is complete when no nonzero assumptions are left to back up to.
• The result is a tree of disjoint cases, with the simplified forms presented in a table. Each case is stored as a numbered entry in the output table, having all the standard entries, along with an entry called Case that can be used to reconstruct a tree of case splittings using the caseplot command. This Case entry is a list of assumptions made to obtain the answer for that case. Each assumption is a two or three element list, the first element is the assumption made, the second is the derivative being isolated that required the assumption, and if the third entry is present, it indicates that is was later found that the assumption is always true, so the assumption does not represent a true case split of the problem, but rather a false split .
• There are three options below that mildly alter this behavior, and these are the faclimit , factoring , and grobonly options. The first two allow pivots to be introduced to the system that do not necessarily occur as the coefficient of a specific leading derivative. When one of these pivots occur, then the second element of the assumption is the name of the option (rather than the leading derivative). The third option, grobonly , has the effect of introducing fewer pivots (as equations that are nonlinear in their leading derivative, such as the equation in the second example at the top of this page, do not directly introduce case splittings), but has the disadvantage that a less efficient nonlinear equation handling method (pure Groebner basis) must be employed. For more detail on the output see rifsimp[output] , and for more detail on nonlinear equation handling see rifsimp[nonlinear] .

• Case Restrictions

• Two options can be used to limit or restrict which cases are explored:
• 1) casesplit=[`<>`,`=`,`<>`]
• This option turns on casesplit and gives the start of the tree to be examined. It is used primarily for repeating a calculation, or for avoiding particularly difficult cases. Note: A rerun of the system with additional equations is likely to change the order of the pivots, so this option is only reliable for the same input as the initial calculation. If a calculation for a specific case is to be repeated with additional equations, it would be better to append the assumptions made in the Case list to the original system, and run rifsimp with the combined system.
• 2) mindim=[...]
• This option is used to limit the cases being examined based on the solution space dimension of the linear part of the current system. Though the dimension of the solution space is not known until the computation is complete, an upper bound is available by looking at the current Solved equations. Note: In the presence of nonlinear constraints, the computed dimension represents an upper bound on the dimension of the case. This could be used, for example, to find all forms of a second order ODE that are related by a Lie-point transformation to the equation y''=0 , by setting the minimum free parameters of the Lie-determining system to 8. The minimum dimension can be specified in a number of ways, including some shortcuts:

• When this option is used, a dimension entry is also provided for each case in the output system. See the information in rifsimp[output] for more detail.
• Note: When using multiple specifications, each must be a full specification defining the number, the dependent variables, and the dimension of the required data.
• If any of the input conditions fail, computation is halted on the current case, it is tagged with the status "free count fell below mindim" , and the computation proceeds to the next case.

• Pivoting and Pivot Selection

• The rifsimp algorithm proceeds by putting as many PDEs into solved form as possible without introducing new pivots. When it has reached a point where none of the remaining unsolved equations can be solved without the introduction of a pivot, it must then decide which equation to solve. By default, rifsimp chooses the leading linear unsolved equation that is smallest in size, but this behavior can be modified by the pivselect option described below. The new pivot for the chosen equation then results in a case split if casesplit is set, otherwise exploration of only the nonzero (generic) case if casesplit is not set. If none of the equations are leading linear, then no standard pivot can be found, so rifsimp then attempts to factor the leading nonlinear equations searching for factors that do not depend on the leading derivative. If these are found, then the smallest factor (based on the Maple length function) is chosen, and a "factor" split is performed. This behavior can be modified through use of the factoring option described below. If nonlinear equations remain, then the coefficient of the highest degree of the leading derivative in the equation (the initial of the equation) is split on if initial has been specified (see below) or if grobonly has not been specified (see rifsimp[nonlinear] ).
• The following options relate to pivoting and to the control of pivoting in the course of the algorithm:
• 1) pivselect=choice
• During the course of a computation, rifsimp proceeds by performing as much elimination as possible before introducing a pivot. Once no further elimination can be done, a pivot must be introduced, and there is generally more than one possible choice. There are currently six possible choices for pivot selection:

• The choice of a pivoting strategy can significantly affect the efficiency of a computation for better or worse. In addition to efficiency considerations, the selection of different pivoting strategies can also simplify the resulting case structure, though the choice that gives the best case structure is highly problem dependent.
• The "smalleq" and "smallpiv" options are generally focussed on efficiency. "smalleq" makes the computation more efficient by selecting smaller equations for splitting, while "smallpiv" makes the computation more efficient by introducing smaller pivots.
• The "lowrank" and "mindim" options are focussed on keeping the number of cases to a minimum.
• 2) nopiv=[var1, ...]
• This option gives a list of all variables and constants that cannot be present in pivots. This is most useful for quasi-linear systems for which the linearity of the resulting system is of greatest importance. This may also have the effect of reducing the size of the case tree in these systems. The unsolved equations are then treated as fully nonlinear (see rifsimp[nonlinear] ).
• 3) faclimit=<n>
• Typically the pivot chosen is the coefficient of the leading indeterminate in the equation. In the event that the leading indeterminate is itself a factor of the equation, and this same leading indeterminate factor occurs in <n> or more equations, then it is chosen as the pivot rather than as the coefficient. This is most useful for Lie determining systems having many inconsistent cases, since in these systems, many equations of this form typically occur during the calculation. The answer may be obtained without this option, but it can significantly reduce the number of cases returned.
• 4) factoring=desc
• As briefly described above, by default equations that factor are split if one of the factors does not depend upon the leading derivative of that equation. This option can be used to modify that behavior based on the value of desc used in the factoring option:

• In any event, the factoring pivots are always the last to be considered (i.e. faclimit and regular pivots are used if available). Note: factoring="all" should be used with caution as it has the potential to significantly increase the number of cases returned. Note: factoring="none" can result in non-termination for some nonlinear problems.
• 5) pivsub
• When introducing a new pivot, attempt to reword that pivot as a new dependent variable when it is advantageous to do so. For example, if the new pivot is a(x)+b(x)-c(x,y) , then rifsimp creates a new dependent variable, say F1(x,y) , and adds an equation to the system indicating that F1(x,y) = a(x)+b(x)^2-c(x,y) . The ranking would be arranged such that the new equation would be solved in terms of an existing indeterminate in the pivot, and the overall effect would be to make the new pivot a single-term expression.
• The primary advantage of this strategy is that, after introducing a pivot, the solution procedure usually results in the occurrence of that pivot and its derivatives, sometimes to a high polynomial degree. Leaving the pivot in its regular form can result in extensive expression swell, whereas the reworded pivot remains quite small and manageable.
• The new dependent variables are chosen as F.(i),F.(i+1) , and so on, where i is larger than the largest occurrence of an F.(j) in the present system, and is not globally assigned.
• 6) initial
• This option only applies to systems which have nonlinear Constraint equations in their output. The initial is the coefficient of the highest power of the leading derivative in a polynomially nonlinear equation (the leading nonlinear derivative ). For example, in the equation u[x]^2*u+u[x]^2+u[x]+u-1 , the initial is the coefficient of u[x]^2 , which is u+1 . By default, rifsimp splits on the initial, unless grobonly is specified (in which case it does not need to), introducing additional cases in the output. With these additional cases, rifsimp isolates the leading nonlinear derivatives in the Constraint equations. When grobonly is not specified, only the form of the Constraint output is different.

• Note: These options do not require that casesplit be on, but are typically most useful in that situation.
• Other Case-related Options

• Another option that is also related to case-splitting is the gensol option, which may return multiple cases for some problems:

• gensol

> with(Rif):

Suppose we have the ODE shown below. We want to determine conditions on g(y(x)) and f(x) that allow the equation to be mapped to y'' = 0 by an invertible change of variables of the form Y=Y(x,y), X=X(x,y) . It is known that the equation can be mapped to y''=0 if the Lie group of the equation is 8-dimensional. This is the perfect opportunity to use the mindim option in combination with cases, to tell rifsimp that we are only interested in cases with 8 dimensions or more:

> ODE1:=diff(y(x),x,x)+g(y(x))*diff(y(x),x)+f(x)*y(x);

We can use the DEtools[odepde] command to generate the determining system for this ODE, and we obtain the following:

> sys1:=[coeffs(expand(DEtools[odepde](ODE1,[xi(x,y),eta(x,y)], y(x))),_y1)];

Applying rifsimp :

> ans1:=rifsimp(sys1,[xi,eta],casesplit,mindim=8):

> caseplot(ans1);

Issuing the caseplot command above would show that there is one case for which this occurs. This case is given by:

> copy(ans1[3]);

So the original ODE is equivalent to y''=0 when g'(y) is zero, regardless of the form of f(x) .

As a demonstration of the faclimit option, consider the following system:

> sys2:=[eta(x,y)*(3*f(x)+2*g(x)-h(x)),
eta(x,y)*(f(x)-2*g(x)-5*h(x)+2),
eta(x,y)*(-f(x)-3*g(x)+h(x)-3),
eta(x,y)*(3*f(x)-3*g(x)-5*h(x)-1)];

The regular case-splitting strategy produces an undesirable result for this system, namely more cases than required to describe the system:

> ans2_1:=rifsimp(sys2,[eta],casesplit);

So we get 4 cases. Now set faclimit set to 2:

> ans2_2:=rifsimp(sys2,[eta],casesplit,faclimit=2);

So although both ans2_1 and ans2_2 equally valid, it is clear that ans2_2 would be preferred.

As an example of the factoring option, consider the following purely algebraic system:

> sys := [x^3-7*x+6];

With default options, we obtain

> rifsimp(sys,casesplit);

With full factoring enabled, we obtain

> rifsimp(sys,casesplit,factoring=all);

So we see that the system has been split into three disjoint cases. Also note that the Case entries describe the path the computation took, and there are no Pivots entries. This is because the pivots resulting from the case splits are identically satisfied for each case.

caseplot , rifsimp , rifsimp[nonlinear] , rifsimp[output]