DEtools[rifsimp] Case Splitting and Related Options

Case Splitting Defined



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 : . 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 . rifsimp needs to isolate the highest power of the leading derivative, 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:


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.


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


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)


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 Liepoint transformation to the equation y''=0, by setting the minimum free parameters of the Liedetermining system to 8. The minimum dimension can be specified in a number of ways, including some shortcuts:

mindim=n

Minimum of n free 0dimensional parameters in


the dependent variables in vars.

mindim=[v,n]

Minimum of n free 0dimensional parameters in


the dependent variables v (v is either a


dependent variable name or set of more than one).

mindim=[v,n,d]

Minimum of n free ddimensional parameters in


the dependent variables v, where v is as above.

mindim=[c1,c2,...]

Here c1,c2,... are conditions of the [v,n,d] type.




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


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:

"smalleq"

Choose the pivot belonging to the smallest


equation (based on the Maple length function).


This is the default.

"smallpiv"

Similar to "smalleq", but the length of the


pivots are compared instead.

"lowrank"

Choose the pivot for the equation with


leading derivative of lowest rank. Ties


are broken by equation length.

"mindim"

Choose the pivot for the equation with


leading derivative that will reduce the size


of the initial data by the greatest amount.


This option can only be used in combination


with the option described above.

["smalleq",vars]

Same as "smalleq" above, but it only looks at


equations with leading derivatives in the


vars sequence.

["lowrank",vars]

Same as "lowrank" above, but it only looks at


equations with leading derivatives in the


vars sequence.




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)


This option gives a list of all variables and constants that cannot be present in pivots (that is, any pivots that arise in the computation that involve these variables will not be used as case splits in the process of reducing the system, and the corresponding equations with those pivots must be treated as nonlinear equations).


This is most useful for quasilinear systems for which the linearity of the resulting system is of greatest importance. In this case the variables for which linearity should be maintained should be in the list. For problems of this type, this may have the effect of reducing the size of the case tree (with some possible tradeoff in efficiency).


If this option is used with highly nonlinear systems, the decrease in the efficiency may be prohibitively severe, as many equations that could be treated by the linear code without , now must be treated with the nonlinear code (see rifsimp[nonlinear]).


3)


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)


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:

nolead

This is the default. Only split on a factor


if it does not contain the leading derivative


of the equation.

all

Split on any factors, even if they contain the


leading derivative.

none

Do not perform factored splitting.




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 nontermination for some nonlinear problems.

•

Note: These options do not require that casesplit be on, but are typically most useful in that situation.



Other Caserelated Options



Another option that is also related to casesplitting is the gensol option, which may return multiple cases for some problems:


This option indicates that the program should explore all cases that have the possibility of leading to the most general solution of the problem. Occasionally it is possible for rifsimp to compute only the case corresponding to the general solution of the ODE/PDE system. When this option is given, and this occurs, rifsimp will return the single case corresponding to the general solution. When it is not possible for rifsimp to detect where in the case tree the general solution is, then multiple cases are returned, one or more of which correspond to the general solution of the ODE/PDE system, and others correspond to singular solutions. For some particularly difficult problems, it is possible that the entire case tree is returned. Note: this option cannot be used with the casesplit,casecount, and mindim options.



Examples


>


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 8dimensional. 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:
>


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


 (2) 
Applying rifsimp:
>


>


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


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


 (4) 
The regular casesplitting strategy produces an undesirable result for this system, namely more cases than required to describe the system:
>


 (5) 
So we get 4 cases. Now set faclimit set to 2:
>


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


 (7) 
With default options, we obtain
>


 (8) 
With full factoring enabled, we obtain
>


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

