RootFinding[Parametric] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Factorization and Solving Equations : Roots : RootFinding : Parametric Subpackage : RootFinding/Parametric/CellDecomposition

RootFinding[Parametric]

  

CellDecomposition

  

decompose parameter space into open cells

 

Calling Sequence

Parameters

Options

Description

Examples

Compatibility

Calling Sequence

CellDecomposition(sys, vars, pars, options)

CellDecomposition(eqs, posineqs, vars, pars, options)

CellDecomposition(eqs, posineqs, nzineqs, vars, pars, options)

Parameters

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 g0

options

-

sequence of optional equations of the form keyword=value, where keyword is either output or method

Options

  

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.

Description

• 

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

Examples

In the following univariate example, obtain the well-known discriminant of a quadratic polynomial.

withRootFinding&lsqb;Parametric&rsqb;&colon;

m1CellDecompositionx2&plus;ax&plus;b&equals;0&comma;x

m1:=Equations&equals;ax+x2+bInequalities&equals;Filter&equals;01Variables&equals;xParameters&equals;a&comma;bDiscriminantVariety&equals;a24bProjectionPolynomials&equals;b&comma;a24bSamplePoints&equals;a=0&comma;b=−1&comma;a=−3&comma;b=1&comma;a=0&comma;b=1&comma;a=3&comma;b=1

(1)

Thus, there are 4 full-dimensional open cells, which you can illustrate graphically:

CellPlotm1&comma;&apos;samplepoints&apos;

The number of solutions for x on each of these cells can be computed using the following command:

NumberOfSolutionsm1

1&comma;2&comma;2&comma;2&comma;3&comma;0&comma;4&comma;2

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

m2CellDecompositionx6ax2&plus;b&equals;0&comma;0<b&comma;x

m2:=Equations&equals;x6ax2+bInequalities&equals;bFilter&equals;01Variables&equals;xParameters&equals;a&comma;bDiscriminantVariety&equals;b&comma;4a327b2ProjectionPolynomials&equals;b&comma;4a327b2SamplePoints&equals;a=1&comma;b=1&comma;a=2&comma;b=1

(3)

CellPlotm2&comma;&apos;samplepoints&apos;

m3CellDecompositionm2:-Equations&comma;m2:-Inequalities&comma;m2:-Variables&comma;m2:-Parameters

m3:=Equations&equals;x6ax2+bInequalities&equals;bFilter&equals;01Variables&equals;xParameters&equals;a&comma;bDiscriminantVariety&equals;b&comma;4a327b2ProjectionPolynomials&equals;b&comma;4a327b2SamplePoints&equals;a=1&comma;b=1&comma;a=2&comma;b=1

(4)

Sample points lying entirely in a negative octant are omitted. For example, the open cells represented by the sample points a&equals;1&comma;b&equals;1 and a&equals;2&comma;b&equals;1 from m4:-SamplePoints are not included in m3:-SamplePoints.

m4CellDecompositionx6ax2&plus;b&equals;0&comma;x

m4:=Equations&equals;x6ax2+bInequalities&equals;Filter&equals;01Variables&equals;xParameters&equals;a&comma;bDiscriminantVariety&equals;b&comma;4a327b2ProjectionPolynomials&equals;b&comma;4a327b2SamplePoints&equals;a=1&comma;b=−1&comma;a=2&comma;b=−1&comma;a=1&comma;b=1&comma;a=2&comma;b=1

(5)

CellPlotm4&comma;&apos;samplepoints&apos;

The following system has no solutions for almost all parameters values.

m5CellDecompositionx6&plus;ay2a&equals;0&comma;x6&plus;ay2b&equals;0&comma;x&comma;y

m5:=Equations&equals;x6+ay2a&comma;x6+ay2bInequalities&equals;Filter&equals;01Variables&equals;x&comma;yParameters&equals;a&comma;bDiscriminantVariety&equals;abProjectionPolynomials&equals;&comma;abSamplePoints&equals;a=−1&comma;b=0&comma;a=1&comma;b=0

(6)

NumberOfSolutionsm5

1&comma;0&comma;2&comma;0

(7)

CellPlotm5&comma;&apos;samplepoints&apos;

In this example, we use two different strategies to compute the sample points.

m6CellDecompositionx6&plus;ay2a&equals;0&comma;a3x6&plus;ay2b&equals;0&comma;x&comma;y

m6:=Equations&equals;x6+ay2a&comma;a3x6+ay2bInequalities&equals;Filter&equals;01Variables&equals;x&comma;yParameters&equals;a&comma;bDiscriminantVariety&equals;a&comma;a1&comma;ab&comma;a4b&comma;a2+a+1ProjectionPolynomials&equals;b&comma;1+b&comma;a&comma;a1&comma;ab&comma;a4b&comma;a2+a+1SamplePoints&equals;a=−2&comma;b=−1&comma;a=12&comma;b=−1&comma;a=12&comma;b=−1&comma;a=2&comma;b=−1&comma;a=−1&comma;b=12&comma;a=57785961645137438953472&comma;b=12&comma;a=14&comma;b=12&comma;a=92145700013137438953472&comma;b=12&comma;a=253010876763274877906944&comma;b=12&comma;a=2&comma;b=12&comma;a=−2&comma;b=2&comma;a=−1&comma;b=2&comma;a=12&comma;b=2&comma;a=300882334819274877906944&comma;b=2&comma;a=10958032207368719476736&comma;b=2&comma;a=3&comma;b=2

