Overview of the RootFinding[Parametric] Subpackage

Calling Sequence


RootFinding[Parametric][command](arguments)
command(arguments)


Description


•

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

•

(socalled discriminant variety) includes those parameter values leading to nongeneric solutions of the input system, such as infinitely many solutions, solutions at infinity, or solutions of multiplicity greater than .

•

The polynomial equations defining are a generalization of the discriminant of a univariate polynomial.

•

The complement 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 , maintaining the key property that the number of solutions of the system is constant on each cell. For each fulldimensional 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 zerodimensional).

–

For almost all complex parameter values, there are no solutions of multiplicity greater than (that is, the system is generically radical). In particular, the input equations are squarefree.



Accessing RootFinding[Parametric] Subpackage Commands


•

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. Since the underlying implementation of the RootFinding[Parametric] subpackage is a module, it is also possible to use the form RootFinding[Parametric]:command to access a command.



List of RootFinding[Parametric] Subpackage Commands


•

The following is a list of available commands:


CellDecomposition  decompose a parameter space into fulldimensional 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


SampleSolutions  find all real solutions of the nonparametric system resulting from substituting given parameter values



The Solution Record Data Structure


•

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 representing the equations of the system

–

Inequalities: list of polynomials representing the inequalities of the system, of the form

–

NonEquations: list of polynomials representing the inequalities of the system, of the form

–

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



Examples


This example studies the parametric univariate polynomial . How many real solutions does this polynomial have, depending on the parameter values and ? First compute the discriminant variety, which in this case corresponds to the wellknown discriminant.
>


 (1) 
>


 (2) 
>


 (3) 
>


 (4) 
Compute and plot the decomposition of the twodimensional parameter space into fulldimensional open cells, including a sample point in the interior of each cell.
>


 (5) 
>


 (6) 
>


Notice that there are four cells in total. Compute the number of real solutions of the system for each cell.
>


 (7) 
>


 (8) 
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 and by solving the system at the corresponding sample points:
>


 (9) 
>


 (10) 
Compute a geometric description of the second cell.
>


 (11) 
The result is interpreted as follows: A point in the parameter space belongs to the second cell if and only if
The point satisfies these requirements. Confirm that it indeed lies in the second cell.
>


 (12) 


References



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.


