Leading nonlinear equations

This help page explains how rifsimp handles equations which are polynomially nonlinear in their leading indeterminate (called leading nonlinear equations), or equations that are leading linear, but have a coefficient that depends on pivot restricted variables (see nopiv in rifsimp[cases]).

As an example, consider the equation $u_{\mathrm{tt}}u-{u_t}^2=0$. This equation is linear in its leading indeterminate, so as long as $u$ can be present in a pivot it will be handled through case splitting rather than nonlinear equation handling (see rifsimp[cases]). Conversely, the equation $u_{\mathrm{tt}}^2-u_t=0$ is leading nonlinear, and is always handled through the nonlinear methods described here.

During the course of the computation, nonlinear equations are always differentially simplified with respect to the linear equations of the system, but they are also algebraically simplified with respect to each other. This simplification process resembles an algebraic Groebner basis, but takes the inequations (pivots) of the system into account, and does not compute algebraic S-polynomials. Use of this set of equations allows recognition of, and elimination of redundant equations, and produces a more compact representation (due to the use of pivots and lack of S-polynomials).

In order to perform the algebraic simplification of these nonlinear equations, a monomial ordering must be imposed for all possible nonlinear terms. This is simply chosen to be pure lexicographical ordering with respect to the ordering imposed on the linear derivatives.

For example, the equation ${u_{\mathrm{xx}}}^2{u}_x+{u_{\mathrm{xx}}}^{2}u-{u_x}^2-u^2$ for a system in which $u_x+u\ne 0$ holds is algebraically solved for $u_{\mathrm{xx}}^2$ giving the nonlinear relation: $u_{\mathrm{xx}}^2=\frac{u^2+u_x^2}{u_x+u}$.

Note: during the course of the algorithm, when nonlinear equations are encountered, case splitting is performed on the coefficient of the highest degree of the leading derivative each equation. This coefficient is called the initial of the equation. So for the example above, the initial is $u_x+u$. If there was no condition on $u_x+u$, then rifsimp would split into the cases $u_x+u\ne 0$ and $u_x+u=0$. This can increase the number of cases in the output, but is required for the proper functioning of the more compact nonlinear equation handling algorithm, so if this splitting is not desired, pure Groebner basis methods can be used instead with the grobonly option.

If leading linear equations with usable pivots are found in the algebraically simplified set, rifsimp removes them from the set, and treats them using leading linear methods (i.e. isolation of the leading derivative and pivoting, differential substitution, and linear integrability conditions).

Differential consequences are enforced by the spawning (differentiation with respect to each independent variable) of each equation, which naturally results in leading linear equations.

Before algorithm completion, rifsimp forms an algebraic Groebner basis over the leading nonlinear equations, spawning any new relations that appear as a result of S-polynomials. This step is necessary to ensure that all differential consequences of the leading nonlinear equations are accounted for, so that the set of nonlinear constraint equations returned by the algorithm can be viewed as algebraic (not differential) constraints.

Of course, Groebner basis computations require a ranking of monomials in a system. By default the ranking is chosen as total-degree order with ties broken by inverse lexicographical order (otherwise known as grevlex). The allowed rankings for rifsimp are quite flexible, but require some knowledge of rankings (please see rifsimp[ranking], and look at the Groebner Rankings description below).

Control options

There are four options used to control how rifsimp handles leading nonlinear equations. The spoly and spawn options limit what is done in the algorithm, and thus they generally return an incomplete answer. Unfortunately, these options are needed in some cases as highly nonlinear ODE/PDE systems may have to perform a Groebner basis of a large number of equations in a large number of indeterminates. Though the process is finite, it can be extremely time consuming, and may not return the result for days (weeks, months, etc.). These options allow rifsimp to return a result that can be further processed using other tools, such as hand integration or resultants, to obtain the final result.

1) grobonly

This option tells rifsimp to only use Groebner basis simplification of the nonlinear equations in the course of the algorithm instead of using the algebraic simplification described above. This has the potential to decrease the number of cases in the output, but caution should be used with this option, as rifsimp works with only part of the system at any one time, so use of full a Groebner basis on only a partial system can often lead to inefficiency.

2) checkempty

This option tells rifsimp to attempt to determine, on the completion of the calculation (or the completion of each calculation when dealing with cases) whether the resulting system contains any solutions. These empty systems do not occur for linear problems, but when algebraic constraints and pivots are both present for a system, then there is a possibility that the resulting output has no solution. For a simple example, see the last problem in the examples section below. Caution should be used for this option also, as the checking process can be quite expensive.