(8)

m7CellDecompositionx6&plus;ay2a&equals;0&comma;a3x6&plus;ay2b&equals;0&comma;x&comma;y&comma;&apos;output&apos;&equals;&apos;witnesspoints&apos;

m7:=Equations&equals;x6+ay2a&comma;a3x6+ay2bInequalities&equals;Filter&equals;01Variables&equals;x&comma;yParameters&equals;a&comma;bDiscriminantVariety&equals;a&comma;a1&comma;ab&comma;a4b&comma;a2+a+1SamplePoints&equals;a=−1&comma;b=−2&comma;a=−1&comma;b=0&comma;a=−1&comma;b=2&comma;a=12&comma;b=−1&comma;a=12&comma;b=932&comma;a=12&comma;b=2&comma;a=2&comma;b=1&comma;a=2&comma;b=3&comma;a=2&comma;b=17

(9)

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&colon;

EnclosingBoxm7&colon;

CellPlotm7&comma;&apos;samplepoints&apos;&comma;&apos;cellcolor&apos;&equals;white&comma;gray&comma;&apos;boxcolor&apos;&equals;DeepSkyBlue

The option output=witnesspoints usually returns fewer points.

p51a&plus;77b&plus;95c&plus;1x3&plus;a&plus;55b28c&plus;16x2&plus;30a27b15c59x96a&plus;72b87c&plus;47

p:=51a&plus;77b&plus;95c&plus;1x3&plus;a&plus;55b28c&plus;16x2&plus;30a27b15c59x96a&plus;72b87c&plus;47

(10)

m8CellDecompositionp&equals;0&comma;x&colon;

m9CellDecompositionp&equals;0&comma;x&comma;&apos;output&apos;&equals;&apos;witnesspoints&apos;&colon;

nopsm8:-SamplePoints

410

(11)

nopsm9:-SamplePoints

126

(12)

The option method=RC computes the equivalent solution record as the default GB method, but usually gives different sample points.

m10CellDecompositionx3&plus;ax2&plus;bx&plus;a&equals;0&comma;x&comma;a&comma;b&comma;method&equals;RC

m10:=Equations&equals;x3+x2a+xb+aInequalities&equals;Filter&equals;01Variables&equals;xParameters&equals;a&comma;bDiscriminantVariety&equals;a414a2b292a2b+b3+274a2ProjectionPolynomials&equals;b&comma;1+b&comma;b9&comma;a414a2b292a2b+b3+274a2SamplePoints&equals;a=317512&comma;b=12&comma;a=0&comma;b=12&comma;a=317512&comma;b=12&comma;a=0&comma;b=12&comma;a=0&comma;b=5&comma;a=759128&comma;b=192&comma;a=693128&comma;b=192&comma;a=0&comma;b=192&comma;a=693128&comma;b=192&comma;a=759128&comma;b=192

(13)

NumberOfSolutionsm10

1&comma;1&comma;2&comma;3&comma;3&comma;1&comma;4&comma;1&comma;5&comma;1&comma;6&comma;1&comma;7&comma;3&comma;8&comma;1&comma;9&comma;3&comma;10&comma;1

(14)

m10CellDecompositionx3&plus;ax2&plus;bx&plus;a&equals;0&comma;x&comma;a&comma;b

m10:=Equations&equals;x3+x2a+xb+aInequalities&equals;Filter&equals;01Variables&equals;xParameters&equals;a&comma;bDiscriminantVariety&equals;4a4a2b218a2b+4b3+27a2ProjectionPolynomials&equals;b&comma;1+b&comma;b9&comma;4a4a2b218a2b+4b3+27a2SamplePoints&equals;a=−1&comma;b=−1&comma;a=0&comma;b=−1&comma;a=1&comma;b=−1&comma;a=0&comma;b=12&comma;a=0&comma;b=5&comma;a=−6&comma;b=10&comma;a=1545779234793274877906944&comma;b=10&comma;a=0&comma;b=10&comma;a=1545779234793274877906944&comma;b=10&comma;a=6&comma;b=10

(15)

NumberOfSolutionsm10

1&comma;1&comma;2&comma;3&comma;3&comma;1&comma;4&comma;1&comma;5&comma;1&comma;6&comma;1&comma;7&comma;3&comma;8&comma;1&comma;9&comma;3&comma;10&comma;1

(16)

The following examples illustrate invalid inputs:

This system has solutions of multiplicity greater than 1 for all parameter values.

CellDecompositionx2&plus;y2&equals;a2&comma;x&equals;a&comma;x&comma;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&equals;ay&comma;y&equals;az&comma;x&equals;a2z&comma;x&comma;y&comma;z

Error, (in RootFinding:-Parametric:-CellDecomposition) cannot solve the system: there are infinitely many complex solutions, for almost all parameter values

Compatibility

• 

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

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam