Overview of the RootFinding:-Parametric Subpackage
Accessing RootFinding:-Parametric Subpackage Commands
List of RootFinding:-Parametric Subpackage Commands
The Solution Record Data Structure
The RootFinding:-Parametric subpackage is designed for parametric systems of polynomial equations and inequalities. The subpackage provides routines for performing a structural analysis of a parametric polynomial system
where f and g are polynomials in two sets of variables, called indeterminates and parameters. This analysis is needed to answer questions such as these: For which parameter values does the system have real solutions for the indeterminates, and how many?
The main command of the package that is used to answer this question is CellDecomposition; it decomposes the parameter space of a parametric system into cells in which the original system has a constant number of solutions.
The idea is to divide the parameter space S into two parts, W and S∖W; W is represented by polynomial equations and S∖W by polynomial inequalities in the parameter space.
W (so-called discriminant variety) includes those parameter values leading to non-generic solutions of the input system, such as infinitely many solutions, solutions at infinity, or solutions of multiplicity greater than 1.
The polynomial equations defining W are a generalization of the discriminant of a univariate polynomial.
The complement S∖W is a finite union of connected open cells, with the important property that the number of real solutions of the input system is finite and remains constant when the parameter values are varied within the same cell. This yields a complete categorization of the parameter space in terms of the number of real solutions of the system.
The commands in this subpackage further subdivide the cells S∖W, maintaining the key property that the number of solutions of the system is constant on each cell. For each full-dimensional open cell, a sample point strictly in the interior of the cell is computed.
The input system is assumed to satisfy the following requirements:
The number of equations is greater or equal to the number of indeterminates.
At least one and at most finitely many complex solutions exist for almost all complex parameter values (that is, the system is generically solvable and 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.
Each command in the RootFinding:-Parametric subpackage can be accessed using either the long form or the short form of the command name in the command calling sequence.
The long form, RootFinding:-Parametric:-command, is always available. The short form can be used after loading the package.
The following is a list of available commands:
CellDecomposition - decompose a parameter space into full-dimensional open cells such that the number of solutions of the given system is finite and constant on each cell
CellDescription - describe an open cell in terms of real roots of some boundary polynomials
CellLocation - determine the open cell in which a given point in parameter space lies
CellPlot - plot one or more open cells
CellsWithSolutions - find all open cells with a given number of real solutions
DiscriminantVariety - compute the discriminant variety of a parametric polynomial system
NumberOfSolutions - compute the number of real solutions for each open cell
SampleSolutions - find all real solutions of the non-parametric system resulting from substituting given parameter values
To display the help page for a particular RootFinding:-Parametric command, see Getting Help with a Command in a Package.
Most commands in the RootFinding:-Parametric subpackage return as output or accept as input a solution record, which captures structural information about a parametric polynomial system. This is a record with the following fields:
Equations: list of polynomials f representing the equations of the system
Inequalities: list of polynomials g representing the inequalities of the system, of the form 0<g
NonEquations: list of polynomials g representing the inequalities of the system, of the form g≠0
Variables: list of names; the indeterminates
Parameters: list of names; the parameters
DiscriminantVariety: list of lists of polynomials in the parameter variables; the discriminant variety is the union of the varieties of each inner list of polynomials
ProjectionPolynomials: list of lists of polynomials in the parameter variables representing the projection polynomials in the sense of the Cylindrical Algebraic Decomposition (CAD)
SamplePoints: list of lists of equations, of the form parameter=rational number, once for each open cell of the CAD; each list represents a sample point strictly in the interior of the cell
Boxes: list of lists of equations, of the form parameter=[rational number, rational number], at least once for each open connected cell in the parameter space; each list represents a box strictly in the interior of the cell
The fields of a solution record m can be accessed using the selection operator, :-, like this: m:-Equations, m:-Inequalities, etc.
Note that although it is possible to modify the fields in a solution record, this is not recommended.
This example studies the parametric univariate polynomial x3−a⁢x+b. How many real solutions does this polynomial have, depending on the parameter values a and b? First compute the discriminant variety, which in this case corresponds to the well-known discriminant.
f ≔ x3−a⁢x+b
Compute and plot the decomposition of the two-dimensional parameter space into full-dimensional open cells, including a sample point in the interior of each cell.
m ≔ CellDecomposition⁡f=0,x
Notice that there are four cells in total. Compute the number of real solutions of the system for each cell.
Thus, the system has one real solution if parameters are chosen from the yellow or pink cells, and three real solutions if parameters are chosen from the blue or green cells. Verify that conclusion for cells 1 and 2 by solving the system at the corresponding sample points:
Compute a geometric description of the second cell.
The result is interpreted as follows: A point a,b=u,v in the parameter space belongs to the second cell if and only if
v is less than the smallest root of b=0, that is, v<0, and
u is greater than the smallest real root of 4⁢a3−27⁢v2=0, or equivalently, u>3⋅v243
The point a,b=4,−2 satisfies these requirements. Confirm that it indeed lies in the second cell.
Lazard, D., and Rouillier, F. "Solving parametric polynomial systems." Journal of Symbolic Computation, Vol. 42 No. 6 (2007): 636 - 667.
Liang, S., Gerhard, J., Jeffrey, D. J., and Moroz G., "A Package for Solving Parametric Polynomial Systems." ACM Communications in Computer Algebra, Vol. 43 No. 3 (2009): 61 - 72.
Moroz, G. "Sur la décomposition réelle et algébrique des systèmes dépendant de paramètres." Ph.D. thesis, l'Universite de Pierre et Marie Curie, Paris, France. 2008.
Download Help Document