3) spoly=[true,false]

This option indicates whether to generate S-polynomials during the Groebner basis algorithm (default is true). Setting spoly=false has some risk associated with it, as if nonlinear equations are present in the output, then it is possible that not all consequences of these equations have been obtained (hence they are placed in the $\mathrm{DiffConstraint}$ list rather than the Constraint list). If an orderly ranking is used ( see rifsimp[ranking]), and spawn is set to true (see below), then only algebraic simplifications remain, but these may still result in an inconsistent system when considered with the Pivot equations.

Note: By algebraic simplifications we mean that there are no further integrability conditions that can result once the system is algebraically simplified. Differential reduction of leading linear equations can still occur.

4) spawn=[true,false]

Indicates whether to perform a differential spawn of nonlinear equations (default is true). A differential spawn simply means taking the derivative of an equation with respect to all independent variables. Setting this to false allows rifsimp to ignore differential consequences of the polynomially nonlinear equations. This is only useful if rifsimp is being used as a single step of a different calculation, since an incomplete answer may be obtained. When spawn=false, all nonlinear equations are placed in the $\mathrm{DiffConstraint}$ list rather than the Constraint list to indicate that the answer may be incomplete.

Groebner rankings 1

A Groebner ranking is a ranking defined on the set of all monomials in the indeterminates of a system of equations. For example, if the indeterminates were x, y, and z, a ranking would be able to order the monomials $x{y}^{2}z,x^3{y}^2,x^{2}y{z}^2,x^{2}y{z}^4$, and determine a leader. The determination of this leader is vital to the completion of a Groebner basis, and different rankings can give drastically different bases for the same input system.

Algebraic monomial rankings

There are a number of standard Groebner basis rankings available for algebraic systems of equations. The rankings described below can be used in rifsimp. Each ranking is described as a comparison of two monomials:

1) Total-degree ranking

This only defines a partial ranking; that is, there can be ties for different terms. It looks at the degree of each monomial in all indeterminates (the total degree), and if the total degrees of the monomials are different, the one of larger degree is ranked higher.

2) Lexicographic ranking

Given an ordered list of indeterminates, lexicographic ranking compares the degrees of the two monomials in each indeterminate in turn. If the degree of one monomial is greater than the other in that indeterminate, then it is ranked higher.

3) Inverse Lexicographic ranking

This ranking looks at the ordered list of indeterminates in reverse order, and compares the degrees of the two monomials in each indeterminate in turn. If the degree of one monomial is lower than the other in that indeterminate, then it is ranked higher.

It is important that a ranking is deterministic. That is, given two different monomials it is always possible to rank one higher than the other. Since a total-degree ranking is not deterministic, it must be followed by either a lexicographic or an inverse lexicographic ranking.

As an example we look at all monomials in x, y, and z up to total degree 3 and rank them using the rankings described above.

Total Degree followed by Lexicographic on [x,y,z]

Total Degree followed by Lexicographic on [z,y,x]

Total Degree followed by Inverse Lexicographic on [x,y,z]

Pure Lexicographic on [x,y,z]

Simple algebraic rankings in rifsimp

The rankings for Groebner basis computations in rifsimp are specified by the $\mathrm{grob\_rank}=\[\mathrm{criterion\; list}\]$ option. If all that is needed is an algebraic ranking as described above (for the indeterminates in the order described by the linear ranking) the criterion list can simply be given as below:

$\mathrm{grob\_rank}=\left[\left[1,\mathrm{deg},\mathrm{none}\right],\left[1,\mathrm{ilex}\right]\right]$ 

This says to use algebraic total-degree ranking followed by inverse lexicographic ranking (this is the default).

$\mathrm{grob\_rank}=\left[\left[1,\mathrm{deg},\mathrm{none}\right],\left[1,\mathrm{lex}\right]\right]$ 

Use algebraic total-degree ranking followed by lexicographic ranking.

$\mathrm{grob\_rank}=\left[\left[1\,\mathrm{lex}\right]\right]$

Use pure lexicographic ranking.

The criterion lists may seem a bit verbose for what they need to accomplish, but far more detailed rankings are available (see Groebner Rankings 2 below).

Though the pure lexicographic ranking produces a more desirable result, total-degree / inverse lexicographic ranking was chosen as the default as it was in general (by experiment on a number of ODE/PDE systems) the least expensive in time and memory.

Groebner Rankings 2: a different point of view

The main thing to note is that all the types of monomial rankings previously discussed can be viewed as looking at the degree of one or more indeterminates between the two monomials being compared.

