Overview - Maple Help

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

${\left[f=0,0

 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\setminus W$; $W$ is represented by polynomial equations and $S\setminus 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\setminus 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\setminus 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.

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

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 $f$ representing the equations of the system
 – Inequalities: list of polynomials $g$ representing the inequalities of the system, of the form $0
 – NonEquations: list of polynomials $g$ representing the inequalities of the system, of the form $g\ne 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.

Examples

This example studies the parametric univariate polynomial ${x}^{3}-ax+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.

 > $\mathrm{with}\left(\mathrm{RootFinding}\left[\mathrm{Parametric}\right]\right)$
 $\left[{\mathrm{CellDecomposition}}{,}{\mathrm{CellDescription}}{,}{\mathrm{CellLocation}}{,}{\mathrm{CellPlot}}{,}{\mathrm{CellsWithSolutions}}{,}{\mathrm{DiscriminantVariety}}{,}{\mathrm{NumberOfSolutions}}{,}{\mathrm{SampleSolutions}}\right]$ (1)
 > $f≔{x}^{3}-ax+b$
 ${f}{≔}{{x}}^{{3}}{-}{a}{}{x}{+}{b}$ (2)
 > $\mathrm{DiscriminantVariety}\left(\left[f=0\right],\left[x\right]\right)$
 $\left[\left[{4}{}{{a}}^{{3}}{-}{27}{}{{b}}^{{2}}\right]\right]$ (3)
 > $\mathrm{discrim}\left(f,x\right)$
 ${4}{}{{a}}^{{3}}{-}{27}{}{{b}}^{{2}}$ (4)

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≔\mathrm{CellDecomposition}\left(\left[f=0\right],\left[x\right]\right)$
 ${m}{≔}\left[\begin{array}{lll}{\mathrm{Equations}}& {=}& {}\left[{{x}}^{{3}}{-}{a}{}{x}{+}{b}\right]\\ {\mathrm{Inequalities}}& {=}& {}\left[\right]\\ {\mathrm{Filter}}& {=}& {}{0}{\ne }{1}\\ {\mathrm{Variables}}& {=}& {}\left[{x}\right]\\ {\mathrm{Parameters}}& {=}& {}\left[{a}{,}{b}\right]\\ {\mathrm{DiscriminantVariety}}& {=}& {}\left[\left[{4}{}{{a}}^{{3}}{-}{27}{}{{b}}^{{2}}\right]\right]\\ {\mathrm{ProjectionPolynomials}}& {=}& {}\left[\left[{b}\right]{,}\left[{4}{}{{a}}^{{3}}{-}{27}{}{{b}}^{{2}}\right]\right]\\ {\mathrm{SamplePoints}}& {=}& {}\left[\left[{a}{=}{1}{,}{b}{=}{-1}\right]{,}\left[{a}{=}{2}{,}{b}{=}{-1}\right]{,}\left[{a}{=}{1}{,}{b}{=}{1}\right]{,}\left[{a}{=}{2}{,}{b}{=}{1}\right]\right]\end{array}\right$ (5)
 > $m:-\mathrm{SamplePoints}$
 $\left[\left[{a}{=}{1}{,}{b}{=}{-1}\right]{,}\left[{a}{=}{2}{,}{b}{=}{-1}\right]{,}\left[{a}{=}{1}{,}{b}{=}{1}\right]{,}\left[{a}{=}{2}{,}{b}{=}{1}\right]\right]$ (6)
 > $\mathrm{CellPlot}\left(m,'\mathrm{samplepoints}'\right)$

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

 > $\mathrm{NumberOfSolutions}\left(m\right)$
 $\left[\left[{1}{,}{1}\right]{,}\left[{2}{,}{3}\right]{,}\left[{3}{,}{1}\right]{,}\left[{4}{,}{3}\right]\right]$ (7)
 > $\mathrm{CellsWithSolutions}\left(m,3\right)$
 $\left[{2}{,}{4}\right]$ (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 $1$ and $2$ by solving the system at the corresponding sample points:

 > $\mathrm{SampleSolutions}\left(m,1\right)$
 $\left[\left[{x}{=}{1.324717957}\right]\right]$ (9)
 > $\mathrm{SampleSolutions}\left(m,2\right)$
 $\left[\left[{x}{=}{-1.}\right]{,}\left[{x}{=}{-0.6180339887}\right]{,}\left[{x}{=}{1.618033989}\right]\right]$ (10)

Compute a geometric description of the second cell.

 > $\mathrm{CellDescription}\left(m,2\right)$
 $\left[\left[{-}{\mathrm{\infty }}{,}{0}{,}{b}{,}{b}{,}{1}\right]{,}\left[{4}{}{{a}}^{{3}}{-}{27}{}{{b}}^{{2}}{,}{1}{,}{a}{,}{\mathrm{\infty }}{,}{0}\right]\right]$ (11)

The result is interpreted as follows: A point $\left[a,b\right]=\left[u,v\right]$ 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{a}^{3}-27{v}^{2}=0$, or equivalently, $u>3\cdot \sqrt[3]{\frac{{v}^{2}}{4}}$

The point $\left[a,b\right]=\left[4,-2\right]$ satisfies these requirements. Confirm that it indeed lies in the second cell.

 > $\mathrm{CellLocation}\left(m,\left[4,-2\right]\right)$
 ${2}$ (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.