RootFinding[Parametric]
CellDecomposition
decompose parameter space into open cells
Calling Sequence
Parameters
Options
Description
Examples
Compatibility
CellDecomposition(sys, vars, pars, options)
CellDecomposition(eqs, posineqs, vars, pars, options)
CellDecomposition(eqs, posineqs, nzineqs, vars, pars, options)
sys
-
list of equations, strict inequalities, and inequations between polynomials with rational coefficients
vars
list of names; the indeterminates
pars
(optional in the first two calling sequences) list of names; the parameters
eqs
list of polynomials f with rational coefficients, representing the equations of the form f=0
posineqs
list of polynomials g with rational coefficients, representing constraint inequalities of the form 0<g
nzineqs
list of polynomials g with rational coefficients, representing constraint inequations of the form g≠0
options
sequence of optional equations of the form keyword=value, where keyword is either output or method
output=cad or witnesspoints: type of decomposition
If output=cad, the command computes an open Cylindrical Algebraic Decomposition (CAD) of the parameter space. In addition, the record contains the projection polynomials describing the CAD of the parameter space such that the number of solutions of the input system is constant on each full-dimensional open cell of the decomposition.
The option output is set to cad by default.
The option output=witnesspoints avoids the computation of a CAD by using the command RootFinding[WitnessPoints] internally. When output=witnesspoints, the output does not include the field ProjectionPolynomials.
method=GB or RC: algorithm to use
By default, the Groebner basis method (GB) is used. The RegularChains method can be accessed by specifying method=RC.
When output=witnesspoints is specified, the Groebner basis method will be used even if method=RC.
The CellDecomposition command decomposes the parameter space of a parametric polynomial system into cells in which the original system has a constant number of solutions.
The command returns a data structure that can be used for (for example):
Plotting the regions of the parameter space for which the system has a given number of solutions (see CellPlot)
Extracting sample points in the parameter space for which the system has a given number of solutions (see SampleSolutions)
Extracting boxes in the parameter space in which the system has a given number of solutions (see EnclosingBox)
The type of the output is a solution record with the following fields: Equations, Inequalities, Filter, Variables, Parameters, DiscriminantVariety, ProjectionPolynomials (sometimes present), and SamplePoints. The field Boxes is not initially present, but is added if you call EnclosingBox on a solution from CellDecomposition, as shown in the Examples section below.
The record returned captures information about the solutions of the system depending on the parameter values, including:
A discriminant variety (see DiscriminantVariety)
For each full-dimensional open cell, a sample point strictly in the interior of the cell; if possible, the coordinates of the sample point are chosen to be integers
The input system must satisfy the following properties:
The number of equations is equal to or greater than the number of indeterminates
At most finitely many complex solutions exist for almost all complex parameter values (that is, the system is generically zero-dimensional)
For almost all complex parameter values, there are no solutions of multiplicity greater than 1 (that is, the system is generically radical); in particular, the input equations are square-free
An error occurs if one of these conditions is violated.
If pars is not specified, it defaults to all the names in sys that are not indeterminates.
Note that if the input system sys contains an inequality of the form 0<parameter (or ineqs contains parameter), then sample points for those cells lying entirely in the octant described by the inequality parameter<0 may not be computed (see the examples below).
This command is part of the RootFinding[Parametric] package, so it can be used in the form CellDecomposition(..) only after executing the command with(RootFinding[Parametric]). However, it can always be accessed through the long form of the command by using RootFinding[Parametric][CellDecomposition](..).
In the following univariate example, obtain the well-known discriminant of a quadratic polynomial.
withRootFindingParametric:
m1≔CellDecompositionx2+ax+b=0,x
m1≔Equations=ax+x2+bInequalities=Filter=0≠1Variables=xParameters=a,bDiscriminantVariety=a2−4bProjectionPolynomials=b,a2−4bSamplePoints=a=0,b=−1,a=−3,b=1,a=0,b=1,a=3,b=1
Thus, there are 4 full-dimensional open cells, which you can illustrate graphically:
CellPlotm1,samplepoints
The number of solutions for x on each of these cells can be computed using the following command:
NumberOfSolutionsm1
1,2,2,2,3,0,4,2
So, the univariate equation has exactly two solutions in the yellow and pink cells, below the parabola, and no solution in the blue cell, above the parabola. In fact, it has one solution of multiplicity 2 exactly on the parabola, but this is a lower-dimensional sub-manifold, which is not considered by this command.
The next two examples illustrate the alternate calling sequences. Since the output of the assignment is the same for m2 and m3, they will each produce the same image using the CellPlot command.
m2≔CellDecompositionx6−ax2+b=0,0<b,x
m2≔Equations=x6−ax2+bInequalities=bFilter=0≠1Variables=xParameters=a,bDiscriminantVariety=b,4a3−27b2ProjectionPolynomials=b,4a3−27b2SamplePoints=a=1,b=1,a=2,b=1
CellPlotm2,samplepoints
m3≔CellDecompositionm2:-Equations,m2:-Inequalities,m2:-Variables,m2:-Parameters
m3≔Equations=x6−ax2+bInequalities=bFilter=0≠1Variables=xParameters=a,bDiscriminantVariety=b,4a3−27b2ProjectionPolynomials=b,4a3−27b2SamplePoints=a=1,b=1,a=2,b=1
Sample points lying entirely in a negative octant are omitted. For example, the open cells represented by the sample points a=1,b=−1 and a=2,b=−1 from m4:-SamplePoints are not included in m3:-SamplePoints.
m4≔CellDecompositionx6−ax2+b=0,x
m4≔Equations=x6−ax2+bInequalities=Filter=0≠1Variables=xParameters=a,bDiscriminantVariety=b,4a3−27b2ProjectionPolynomials=b,4a3−27b2SamplePoints=a=1,b=−1,a=2,b=−1,a=1,b=1,a=2,b=1
CellPlotm4,samplepoints
The following system has no solutions for almost all parameters values.
m5≔CellDecompositionx6+ay2−a=0,x6+ay2−b=0,x,y
m5≔Equations=x6+ay2−a,x6+ay2−bInequalities=Filter=0≠1Variables=x,yParameters=a,bDiscriminantVariety=a−bProjectionPolynomials=,a−bSamplePoints=a=−1,b=0,a=1,b=0
NumberOfSolutionsm5
1,0,2,0
CellPlotm5,samplepoints
In this example, we use two different strategies to compute the sample points.
m6≔CellDecompositionx6+ay2−a=0,a3x6+ay2−b=0,x,y
m6≔Equations=x6+ay2−a,a3x6+ay2−bInequalities=Filter=0≠1Variables=x,yParameters=a,bDiscriminantVariety=a,a−1,a−b,a4−b,a2+a+1ProjectionPolynomials=b,b−1,a,a−1,a−b,a4−b,a2+a+1SamplePoints=a=−2,b=−1,a=−12,b=−1,a=12,b=−1,a=2,b=−1,a=−1,b=12,a=−9467651955984352251799813685248,b=12,a=24758800785707605497982479019903520314283042199192993792,b=12,a=16599493609768089638877596352475880078570760549798248448,b=12,a=139094200477264349448505151115727451828646838272,b=12,a=2,b=12,a=−2,b=2,a=−1,b=2,a=12,b=2,a=98593123473627919007199254740992,b=2,a=5745164789893679336028797018963968,b=2,a=3,b=2
m7≔CellDecompositionx6+ay2−a=0,a3x6+ay2−b=0,x,y,output=witnesspoints
m7≔Equations=x6+ay2−a,a3x6+ay2−bInequalities=Filter=0≠1Variables=x,yParameters=a,bDiscriminantVariety=a,a−1,a−b,a4−b,a2+a+1SamplePoints=a=−1,b=−2,a=−1,b=0,a=−1,b=2,a=12,b=−1,a=12,b=932,a=12,b=2,a=2,b=1,a=2,b=3,a=2,b=17
When we use the strategy witnesspoints, the record m7 contains no ProjectionPolynomials.
m6 and m7 can be visualized with CellPlot.
CellPlotm6
CellPlotm7
When EnclosingBox has been applied to the solutions, the enclosing boxes are also displayed by CellPlot.
withRootFinding:
EnclosingBoxm7:
CellPlotm7,samplepoints,cellcolor=white,gray,boxcolor=DeepSkyBlue
The option output=witnesspoints usually returns fewer points.
p≔−51a+77b+95c+1x3+a+55b−28c+16x2+30a−27b−15c−59x−96a+72b−87c+47
m8≔CellDecompositionp=0,x:
m9≔CellDecompositionp=0,x,output=witnesspoints:
nopsm8:-SamplePoints
410
nopsm9:-SamplePoints
126
The option method=RC computes the equivalent solution record as the default GB method, but usually gives different sample points.
m10≔CellDecompositionx3+ax2+bx+a=0,x,a,b,method=RC
m10≔Equations=x3+x2a+xb+aInequalities=Filter=0≠1Variables=xParameters=a,bDiscriminantVariety=a4−14a2b2−92a2b+b3+274a2ProjectionPolynomials=b,b−9,b−1,a4−14a2b2−92a2b+b3+274a2SamplePoints=a=−317512,b=−12,a=0,b=−12,a=317512,b=−12,a=0,b=12,a=0,b=5,a=−759128,b=192,a=−693128,b=192,a=0,b=192,a=693128,b=192,a=759128,b=192
NumberOfSolutionsm10
1,1,2,3,3,1,4,1,5,1,6,1,7,3,8,1,9,3,10,1
m10≔CellDecompositionx3+ax2+bx+a=0,x,a,b
m10≔Equations=x3+x2a+xb+aInequalities=Filter=0≠1Variables=xParameters=a,bDiscriminantVariety=4a4−a2b2−18a2b+4b3+27a2ProjectionPolynomials=b,b−9,b−1,4a4−a2b2−18a2b+4b3+27a2SamplePoints=a=−1,b=−1,a=0,b=−1,a=1,b=−1,a=0,b=12,a=0,b=5,a=−6,b=10,a=−791438968214443140737488355328,b=10,a=0,b=10,a=123662338783532199023255552,b=10,a=6,b=10
The following examples illustrate invalid inputs:
This system has solutions of multiplicity greater than 1 for all parameter values.
CellDecompositionx2+y2=a2,x=a,x,y
Error, (in RootFinding:-Parametric:-CellDecomposition) cannot solve the system: either there are infinitely many complex solutions, or there are solutions of multiplicity > 1, for almost all parameter values
This system has infinitely many solutions for all parameter values.
CellDecompositionx=ay,y=az,x=a2z,x,y,z
Error, (in RootFinding:-Parametric:-CellDecomposition) cannot solve the system: there are infinitely many complex solutions, for almost all parameter values
The method option was introduced in Maple 15.
For more information on Maple 15 changes, see Updates in Maple 15.
See Also
CellPlot
DiscriminantVariety
EnclosingBox
Groebner
NumberOfSolutions
Parametric
PolynomialIdeals
RegularChains
RootFinding
WitnessPoints
Download Help Document