For example, total degree followed by lexicographic ranking (for the x,y,z example) looks at the degree of the monomials in $x,y,z$, then in $x$, then in $y$, then finally in $z$. Total degree followed by inverse lexicographic ranking looks at the degree of the monomials in $x,y,z$, then $x,y$, then $x,z$, then $y,z$ .

So now that we are dealing with differential systems, it may be desirable to rank indeterminates based upon other criteria such as their differential degree, dependent variable, differentiations, etc. This can be accomplished in rifsimp.

Classification of linear ranking criteria

As a first step, all linear differential ranking criteria are classified.

For more detail about criteria, please see rifsimp[ranking]. In that help page, an example of the $\mathrm{diffdeg}$ classification is given by criterion 2, $\mathrm{diffvar}$ by criterion 3, and $\mathrm{depvar}$ by criterion 1 and 4.

These classifications, which actually refer to a specific part of the linear ranking, allow the definition of equivalence classes for the derivatives. The monomial ranking then takes the degree of each monomial in derivatives of the same equivalence class.

Definition of the criteria for $\mathrm{grob\_rank}$

With the above information we can now construct a differential monomial ranking as an example. Suppose we define our first criterion as $\left[1\,\mathrm{deg}\,\mathrm{diffdeg}\right]$. This describes equivalence classes based upon the differential degree of the derivatives. Consider a system containing the dependent variable f(x,y) and all derivatives up to second order, and using the default linear ranking for differential degree (all differentiations have equal weight). This defines the following equivalence classes:

Now when comparing two monomials, the degree of the monomials in each equivalence class is considered in turn, and if they are different, the one with greater degree is ranked higher.

Here are a few examples:

This does not fully determine a ranking, since if there were (for example) two terms that were fourth degree in second order derivatives, this criterion would regard them as equal.

To fully specify the monomial ranking, we could add another criterion of the lex or ilex type. If we added a lex criterion, namely [1,lex], then we would be looking at the degree of the monomials in the indeterminates in their linearly ranked order. Again using the default for the linear ranking, and considering the f(x,y) system up to second order we would get the following:

This is presented in the same manner as the equivalence classes for the degree-type monomial ranking.

In summary, one should consider all the criteria as a list of equivalence classes, for which the degree of the monomial in the indeterminates of the equivalence class determines the relative monomial ranking. For $\mathrm{grob\_rank}=\left[\left[1\,\mathrm{deg}\,\mathrm{diffdeg}\right]\,\left[1\,\mathrm{lex}\right]\right]$, and the above examples, the list of equivalence classes is given as follows:

One final detail -- a bit more flexibility

You may have noticed that there is always a 1 present as the first element of each criterion, but it is not discussed. This allows a bit more flexibility in the specification of the ranking, as it allows for nesting of the criteria.

Consider again the earlier example where the criterion was specified as $\left[\left[1\,\mathrm{deg}\,\mathrm{diffdeg}\right]\,\left[1\,\mathrm{lex}\right]\right]$. Based on the above description, if the higher derivatives are of equal degree in each order of derivative, then the degree of the lower order derivatives may be used to break the tie. This may not be what is desired. Suppose one wants to examine the degree in the higher-order derivatives, and if they are equal, to compare the higher-order derivatives lexicographically.  This can be accomplished through nesting. Any increase in the first element (integer) of a criterion from the prior criterion indicates that the new criterion should be nested inside the prior.

Consider our earlier example system with the new nested ranking $\left[\left[1\,\mathrm{deg}\,\mathrm{diffdeg}\right]\,\left[2\,\mathrm{lex}\right]\right]$. This would have the effect of changing the order of the combined equivalence classes to the following:

This tells rifsimp to consider the degree of the monomial in second order derivatives, then in each second order derivative in turn, then do the same for first order derivatives, etc.

Here are a few examples:

The comparisons with * will give different results for the non-nested ranking.

$\mathrm{with}\left(\mathrm{DEtools}\right)\:$

$\mathrm{PDEtools}\left[\mathrm{declare}\right]\left(x\left(t\right)\,y\left(t\right)\,z\left(t\right)\,\mathrm{prime}=t\right)$

$x\left(t\right)\mathrm{will\; now\; be\; displayed\; as}x$

$y\left(t\right)\mathrm{will\; now\; be\; displayed\; as}y$

$z\left(t\right)\mathrm{will\; now\; be\; displayed\; as}z$

