Description
-
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[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[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[xx]^2 u[x]+u[xx]^2 u-u[x]^2-u^2
for a system in which
u[x]+u<>0
holds is algebraically solved for
u[xx]^2
giving the nonlinear relation:
-
u[xx]^2=(u[x]^2+u^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<>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 non-linear 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).
-
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
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
DiffConstraint
list rather than the
Constraint
list to indicate that the answer may be incomplete.
-
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]
x^3 > x^2*y > x^2*z > x*y^2 > x*y*z > x*z^2 > y^3 > y^2*z > y*z^2
> z^3 > x^2 > x*y > x*z > y^2 > y*z > z^2 > x > y > z > 1
-
Total Degree followed by Lexicographic on [z,y,x]
z^3 > y*z^2 > x*z^2 > y^2*z > x*y*z > x^2*z > y^3 > x*y^2 > x^2*y
> x^3 > z^2 > y*z > x*z > y^2 > x*y > z^2 > z > y > x > 1
-
Total Degree followed by Inverse Lexicographic on [x,y,z]
x^3 > x^2*y > x*y^2 > y^3 > x^2*z > x*y*z > y^2*z > x*z^2 > y*z^2
> z^3 > x^2 > x*y > y^2 > x*z > y*z > z^2 > x > y > z > 1
-
Pure Lexicographic on [x,y,z]
x^3 > x^2*y > x^2*z > x^2 > x*y^2 > x*y*z > x*y > x*z^2 > x*z > x
> y^3 > y^2*z > y^2 > y*z^2 > y*z > y > z^3 > z^2 > z > 1
-
Simple algebraic rankings in
rifsimp
-
The rankings for Groebner basis computations in
rifsimp
are specified by the
grob_rank=[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:
-
grob_rank=[[1,deg,none],[1,ilex]]
-
This says to use algebraic total-degree ranking followed by inverse lexicographic ranking (this is the default).
-
grob_rank=[[1,deg,none],[1,lex]]
-
Use algebraic total-degree ranking followed by lexicographic ranking.
-
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.
diffdeg any criterion comparing differentiations of more than one
independent variable
diffvar any criterion involving differentiations of a single independent
variable
depvar any criterion only involving dependent variables
other any criterion which mixes independent and dependent variables
all all possible criteria
none no criteria
-
For more detail about criteria, please see
rifsimp[ranking]
. In that help page, an example of the
diffdeg
classification is given by criterion 2,
diffvar
by criterion 3, and
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
grob_rank
-
With the above information we can now construct a differential monomial ranking as an example. Suppose we define our first criterion as
[1,deg,diffdeg]
. 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:
{f[xx], f[xy], f[yy]}, {f[x], f[y]}, {f}
-
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:
f[xx]^2*f[xy]*f[y]*f < f[yy]^4 Degree in second order derivatives
is 3 < 4
f[xy]*f[yy] < f[xx]^3 Degree in second order derivatives
is 2 < 3
f[xy]^2*f[yy]*f[y]*f^20 < Degree in first order derivatives
f[yy]^3*f[x]^2*f^3 is 1 < 2.
-
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:
{f[xx]},{f[xy]},{f[yy]},{f[x]},{f[y]},{f}
-
This is presented in the same manner as the equivalence classes for the degree-type monomial ranking.
f[xx]^2 f[xy] f[y] f < f[xx]^3 f[x] f Degree in f[xx] is 2 < 3.
f[xx]^2 f[yy] < f[xx]^2 f[xy] Degree in f[xy] is 0 < 1.
f[xy]^2 f[yy] f[x] f[y] f < Degree in f[x] is
f[xy]^2 f[yy] f[x]^2 f 1 < 2.
-
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
grob_rank=[[1,deg,diffdeg],[1,lex]]
, and the above examples, the list of equivalence classes is given as follows:
[{f[xx], f[xy], f[yy]}, {f[x], f[y]}, {f}, {f[xx]}, {f[xy]}, {f[yy]},
{f[x]}, {f[y]}, {f}]}
-
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 [[1,deg,diffdeg],[1,lex]]. 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
[[1,deg,diffdeg],[2,lex]]
. This would have the effect of changing the order of the combined equivalence classes to the following:
[{f[xx], f[xy], f[yy]}, {f[xx]}, {f[xy]}, {f[yy]}, {f[x], f[y]},
{f[x]}, {f[y]}, {f}, {f}]
-
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.
f[xx]^2 f[xy] f[y] f < f[yy]^4 Degree in second order derivatives
is 3 < 4.
f[xy]^2 f[yy] f[y]^6 < f[xx]^3 Degree in f[xx] is 0 < 3*.
f[yy]^3 f[y]^2 f^20 < Degree in first order derivative
f[yy]^3 f[x]^2 f^3 f[x] is 0 < 2*.
-
The comparisons with * will give different results for the non-nested ranking.
Examples
The following example arises from the parameterization of an ellipse (where we have used
PDEtools[declare]
to compact the output and display the derivatives in primed notation.
>
with(Rif):
PDEtools[declare](x(t),y(t),z(t),prime=t);
>
sys1:=[diff(y(t),t)-x(t)^2-x(t),
y(t)^4-2*y(t)^2*diff(z(t),t)+diff(z(t),t)^2
-y(t)^2+2*diff(z(t),t),
diff(x(t),t)^2+2*y(t)*diff(x(t),t)+y(t)^4];
Calling with the default ranking gives the following:
>
ans1:=rifsimp(sys1);
So we have isolated ODE for
y'
,
x''
and
z''
, and four constraints involving
x
,
y
,
x'
, and
z'
.
>
nops(ans1[Constraint]);
If instead we want to perform an elimination of
x
, then
z
, then
y
, we can specify this through use of a lex ranking for the algebraic problem.
>
ans2:=rifsimp(sys1,[[x],[z],[y]],grob_rank=[[1,lex]]);
so now we have isolated ODE for
x
and
z''
, an ODE in
y'''
in terms of
y
alone, and two constraints involving
z'
,
y''
,
y'
and
y
.
For an example of the use of the
grobonly
and
checkempty
options we consider the following algebraic system:
>
sys3:=Groebner[gbasis]([(b+a^2)^2,a^3-c],tdeg(a,b,c));
If we call rifsimp with this system, and the inequation
a^2+b<>0
we get:
>
ans3_1:=rifsimp([op(sys3),a^2+b<>0],nopiv=[b],casesplit,grobonly);
But with the additional option 'checkempty' we get
>
ans3_2:=rifsimp([op(sys3),a^2+b<>0],nopiv=[b],casesplit,grobonly,checkempty);
because
ans3_1
represents an empty case.