$\mathrm{derivatives\; with\; respect\; to}t\mathrm{of\; functions\; of\; one\; variable\; will\; now\; be\; displayed\; with\; \text{'}}$

$\mathrm{sys1}≔\left[\mathrm{diff}\left(y\left(t\right)\,t\right)-{x\left(t\right)}^2-x\left(t\right)\,{y\left(t\right)}^4-2{y\left(t\right)}^2\mathrm{diff}\left(z\left(t\right)\,t\right)+{\mathrm{diff}\left(z\left(t\right)\,t\right)}^2-{y\left(t\right)}^2+2\mathrm{diff}\left(z\left(t\right)\,t\right)\,{\mathrm{diff}\left(x\left(t\right)\,t\right)}^2+2y\left(t\right)\mathrm{diff}\left(x\left(t\right)\,t\right)+{y\left(t\right)}^4\right]$

$\mathrm{sys1}≔\left[\mathrm{y\text{'}}-x^2-x\,y^4-2y^2\mathrm{z\text{'}}+{\mathrm{z\text{'}}}^2-y^2+2\mathrm{z\text{'}}\,{\mathrm{x\text{'}}}^2+2y\mathrm{x\text{'}}+y^4\right]$

$\mathrm{ans1}≔\mathrm{rifsimp}\left(\mathrm{sys1}\right)$

$\mathrm{ans1}≔table\left(\left[\mathrm{Solved}=\left[\mathrm{x\text{'}\text{'}}=-\frac{x\left(x+1\right)\mathrm{x\text{'}}+x\left(2x+2\right)y^3}{\mathrm{x\text{'}}+y}\,\mathrm{z\text{'}\text{'}}=-\frac{-x\left(2x+2\right)y^3-x\left(-2x-2\right)y\mathrm{z\text{'}}-x\left(-x-1\right)y}{y^2-\mathrm{z\text{'}}-1}\,\mathrm{y\text{'}}=x\left(x+1\right)\right]\,\mathrm{Constraint}=\left[8y^3\mathrm{x\text{'}}-4{\mathrm{z\text{'}}}^{2}y\mathrm{x\text{'}}-4{\mathrm{x\text{'}}}^{3}y-{\mathrm{z\text{'}}}^4-2{\mathrm{z\text{'}}}^2{\mathrm{x\text{'}}}^2-{\mathrm{x\text{'}}}^4-12\mathrm{z\text{'}}y\mathrm{x\text{'}}-6{\mathrm{z\text{'}}}^3-6\mathrm{z\text{'}}{\mathrm{x\text{'}}}^2+3y^2-4y\mathrm{x\text{'}}-11{\mathrm{z\text{'}}}^2-2{\mathrm{x\text{'}}}^2-6\mathrm{z\text{'}}=0\,8y^3\mathrm{x\text{'}}+4y^2{\mathrm{x\text{'}}}^2-12\mathrm{z\text{'}}y\mathrm{x\text{'}}-2{\mathrm{z\text{'}}}^3-6\mathrm{z\text{'}}{\mathrm{x\text{'}}}^2+3y^2-2y\mathrm{x\text{'}}-7{\mathrm{z\text{'}}}^2-{\mathrm{x\text{'}}}^2-6\mathrm{z\text{'}}=0\,{\mathrm{x\text{'}}}^2+2y\mathrm{x\text{'}}+y^4=0\,2y^2\mathrm{z\text{'}}+{\mathrm{x\text{'}}}^2-{\mathrm{z\text{'}}}^2+2y\mathrm{x\text{'}}+y^2-2\mathrm{z\text{'}}=0\right]\,\mathrm{Case}=\left[\left[\mathrm{x\text{'}}+y\ne 0\,\mathrm{x\text{'}\text{'}}\right]\,\left[-y^2+\mathrm{z\text{'}}+1\ne 0\,\mathrm{z\text{'}\text{'}}\right]\right]\,\mathrm{Pivots}=\left[\mathrm{x\text{'}}+y\ne 0\,-y^2+\mathrm{z\text{'}}+1\ne 0\right]\right]\right)$

$\mathrm{nops}\left(\mathrm{ans1}\left[\mathrm{Constraint}\right]\right)$

$4$

$\mathrm{ans2}≔\mathrm{rifsimp}\left(\mathrm{sys1}\,\left[\left[x\right]\,\left[z\right]\,\left[y\right]\right]\,\mathrm{grob\_rank}=\left[\left[1\,\mathrm{lex}\right]\right]\right)$

$\mathrm{ans2}≔table\left(\left[\mathrm{Solved}=\left[x=-\frac{4y^4\mathrm{y\text{'}}+y^4+{\mathrm{y\text{'}\text{'}}}^2+2\mathrm{y\text{'}\text{'}}y}{4\mathrm{y\text{'}\text{'}}y}\,\mathrm{z\text{'}\text{'}}=-\frac{-2y^3\mathrm{y\text{'}}+2y\mathrm{z\text{'}}\mathrm{y\text{'}}+y\mathrm{y\text{'}}}{y^2-\mathrm{z\text{'}}-1}\,\mathrm{y\text{'}\text{'}\text{'}}=-\frac{8y^9\mathrm{y\text{'}}+2y^9+6{\mathrm{y\text{'}\text{'}}}^2{y}^5+12\mathrm{y\text{'}\text{'}}{y}^4{\mathrm{y\text{'}}}^2+3\mathrm{y\text{'}\text{'}}{y}^4\mathrm{y\text{'}}-8{\mathrm{y\text{'}\text{'}}}^2{y}^3-{\mathrm{y\text{'}\text{'}}}^3\mathrm{y\text{'}}}{-4y^5\mathrm{y\text{'}}-y^5+{\mathrm{y\text{'}\text{'}}}^{2}y}\right]\,\mathrm{Constraint}=\left[y^4-2y^2\mathrm{z\text{'}}+{\mathrm{z\text{'}}}^2-y^2+2\mathrm{z\text{'}}=0\,16y^8{\mathrm{y\text{'}}}^2+8y^8\mathrm{y\text{'}}+y^8+8{\mathrm{y\text{'}\text{'}}}^2{y}^4\mathrm{y\text{'}}+2{\mathrm{y\text{'}\text{'}}}^2{y}^4-16\mathrm{y\text{'}}{\mathrm{y\text{'}\text{'}}}^2{y}^2+{\mathrm{y\text{'}\text{'}}}^4-4{\mathrm{y\text{'}\text{'}}}^2{y}^2=0\right]\,\mathrm{Case}=\left[\left[-2x-1\ne 0\,\mathrm{x\text{'}}\right]\,\left[\mathrm{y\text{'}\text{'}}y\ne 0\,x\right]\,\left[-y^2+\mathrm{z\text{'}}+1\ne 0\,\mathrm{z\text{'}\text{'}}\right]\,\left[\left(4\mathrm{y\text{'}}+1\right)\left(-4y^4\mathrm{y\text{'}}-y^4+{\mathrm{y\text{'}\text{'}}}^2\right)\ne 0\,\mathrm{y\text{'}\text{'}\text{'}}\right]\right]\,\mathrm{Pivots}=\left[-4y^4\mathrm{y\text{'}}-y^4-{\mathrm{y\text{'}\text{'}}}^2\ne 0\,\mathrm{y\text{'}\text{'}}\ne 0\,-y^2+\mathrm{z\text{'}}+1\ne 0\,-4y^4\mathrm{y\text{'}}-y^4+{\mathrm{y\text{'}\text{'}}}^2\ne 0\right]\right]\right)$

$\mathrm{sys3}≔\mathrm{Groebner}\left[\mathrm{Basis}\right]\left(\left[{\left(b+a^2\right)}^2\,a^3-c\right]\,\mathrm{tdeg}\left(a\,b\,c\right)\right)$

$\mathrm{sys3}≔\left[-3abc+b^3-2c^2\,a^{2}c+a{b}^2+2bc\,2a^{2}b+ac+b^2\,a^3-c\right]$

$\mathrm{ans3\_1}≔\mathrm{rifsimp}\left(\left[\mathrm{op}\left(\mathrm{sys3}\right)\,a^2+b\ne 0\right]\,\mathrm{nopiv}=\left[b\right]\,\mathrm{casesplit}\,\mathrm{grobonly}\right)$

$\mathrm{ans3\_1}≔table\left(\left[\mathrm{Constraint}=\left[a^3-c=0\,2a^{2}b+ac+b^2=0\,a^{2}c+a{b}^2+2bc=0\,3abc-b^3+2c^2=0\right]\,\mathrm{Pivots}=\left[a^2+b\ne 0\right]\right]\right)$

$\mathrm{ans3\_2}≔\mathrm{rifsimp}\left(\left[\mathrm{op}\left(\mathrm{sys3}\right)\,a^2+b\ne 0\right]\,\mathrm{nopiv}=\left[b\right]\,\mathrm{casesplit}\,\mathrm{grobonly}\,\mathrm{checkempty}\right)$

$\mathrm{ans3\_2}≔table\left(\left[\mathrm{status}=''system\; is\; inconsistent''\right]\right)$