Isolate - Maple Help

RootFinding

 Isolate
 isolate the real or complex roots of a univariate polynomial or polynomial system

 Calling Sequence Isolate(f) Isolate(f, X, digits=d, constraints=icons, output=outpt, maxroots=mxrts, method=mthd, domain=dom) Isolate(g) Isolate(g, X, digits=d, constraints=rcons, output=outpt, maxroots=mxrts, method=ABND, domain=dom, maxprec=mxprc, partialresults=partial) Isolate(h, X, digits=d, output=outpt, maxroots=mxrts, complex, domain=dom, maxprec=mxprc, partialresults=partial) Isolate(h, X, digits=d, output=outpt, maxroots=mxrts, method=HR, domain=dom, maxprec=mxprc, partialresults=partial) Isolate(h, X, digits=d, output=outpt, maxroots=mxrts, method=PW, domain=dom, maxprec=mxprc, partialresults=partial) Isolate(J, X) Isolate(J, X, digits=d, constraints=icons, output=outpt, maxroots=mxrts, method=mthd, makereal=b)

Parameters

 f - univariate polynomial with real-valued numeric coefficients g - univariate polynomial with real-valued coefficients h - univariate polynomial with complex(numeric) coefficients J - set or list of polynomials, or a PolynomialIdeal X - (optional) name or list of names; the variable(s) d - (optional) positive integer; number of significant digits (default: Digits) icons - (optional) list of polynomials with integer coefficients rcons - (optional) list of polynomials with real coefficients outpt - (optional) type of output: numeric (default), midpoint, or interval mxrts - (optional) maximum number of roots to be returned. Default is $\mathrm{\infty }$. mthd - (optional) name of algorithm to use: ABND, HR, PW, RS, or RC. Default is ABND for univariate and RS for multivariate inputs. complex - (optional) literal name; equivalent to method=PW if the domain option is not given, and method=HR otherwise dom - (optional) list of two complex(extended_numeric) numbers, bounding the search domain in the complex plane mxprc - (optional) maximum internal working precision. Default is $\mathrm{\infty }$ for complex(numeric) coefficients, otherwise see the description of the option below. partial - (optional) return regions that could not be completely decided: $\mathrm{true}$ or $\mathrm{false}$ (default). b - (optional) $\mathrm{true}$ (default) or $\mathrm{false}$; attempt to detect real, imaginary, integer and imaginary integer coordinates

Options

 • The digits=d option controls the output precision.
 – In the case of numeric coefficients and when the method is not HR or PW, the isolating intervals, for both the roots and the constraints, have a relative diameter of at most ${10}^{-d}$. That is, if the result is evaluated numerically, the resulting floating-point mantissae have $d$ digits and an error of at most $0.6$ units in the last place. Note that this does not necessarily mean that the preceding digits are correct; e.g., an exact value of $\frac{5751}{2500}$ could be represented with the interval $\left[2.299,2.301\right]$ at digits=$4$. In particular, isolating intervals corresponding to a root of magnitude larger than ${10}^{d}$ may have a width larger than $1$; even if the exact root is an integer, the midpoint does not necessarily round to this value.
 – For non-numeric coefficients, and when the method is not HR or PW, it might not be possible to decide if the trailing coefficient vanishes or, equivalently, whether $0$ is an exact root. In this situation, the isolating interval for the near-$0$ root will be of absolute diameter of at most ${10}^{-d}$ and contain $0$, and neither of the output formats midpoint or numeric (see below) will help to determine the sign of the root; for closer inspection, use the output format interval.
 • The output option specifies the format of the output, and can be one of interval, midpoint, or numeric (the default).
 – output=interval returns a list of intervals (or boxes) with (complex) rational endpoints, each containing a root. The intervals (boxes) are open, unless an exact root is found; in this situation, both endpoints are identical.
 – output=midpoint computes the midpoint of each interval (box) exactly, so that a list of (complex) rational approximations is returned.
 – output=numeric evaluates the midpoints numerically at the desired precision $d$, resulting in a list of (complex) floating-point approximations.
 • The constraints option takes a list of polynomials with real-valued coefficients and evaluates them at the roots of the system. This option is more reliable than direct evaluation using evalf because of two reasons: (1) A smaller numerical error is introduced, and (2) the results are certified in the sense that the exact value of the constraint at the exact root will always be contained in the interval returned by this option. In contrast, evaluation via evalf can be subject to round-off errors and cancellation. For numeric coefficients, the intervals for the results have a relative diameter of at most ${10}^{-d}$. The constraints option is only supported for the RS method, and in the univariate case also for the ABND method.
 • The maxroots option specifies the maximum number of roots to be returned. If the polynomials have fewer roots than maxroots, this setting is ignored. Note that this option does not guarantee any particular roots to be returned.
 This option cannot be used in conjunction with method=RC. If both method=RC and maxroots are given, method=RC is silently ignored in the univariate case and method=ABND is used; in the multivariate case, the maxroots option is silently ignored.
 • The method option specifies the algorithm to use. It can be ABND (default for the univariate case), HR, PW, RS (default for the multivariate case), or RC.
 – method=PW uses the pwpoly C library by Guillaume Moroz and Rémi Imbach and computes all the complex roots (univariate case only; see below).
 – method=HR uses the hefroots C library by Guillaume Moroz and Rémi Imbach and computes all the complex roots (univariate case only; see below).
 – method=RS uses the RealSolving (RS) C library by F. Rouillier et al. and computes only real roots.
 – method=RC computes the result by using the RegularChains package by M. Moreno Maza et al. and computes only real roots.
 – method=ABND uses the Approximate Bitstream Newton-Descartes method by A. Kobel et al. to compute all the real roots, which is based on the univariate components of RS. Compared to RS, the ABND variant gives improved complexity guarantees and significantly improved performance for ill-conditioned problems, and it also can handle non-numeric real coefficients.
 The constraints and maxroots options cannot be used simultaneously with method=RC. If both method=RC and constraints or maxroots are specified, Isolate carries out the computation using method=ABND (univariate case) or method=RS (multivariate case).
 The maxprec and partialresults options can only be used with method=ABND, method=HR, or method=PW (and univariate inputs in each case). If maxprec or partialresults are given and the method is not HR or PW, then the specified method is ignored and method=ABND is used.
 • When method=HR or method=PW, or alternatively, when the complex keyword is specified, all complex roots are computed. These methods only support polynomial(s) with numeric or complex(numeric) coefficients. In this case, the result is a list (or a list of lists in the multivariate case) of isolating boxes in the complex plane, of the form $\left[r+Is,u+Iv\right]$, where $r\le u$ and $s\le v$ are rational numbers. For all nonzero roots, $d$ is the relative accuracy (i.e., the number of significant digits for both the real and the imaginary part).
 • The maxprec option specifies the maximum internal working precision of the root solver when the method is not HR or PW. The numerical solver works in stages of gradually increasing precision; when a new stage begins, the computation is interrupted if the new precision would exceed the given value.
 When both maxprec=mxprc and method=HR or method=PW are given, then the computation will be halted if an accuracy of $\mathrm{min}\left(\mathrm{mxprc},d\right)$ has been reached for all the roots, even if the resulting boxes are not isolating. By default, only the boxes known to contain a single root are returned.
 The unprocessed intermediate results can be inspected with the partialresults option (see below).
 If an interval (box) can be proven to be isolating within the maxprec constraints, but cannot be refined to the accuracy requested through the digits option, it will nevertheless be reported in the default output even if partialresults is not given.
 This option can only be used for univariate polynomials and in conjunction with method=ABND, method=HR, or method=PW. If maxprec is specified and the method is not HR or PW, the choice of method is silently ignored and method=ABND is used.
 • If partialresults=true, a list of intervals (boxes) that have not been fully processed within the limits of maxroots or maxprec is returned as a second (or third) return value. Each item of the list is a record with two fields, named interval and multiplicity. The interval entry contains an interval (box) with (complex) rational endpoints, and when method=ABND, the multiplicity entry contains a certified estimate of the possible number of distinct roots of g in the corresponding interval, given as a range. If method=HR or method=PW is specified, then the multiplicity entry will always be exact, i.e., the upper and lower bounds coincide, and specify the sum of the multiplicities of the roots of h in the box.
 This option can only be used for univariate polynomials and in conjunction with method=ABND, method=HR, or method=PW. If partialresults is specified and the method is not HR or PW, the choice of method is silently ignored and method=ABND is used.
 • When the domain option is specified (only supported for methods ABND, RS, HR, and PW), then all the roots of the univariate polynomial f, g, or h inside the box specified by dom are computed. This includes roots on the boundary, if any, and the boxes returned for such roots will have a nonempty intersection with dom but may not be contained inside dom. In fact, even roots outside of the box may be returned if they are very close to the boundary. $\mathrm{\infty }$ or $-\mathrm{\infty }$ may be used in the domain boundaries, and the domain can also be a subset of the real axis or the imaginary axis. For methods ABND and RS, the domain boundaries must be of type extended_numeric. The domain option is not supported in the multivariate case.
 • When a complex solver is used, i.e., option complex or method=HR or method=PW is given in the multivariate case, then RootFinding:-Isolate will attempt to detect and certify solution components that are real, imaginary, integer, or imaginary integer. This generally increases the running time. In order to speed up the computation, makereal=false can be specified to omit this additional step. This option is ignored in the univariate case or when method=RS or method=RC is used.

Description

 • The RootFinding[Isolate] command isolates the real (or complex) roots of univariate polynomials and polynomial systems with a finite number of solutions. By default it computes isolating intervals (boxes) for each of the roots and numerically evaluates the midpoints of those intervals at the current setting of Digits. If possible, the intervals (boxes) are refined such that the numerical evaluation is accurate up to $0.6$ units in the last place; see the digits option for details.
 Unlike purely numerical methods no roots are ever lost, although repeated roots may be discarded. This command does not support parametric coefficients, i.e., all the variables occurring in the input must be listed in X.
 For a polynomial with complex(numeric) coefficients (that is, the real and imaginary parts of all coefficients are of type integer, fraction, or float), all real (or complex) roots are given in the output, unless specifically requested otherwise; see the maxroots, maxprec, and domain options.
 Polynomials with irrational real coefficients are only supported in the univariate case, and only with method=ABND (see below). For such inputs, complete and certified root isolation is infeasible for sufficiently general instances, and Isolate returns a best-effort output according to the specification in the corresponding section.
 • For multivariate polynomial systems, the second argument must be an ordered list of variables, and the roots are returned as corresponding lists of values. Unless method=RC is specified, Isolate first computes a Groebner basis followed by a Rational Univariate Representation.
 • The system must have a finite number of complex solutions; otherwise, Isolate will return an error.
 • This function is part of the RootFinding package, and can be used in the form Isolate(..) only after executing the command with(RootFinding). However, it can always be accessed through the long form of the command using RootFinding[Isolate](..).

Univariate polynomials with irrational real coefficients

 • Irrational coefficient support for univariate real polynomials is provided with method=ABND. If non-numeric coefficients are given and the method is not HR or PW, then the choice of method is silently ignored and the ABND algorithm is used. If irrational real polynomials are passed to RootFinding[Isolate], the user is required to take proper precautions for dealing with possibly incomplete output; see the description of the maxprec and partialresults options above.
 • In full generality, root isolation for arbitrary polynomials is infeasible: a purely numerical routine can eventually isolate simple roots, but cannot detect multiple roots. A square-free decomposition is required, but this cannot be performed in all situations. A notable exception are polynomials with numeric coefficients, where such a decomposition is done implicitly if required.
 Instead, the ANBD root solver tries a best-effort isolation up to a certain maximum internal working precision maxprec. If the instance could not be conclusively handled within that precision constraint, a partial output is given. It contains (1) a list of proven isolating intervals, (2) a list of the constraint polynomials (if applicable, i.e., if constraints is not empty) evaluated at those isolating intervals, and (3) a list of unresolved intervals (if partialresults=true; see the description of the option above).
 • There is no general way to determine the "right" value of maxprec a priori. For numeric instances, the default maximum precision is virtually infinity; such instances can always be dealt with in a complete manner. For non-numeric instances, the default is chosen purely heuristically, as a function of the value of the Digits environment variable, the digits option, and the degree $n$ of the polynomial g: maxprec defaults to $\mathrm{max}\left(\mathrm{Digits},4d,8n{\mathrm{log}}_{2}\left(n\right)\right)$. Under typical circumstances, the default value allows to isolate and refine well-separated roots of g up to the requested accuracy of d digits, but there is no guarantee.
 • A special situation arises in the case g is a numeric polynomial, but some or all constraints are non-numeric. Under such circumstances, a user-given value maxprec is enforced throughout the entire computation, but a heuristic default of maxprec is applied only to non-numeric constraint evaluation. In particular, an important use case for constraints is to check whether any constraint polynomial might be zero at a root of g.
 If g is a numeric polynomial, the default is to fully isolate the roots of g up to an accuracy of d digits, and to enforce the evaluation of numeric constraints up to d significant digits. In particular, the interval evaluation of a numeric constraint will be $\left[0,0\right]$ if and only if the constraint vanishes at the corresponding root of g; otherwise, all interval evaluations of numeric constraints will not contain $0$.
 Similar guarantees cannot be made if the constraint is non-numeric. In this situation, the numeric subinstances will be solved according to the above rules, and the remaining non-numeric subinstances will be subject to the maxprec heuristic.

Complex roots

 • For a single univariate polynomial h with numeric or complex(numeric) coefficients, when method=HR or method=PW or, alternatively, the complex keyword is given, isolating rectangles (boxes) for all the complex roots are computed.
 • method=PW is generally more efficient than method=HR when the domain option is not used, and it is the default in that case and when only the complex keyword is given.
 • If h has numeric coefficients, then all real roots of h can be certified as such, i.e., the imaginary parts of the bounding boxes are identically zero, and all other boxes lie either strictly in the upper half plane or strictly in the lower half plane.
 • For nonzero roots, the value of d specifies the relative accuracy of the box, i.e., the number of significant digits for both the real and the imaginary part.
 • If maxprec is not given, multiple roots are eliminated by first computing the square-free part $p$. In this case the number of isolating boxes returned will always be equal to the degree of $p$ (unless mxrts is smaller than that degree or the domain option is used).
 • If maxprec is specified, then no square-free factorization is performed, and all roots are approximated with an accuracy of at least d or mxprc, whichever is smaller. If mxprc is too small to separate all the roots or if $h$ has multiple roots, then only the isolating boxes for the simple roots that were actually isolated are returned. If moreover the option partialresults is given, boxes containing more than one root together with the associated sum of the multiplicities are also returned. The number of isolating boxes plus the sum of the multiplicities for all boxes given via partialresults will be equal to the degree of $h$ (unless mxrts is smaller than that degree or the domain option is used).
 • It is possible to limit the search space to a bounded or partially bounded rectangle in the complex plane for method=HR or method=PW by using the domain option; see the description of this option above.
 • The domain and maxroots options can be used in conjunction. If $\mathrm{dom}$ contains $\mathrm{mxrts}$ or more roots, then exactly $\mathrm{mxrts}$ boxes are returned. If maxprec is also used, then the counts include multiplicities.
 • The complex, method=HR, and method=PW options are also supported in the multivariate case. For a system of polynomials with rational or complex(rational) coefficients, all complex roots will be computed. Each solution is returned as a list of complex intervals or numbers, depending on the output option.

Examples

 > $\mathrm{with}\left(\mathrm{RootFinding}\right):$
 > $f≔{x}^{4}-3{x}^{2}+2$
 ${f}{≔}{{x}}^{{4}}{-}{3}{}{{x}}^{{2}}{+}{2}$ (1)
 > $\mathrm{Isolate}\left(f\right)$
 $\left[{x}{=}{-1.414213562}{,}{x}{=}{-1.}{,}{x}{=}{1.}{,}{x}{=}{1.414213562}\right]$ (2)
 > $\mathrm{factor}\left(f\right)$
 $\left({{x}}^{{2}}{-}{2}\right){}\left({x}{-}{1}\right){}\left({x}{+}{1}\right)$ (3)
 > $\mathrm{Isolate}\left(f,\mathrm{digits}=30\right)$
 $\left[{x}{=}{-1.41421356237309504880168872421}{,}{x}{=}{-1.}{,}{x}{=}{1.}{,}{x}{=}{1.41421356237309504880168872421}\right]$ (4)

Isolating intervals for only the nonnegative roots.

 > $\mathrm{Isolate}\left(f,\mathrm{output}=\mathrm{interval},\mathrm{domain}=\left[0,\mathrm{\infty }\right]\right)$
 $\left[{x}{=}\left[{1}{,}{1}\right]{,}{x}{=}\left[\frac{{26713738906281537970833}}{{18889465931478580854784}}{,}\frac{{427419822500504607535299}}{{302231454903657293676544}}\right]\right]$ (5)

A multivariate system.

 > $F≔\left[{x}^{2}-2,y-1\right]$
 ${F}{≔}\left[{{x}}^{{2}}{-}{2}{,}{y}{-}{1}\right]$ (6)
 > $\mathrm{Isolate}\left(F,\left[x,y\right]\right)$
 $\left[\left[{x}{=}{-1.414213562}{,}{y}{=}{1.000000000}\right]{,}\left[{x}{=}{1.414213562}{,}{y}{=}{1.000000000}\right]\right]$ (7)
 > $R≔\mathrm{Isolate}\left(F,\left[x,y\right],\mathrm{output}='\mathrm{midpoint}'\right)$
 ${R}{≔}\left[\left[{x}{=}{-}\frac{{52175271301331166243}}{{36893488147419103232}}{,}{y}{=}\frac{{73786976294838206465}}{{73786976294838206464}}\right]{,}\left[{x}{=}\frac{{52175271301331166243}}{{36893488147419103232}}{,}{y}{=}\frac{{73786976294838206465}}{{73786976294838206464}}\right]\right]$ (8)
 > $\mathrm{evalf}\left(R\right)$
 $\left[\left[{x}{=}{-1.414213562}{,}{y}{=}{1.000000000}\right]{,}\left[{x}{=}{1.414213562}{,}{y}{=}{1.000000000}\right]\right]$ (9)
 > $R≔\mathrm{Isolate}\left(F,\left[x,y\right],\mathrm{output}='\mathrm{interval}',\mathrm{method}='\mathrm{RC}'\right)$
 ${R}{≔}\left[\left[{x}{=}\left[{-}\frac{{26087635650665564425}}{{18446744073709551616}}{,}{-}\frac{{3260954456333195553}}{{2305843009213693952}}\right]{,}{y}{=}\left[{1}{,}{1}\right]\right]{,}\left[{x}{=}\left[\frac{{3260954456333195553}}{{2305843009213693952}}{,}\frac{{26087635650665564425}}{{18446744073709551616}}\right]{,}{y}{=}\left[{1}{,}{1}\right]\right]\right]$ (10)
 > $\mathrm{evalf}\left(R\right)$
 $\left[\left[{x}{=}\left[{-1.414213562}{,}{-1.414213562}\right]{,}{y}{=}\left[{1.}{,}{1.}\right]\right]{,}\left[{x}{=}\left[{1.414213562}{,}{1.414213562}\right]{,}{y}{=}\left[{1.}{,}{1.}\right]\right]\right]$ (11)

Specify the maximum number of roots returned by using the maxroots option.

 > $R≔\mathrm{Isolate}\left(\left({x}^{2}-2\right)\left({x}^{2}-7\right),x\right)$
 ${R}{≔}\left[{x}{=}{-2.645751311}{,}{x}{=}{-1.414213562}{,}{x}{=}{1.414213562}{,}{x}{=}{2.645751311}\right]$ (12)
 > $R≔\mathrm{Isolate}\left(\left({x}^{2}-2\right)\left({x}^{2}-7\right),x,\mathrm{maxroots}=1\right)$
 ${R}{≔}\left[{x}{=}{2.645751311}\right]$ (13)

An example with ill-conditioned constraints.

 > $w≔\mathrm{expand}\left(\mathrm{mul}\left(x-i,i=1..10\right)\right):$

Slightly shift a coefficient:

 > $f≔w+{x}^{7}:$
 > $R,C≔\mathrm{Isolate}\left(f,x,\mathrm{constraints}=\left[w\right],\mathrm{digits}=10\right):$
 > $C$
 $\left[\left[{{x}}^{{10}}{-}{55}{}{{x}}^{{9}}{+}{1320}{}{{x}}^{{8}}{-}{18150}{}{{x}}^{{7}}{+}{157773}{}{{x}}^{{6}}{-}{902055}{}{{x}}^{{5}}{+}{3416930}{}{{x}}^{{4}}{-}{8409500}{}{{x}}^{{3}}{+}{12753576}{}{{x}}^{{2}}{-}{10628640}{}{x}{+}{3628800}{=}{-1.000019291}\right]{,}\left[{{x}}^{{10}}{-}{55}{}{{x}}^{{9}}{+}{1320}{}{{x}}^{{8}}{-}{18150}{}{{x}}^{{7}}{+}{157773}{}{{x}}^{{6}}{-}{902055}{}{{x}}^{{5}}{+}{3416930}{}{{x}}^{{4}}{-}{8409500}{}{{x}}^{{3}}{+}{12753576}{}{{x}}^{{2}}{-}{10628640}{}{x}{+}{3628800}{=}{-126.6073008}\right]\right]$ (14)

This agrees with higher precision results:

 > $\mathrm{Isolate}\left(f,x,\mathrm{constraints}=\left[w\right],\mathrm{digits}=20\right)$
 $\left[{x}{=}{1.0000027558065671334}{,}{x}{=}{1.9968767019889278008}\right]{,}\left[\left[{{x}}^{{10}}{-}{55}{}{{x}}^{{9}}{+}{1320}{}{{x}}^{{8}}{-}{18150}{}{{x}}^{{7}}{+}{157773}{}{{x}}^{{6}}{-}{902055}{}{{x}}^{{5}}{+}{3416930}{}{{x}}^{{4}}{-}{8409500}{}{{x}}^{{3}}{+}{12753576}{}{{x}}^{{2}}{-}{10628640}{}{x}{+}{3628800}{=}{-1.0000192908054545330}\right]{,}\left[{{x}}^{{10}}{-}{55}{}{{x}}^{{9}}{+}{1320}{}{{x}}^{{8}}{-}{18150}{}{{x}}^{{7}}{+}{157773}{}{{x}}^{{6}}{-}{902055}{}{{x}}^{{5}}{+}{3416930}{}{{x}}^{{4}}{-}{8409500}{}{{x}}^{{3}}{+}{12753576}{}{{x}}^{{2}}{-}{10628640}{}{x}{+}{3628800}{=}{-126.60730080931688758}\right]\right]$ (15)

Compare this result to direct evaluation:

 > $\mathrm{map2}\left(\mathrm{evalf}\left[20\right]@\mathrm{eval},w,R\right)$
 $\left[{-1.000}{,}{-126.605}\right]$ (16)

Isolate can find roots of polynomials with irrational real coefficients as well.

 > $R≔\mathrm{Isolate}\left(\mathrm{\pi }{x}^{2}-\mathrm{exp}\left(2\right)x+\mathrm{sqrt}\left(2\right)\right)$
 ${R}{≔}\left[{x}{=}{0.2101740008}{,}{x}{=}{2.141835605}\right]$ (17)

In case of multiple or near-multiple roots, this is infeasible in general; in the following example, without symbolic simplification, a purely numerical routine cannot infer the fact that there is a double root at $\sqrt{2}$:

 > $R≔\mathrm{Isolate}\left(\left({x}^{2}-2\right)\left(x-\mathrm{sqrt}\left(2\right)\right)\right)$
 ${R}{≔}\left[{x}{=}{-1.414213562}\right]$ (18)

Inspecting the partial results will reveal such instances:

 > $R,\mathrm{partial}≔\mathrm{Isolate}\left(\left({x}^{2}-2\right)\left(x-\mathrm{sqrt}\left(2\right)\right),\mathrm{partialresults}=\mathrm{true}\right)$
 ${R}{,}{\mathrm{partial}}{≔}\left[{x}{=}{-1.414213562}\right]{,}\left[{\mathrm{Record}}{}\left({\mathrm{interval}}{=}\left[\frac{{101904826760412361}}{{72057594037927936}}{,}\frac{{1630477228166597777}}{{1152921504606846976}}\right]{,}{\mathrm{multiplicity}}{=}{0}{..}{2}\right)\right]$ (19)

If it is a priori known that the input is indeed square-free, increasing the maximum precision allows to resolve such situations:

 > $a≔\mathrm{evalf}\left[100\right]\left(\mathrm{sqrt}\left(2\right)\right):$

Not that $a$ is very close to $\sqrt{2}$, but not identical.

 > $\mathrm{isolating},\mathrm{unfinished}≔\mathrm{Isolate}\left(\left(x-\mathrm{sqrt}\left(2\right)\right)\left(x-a\right),\mathrm{partialresults}=\mathrm{true}\right):$
 > $\mathrm{nops}\left(\mathrm{isolating}\right),\mathrm{nops}\left(\mathrm{unfinished}\right)$
 ${0}{,}{1}$ (20)
 > $\mathrm{isolating},\mathrm{unfinished}≔\mathrm{Isolate}\left(\left(x-\mathrm{sqrt}\left(2\right)\right)\left(x-a\right),\mathrm{maxprec}=1000,\mathrm{partialresults}=\mathrm{true}\right):$
 > $\mathrm{nops}\left(\mathrm{isolating}\right),\mathrm{nops}\left(\mathrm{unfinished}\right)$
 ${2}{,}{0}$ (21)

Note that the polynomial $\left({x}^{2}-2\right)\left(x-a\right)$ has no irrational coefficients, but only such of type numeric (which comprises floats); thus, the following call defaults to complete isolation:

 > $\mathrm{isolating},\mathrm{unfinished}≔\mathrm{Isolate}\left(\left({x}^{2}-2\right)\left(x-a\right),\mathrm{partialresults}=\mathrm{true}\right):$
 > $\mathrm{nops}\left(\mathrm{isolating}\right),\mathrm{nops}\left(\mathrm{unfinished}\right)$
 ${3}{,}{0}$ (22)

The maxprec mechanism can also be used to limit the computational resources if an incomplete or approximate answer is acceptable. The following polynomial has two well-separated simple roots of absolute value close to $110$, but also two simple roots extremely close to ${10}^{-100}$. For the latter two, approximately 50000 digits of accuracy are required to distinguish them:

 > $\mathrm{isolating},\mathrm{unfinished}≔\mathrm{Isolate}\left({x}^{100}-{\left({10}^{100}x-1\right)}^{2},\mathrm{maxprec}=100,\mathrm{partialresults}=\mathrm{true}\right):$
 > $\mathrm{isolating}$
 $\left[{x}{=}{-109.8541142}{,}{x}{=}{109.8541142}\right]$ (23)
 > $\mathrm{evalf}\left[30\right]\left(\mathrm{unfinished}\left[1\right]\left['\mathrm{interval}'\right]\right)$
 $\left[{1.00000000000000000000000000000}{×}{{10}}^{{-100}}{,}{1.00000000000000000000000000000}{×}{{10}}^{{-100}}\right]$ (24)

Despite the fact that it is feasible to fully isolate the roots in this example, such partial results might be sufficient for numerical applications.

Complex roots for univariate polynomials. Both real and complex (numeric) coefficients are supported.

 > $\mathrm{Isolate}\left({x}^{6}-1,x\right)$
 $\left[{x}{=}{-1.}{,}{x}{=}{1.}\right]$ (25)
 > $\mathrm{Isolate}\left({x}^{6}-1,x,'\mathrm{complex}'\right)$
 $\left[{x}{=}{-1.}{,}{x}{=}{1.}{,}{x}{=}{0.5000000000}{+}{0.8660254038}{}{I}{,}{x}{=}{0.5000000000}{-}{0.8660254038}{}{I}{,}{x}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{x}{=}{-0.5000000000}{-}{0.8660254038}{}{I}\right]$ (26)
 > $\mathrm{Isolate}\left({x}^{2}-I,x,'\mathrm{complex}'\right)$
 $\left[{x}{=}{0.7071067812}{+}{0.7071067812}{}{I}{,}{x}{=}{-0.7071067812}{-}{0.7071067812}{}{I}\right]$ (27)

Instead of complex, method=HR or method=PW may be specified in order to request a specific complex solver. If the domain option is not used, then generally method=PW is more efficient, and it is the default in that case when only complex is specified without a method.

 > $\mathrm{Isolate}\left({x}^{6}-1,x,'\mathrm{method}=\mathrm{HR}'\right)$
 $\left[{x}{=}{-1.}{,}{x}{=}{1.}{,}{x}{=}{0.5000000000}{+}{0.8660254038}{}{I}{,}{x}{=}{0.5000000000}{-}{0.8660254038}{}{I}{,}{x}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{x}{=}{-0.5000000000}{-}{0.8660254038}{}{I}\right]$ (28)
 > $\mathrm{Isolate}\left({x}^{2}-I,x,'\mathrm{method}=\mathrm{PW}'\right)$
 $\left[{x}{=}{0.7071067812}{+}{0.7071067812}{}{I}{,}{x}{=}{-0.7071067812}{-}{0.7071067812}{}{I}\right]$ (29)

Output the isolating boxes. For each box, the first complex number is the lower left corner, and the second one is the upper right corner.

 > $\mathrm{Isolate}\left({x}^{2}-I,x,'\mathrm{complex}','\mathrm{output}=\mathrm{interval}'\right)$
 $\left[{x}{=}\left[\frac{{854839645001008256604305}}{{1208925819614629174706176}}{+}\frac{{854839645001008256604305}{}{I}}{{1208925819614629174706176}}{,}\frac{{854839645001010290403183}}{{1208925819614629174706176}}{+}\frac{{854839645001010290403183}{}{I}}{{1208925819614629174706176}}\right]{,}{x}{=}\left[{-}\frac{{854839645001010290403183}}{{1208925819614629174706176}}{-}\frac{{854839645001010290403183}{}{I}}{{1208925819614629174706176}}{,}{-}\frac{{854839645001008256604305}}{{1208925819614629174706176}}{-}\frac{{854839645001008256604305}{}{I}}{{1208925819614629174706176}}\right]\right]$ (30)

If the input polynomial has only real coefficients, then the output boxes for all of its real roots will always have zero imaginary parts.

 > $\mathrm{Isolate}\left({x}^{4}-1,x,'\mathrm{complex}'\right)$
 $\left[{x}{=}{-1.}{,}{x}{=}{1.}{,}{x}{=}{I}{,}{x}{=}{-I}\right]$ (31)
 > $\mathrm{Isolate}\left({x}^{4}-1,x,'\mathrm{complex}','\mathrm{output}=\mathrm{interval}'\right)$
 $\left[{x}{=}\left[{-1}{,}{-1}\right]{,}{x}{=}\left[{1}{,}{1}\right]{,}{x}{=}\left[{I}{,}{I}\right]{,}{x}{=}\left[{-I}{,}{-I}\right]\right]$ (32)

If the input polynomial does not have real coefficients but has real roots, then the isolating boxes for the real roots will in general still have (small) nonzero imaginary parts.

 > $\mathrm{Isolate}\left(\mathrm{expand}\left(\left({x}^{2}-2\right)\left(x-I\right)\right),x,'\mathrm{complex}'\right)$
 $\left[{x}{=}{I}{,}{x}{=}{1.414213562}{-}{2.736911063}{×}{{10}}^{{-46}}{}{I}{,}{x}{=}{-1.414213562}{-}{6.679151101}{×}{{10}}^{{-34}}{}{I}\right]$ (33)
 > $\mathrm{Isolate}\left(\mathrm{expand}\left(\left({x}^{2}-2\right)\left(x-I\right)\right),x,'\mathrm{complex}','\mathrm{output}=\mathrm{interval}'\right)$
 $\left[{x}{=}\left[{-}\frac{{125361639}}{{151115727451828646838272}}{+}\frac{{151115727451828521476633}{}{I}}{{151115727451828646838272}}{,}\frac{{125361639}}{{151115727451828646838272}}{+}\frac{{151115727451828772199911}{}{I}}{{151115727451828646838272}}\right]{,}{x}{=}\left[\frac{{213709911250251657417421}}{{151115727451828646838272}}{-}\frac{{399524907238821585794734825144345}{}{I}}{{91343852333181432387730302044767688728495783936}}{,}\frac{{213709911250252979334451}}{{151115727451828646838272}}{+}\frac{{399524907238821585794734825144295}{}{I}}{{91343852333181432387730302044767688728495783936}}\right]{,}{x}{=}\left[{-}\frac{{213709911250252979334451}}{{151115727451828646838272}}{-}\frac{{799049814477643171711489528659011}{}{I}}{{182687704666362864775460604089535377456991567872}}{,}{-}\frac{{213709911250251657417421}}{{151115727451828646838272}}{+}\frac{{799049814477643171467449771918269}{}{I}}{{182687704666362864775460604089535377456991567872}}\right]\right]$ (34)

Limit the search to nonnegative real and imaginary parts.

 > $\mathrm{Isolate}\left({x}^{6}-1,x,'\mathrm{complex}','\mathrm{domain}'=\left[0,\mathrm{\infty }+I\mathrm{\infty }\right]\right)$
 $\left[{x}{=}{1.}{,}{x}{=}{0.5000000000}{+}{0.8660254038}{}{I}\right]$ (35)

Only imaginary roots.

 > $\mathrm{Isolate}\left({x}^{8}-3{x}^{4}+1,x,'\mathrm{complex}','\mathrm{domain}'=\left[-I\mathrm{\infty },I\mathrm{\infty }\right]\right)$
 $\left[{x}{=}{-}{0.7861513778}{}{I}{,}{x}{=}{1.272019650}{}{I}{,}{x}{=}{-}{1.272019650}{}{I}{,}{x}{=}{0.7861513778}{}{I}\right]$ (36)

Limit the number of roots computed.

 > $f≔{x}^{16}-65025{x}^{2}+510x-1$
 ${f}{≔}{{x}}^{{16}}{-}{65025}{}{{x}}^{{2}}{+}{510}{}{x}{-}{1}$ (37)
 > $\mathrm{Isolate}\left(f,x,'\mathrm{complex}','\mathrm{maxroots}'=6\right)$
 $\left[{x}{=}{2.206383923}{,}{x}{=}{0.4905310497}{+}{2.151612560}{}{I}{,}{x}{=}{0.4905310497}{-}{2.151612560}{}{I}{,}{x}{=}{1.987827746}{+}{0.9575576732}{}{I}{,}{x}{=}{1.987827746}{-}{0.9575576732}{}{I}{,}{x}{=}{1.375446946}{+}{1.725459305}{}{I}\right]$ (38)

In the above example, there are two very close roots near the origin. By default, Isolate always tries to isolate all the roots, and internally keeps increasing the precision until that is possible. Using the maxprec option, one can limit that precision, and as a result, not all roots may be found.

 > $\mathrm{Isolate}\left(f,x,'\mathrm{complex}','\mathrm{digits}'=10,'\mathrm{maxprec}'=10\right)$
 $\left[{x}{=}{-2.207504373}{,}{x}{=}{2.206383923}{,}{x}{=}{1.987827746}{+}{0.9575576732}{}{I}{,}{x}{=}{1.987827746}{-}{0.9575576732}{}{I}{,}{x}{=}{0.4905310497}{+}{2.151612560}{}{I}{,}{x}{=}{0.4905310497}{-}{2.151612560}{}{I}{,}{x}{=}{-0.4916514963}{+}{2.151612559}{}{I}{,}{x}{=}{-0.4916514963}{-}{2.151612559}{}{I}{,}{x}{=}{-1.988948195}{+}{0.9575576718}{}{I}{,}{x}{=}{-1.988948195}{-}{0.9575576718}{}{I}{,}{x}{=}{1.375446946}{+}{1.725459305}{}{I}{,}{x}{=}{1.375446946}{-}{1.725459305}{}{I}{,}{x}{=}{-1.376567393}{+}{1.725459303}{}{I}{,}{x}{=}{-1.376567393}{-}{1.725459303}{}{I}\right]$ (39)

Using the partialresults option, Isolate also returns the clusters of roots that could not be isolated.

 > $\mathrm{Isolate}\left(f,x,'\mathrm{complex}','\mathrm{digits}'=10,'\mathrm{maxprec}'=10,'\mathrm{partialresults}'\right)$
 $\left[{x}{=}{-2.207504373}{,}{x}{=}{2.206383923}{,}{x}{=}{1.987827746}{+}{0.9575576732}{}{I}{,}{x}{=}{1.987827746}{-}{0.9575576732}{}{I}{,}{x}{=}{0.4905310497}{+}{2.151612560}{}{I}{,}{x}{=}{0.4905310497}{-}{2.151612560}{}{I}{,}{x}{=}{-0.4916514963}{+}{2.151612559}{}{I}{,}{x}{=}{-0.4916514963}{-}{2.151612559}{}{I}{,}{x}{=}{-1.988948195}{+}{0.9575576718}{}{I}{,}{x}{=}{-1.988948195}{-}{0.9575576718}{}{I}{,}{x}{=}{1.375446946}{+}{1.725459305}{}{I}{,}{x}{=}{1.375446946}{-}{1.725459305}{}{I}{,}{x}{=}{-1.376567393}{+}{1.725459303}{}{I}{,}{x}{=}{-1.376567393}{-}{1.725459303}{}{I}\right]{,}\left[{\mathrm{Record}}{}\left({\mathrm{interval}}{=}\left[\frac{{1103823438081}}{{281474976710656}}{-}\frac{{I}}{{36028797018963968}}{,}\frac{{70644700037185}}{{18014398509481984}}{+}\frac{{I}}{{36028797018963968}}\right]{,}{\mathrm{multiplicity}}{=}{2}{..}{2}\right)\right]$ (40)

We can increase maxprec and digits sufficiently to isolate all roots.

 > $\mathrm{Isolate}\left(f,x,'\mathrm{complex}','\mathrm{digits}'=25,'\mathrm{maxprec}'=25,'\mathrm{partialresults}'\right)$
 $\left[{x}{=}{1.375446945551779641864712}{+}{1.725459305149751407406670}{}{I}{,}{x}{=}{1.375446945551779641864712}{-}{1.725459305149751407406670}{}{I}{,}{x}{=}{-1.376567393345465779959392}{+}{1.725459303460417547940936}{}{I}{,}{x}{=}{-1.376567393345465779959392}{-}{1.725459303460417547940936}{}{I}{,}{x}{=}{-1.988948195028652851974813}{+}{0.9575576718336940068757207}{}{I}{,}{x}{=}{-1.988948195028652851974813}{-}{0.9575576718336940068757207}{}{I}{,}{x}{=}{-0.4916514962757859876144393}{+}{2.151612559134999495972727}{}{I}{,}{x}{=}{-0.4916514962757859876144393}{-}{2.151612559134999495972727}{}{I}{,}{x}{=}{0.4905310496576921502540973}{+}{2.151612559886820176866561}{}{I}{,}{x}{=}{0.4905310496576921502540973}{-}{2.151612559886820176866561}{}{I}{,}{x}{=}{1.987827745769011252162110}{+}{0.9575576731884427011111223}{}{I}{,}{x}{=}{1.987827745769011252162110}{-}{0.9575576731884427011111223}{}{I}{,}{x}{=}{2.206383922877867415056704}{,}{x}{=}{-2.207504372789926225305570}{,}{x}{=}{0.003921568627450980392376213}{,}{x}{=}{0.003921568627450980391937512}\right]{,}\left[\right]$ (41)

If there is an exact double root, then it will be listed only once by default.

 > $g≔\mathrm{expand}\left(\left({x}^{2}-2\right){\left(3x-I\right)}^{2}\right)$
 ${g}{≔}{9}{}{{x}}^{{4}}{-}{19}{}{{x}}^{{2}}{-}{6}{}{I}{}{{x}}^{{3}}{+}{12}{}{I}{}{x}{+}{2}$ (42)
 > $\mathrm{Isolate}\left(g,x,'\mathrm{complex}'\right)$
 $\left[{x}{=}{0.3333333333}{}{I}{,}{x}{=}{1.414213562}{+}{1.233581138}{×}{{10}}^{{-17}}{}{I}{,}{x}{=}{-1.414213562}{+}{1.233581138}{×}{{10}}^{{-17}}{}{I}\right]$ (43)

No matter how high the value of the maxprec option, the double root is only accessible via partialresults.

 > $\mathrm{Isolate}\left(g,x,'\mathrm{complex}','\mathrm{maxprec}'=100\right)$
 $\left[{x}{=}{-1.414213562}{-}{3.189827476}{×}{{10}}^{{-16}}{}{I}{,}{x}{=}{1.414213562}{-}{3.189827476}{×}{{10}}^{{-16}}{}{I}\right]$ (44)
 > $\mathrm{Isolate}\left(g,x,'\mathrm{complex}','\mathrm{maxprec}'=100,'\mathrm{partialresults}'\right)$
 $\left[{x}{=}{-1.414213562}{-}{3.189827476}{×}{{10}}^{{-16}}{}{I}{,}{x}{=}{1.414213562}{-}{3.189827476}{×}{{10}}^{{-16}}{}{I}\right]{,}\left[{\mathrm{Record}}{}\left({\mathrm{interval}}{=}\left[{-}\frac{{1}}{{1125899906842624}}{+}\frac{{93824992236885}{}{I}}{{281474976710656}}{,}\frac{{1}}{{1125899906842624}}{+}\frac{{187649984473771}{}{I}}{{562949953421312}}\right]{,}{\mathrm{multiplicity}}{=}{2}{..}{2}\right)\right]$ (45)

A multivariate system.

 > $\mathrm{Isolate}\left(\left[x+y+z,xy+yz+zx,xyz-1\right],\left[x,y,z\right]\right)$
 $\left[\right]$ (46)
 > $\mathrm{map}\left(\mathrm{print},\mathrm{Isolate}\left(\left[x+y+z,xy+yz+zx,xyz-1\right],\left[x,y,z\right],'\mathrm{complex}'\right)\right):$
 $\left[{x}{=}{-0.5000000000}{-}{0.8660254038}{}{I}{,}{y}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{z}{=}{1.}\right]$
 $\left[{x}{=}{-0.5000000000}{-}{0.8660254038}{}{I}{,}{y}{=}{1.}{,}{z}{=}{-0.5000000000}{+}{0.8660254038}{}{I}\right]$
 $\left[{x}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{y}{=}{-0.5000000000}{-}{0.8660254038}{}{I}{,}{z}{=}{1.}\right]$
 $\left[{x}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{y}{=}{1.}{,}{z}{=}{-0.5000000000}{-}{0.8660254038}{}{I}\right]$
 $\left[{x}{=}{1.}{,}{y}{=}{-0.5000000000}{-}{0.8660254038}{}{I}{,}{z}{=}{-0.5000000000}{+}{0.8660254038}{}{I}\right]$
 $\left[{x}{=}{1.}{,}{y}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{z}{=}{-0.5000000000}{-}{0.8660254038}{}{I}\right]$ (47)
 > $\mathrm{map}\left(\mathrm{print},\mathrm{Isolate}\left(\left[x+y+z,xy+yz+zx,xyz-1\right],\left[x,y,z\right],'\mathrm{complex}','\mathrm{makereal}=\mathrm{false}'\right)\right):$
 $\left[{x}{=}{-0.5000000000}{-}{0.8660254038}{}{I}{,}{y}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{z}{=}{1.000000000}{-}{2.528799864}{×}{{10}}^{{-26}}{}{I}\right]$
 $\left[{x}{=}{-0.5000000000}{-}{0.8660254038}{}{I}{,}{y}{=}{1.000000000}{+}{1.152625820}{×}{{10}}^{{-25}}{}{I}{,}{z}{=}{-0.5000000000}{+}{0.8660254038}{}{I}\right]$
 $\left[{x}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{y}{=}{-0.5000000000}{-}{0.8660254038}{}{I}{,}{z}{=}{1.000000000}{+}{2.528799864}{×}{{10}}^{{-26}}{}{I}\right]$
 $\left[{x}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{y}{=}{1.000000000}{-}{1.152625820}{×}{{10}}^{{-25}}{}{I}{,}{z}{=}{-0.5000000000}{-}{0.8660254038}{}{I}\right]$
 $\left[{x}{=}{1.000000000}{+}{5.574280276}{×}{{10}}^{{-26}}{}{I}{,}{y}{=}{-0.5000000000}{-}{0.8660254038}{}{I}{,}{z}{=}{-0.5000000000}{+}{0.8660254038}{}{I}\right]$
 $\left[{x}{=}{1.000000000}{-}{5.574280276}{×}{{10}}^{{-26}}{}{I}{,}{y}{=}{-0.5000000000}{+}{0.8660254038}{}{I}{,}{z}{=}{-0.5000000000}{-}{0.8660254038}{}{I}\right]$ (48)

The coefficients of the input system may contain $I$.

 > $\mathrm{Isolate}\left(\left[{x}^{2}-2I,Ixy-{x}^{2}+2\right],\left[x,y\right],'\mathrm{complex}'\right)$
 $\left[\left[{x}{=}{-1.}{-}{I}{,}{y}{=}{-2.}\right]{,}\left[{x}{=}{1.}{+}{I}{,}{y}{=}{2.}\right]\right]$ (49)

Finally, we consider a harder multivariate system with infinitely many complex solutions. The input is given as a PolynomialIdeal so that the Groebner basis computed by Isolate is remembered.

 > $\mathrm{with}\left(\mathrm{PolynomialIdeals}\right):$
 > $J≔⟨53yz-28y{x}^{2}+5{y}^{2}{x}^{2}z+13{y}^{4}z,83{y}^{2}z+9{x}^{2}{z}^{2}-60{y}^{2}{x}^{2}z-83{y}^{4}z,62xy+37{y}^{3}+5z{x}^{3}+96{y}^{4}z⟩:$
 > $\mathrm{Isolate}\left(J,\left[x,y,z\right]\right)$

The basis is remembered:

 > $\mathrm{IdealInfo}:-\mathrm{KnownGroebnerBases}\left(J\right)$
 $\left\{{\mathrm{tdeg}}{}\left({z}{,}{x}{,}{y}\right)\right\}$ (50)
 > $J≔⟨53yz-28y{x}^{2}+5{y}^{2}{x}^{2}z+13{y}^{4}z,83{y}^{2}z+9{x}^{2}{z}^{2}-60{y}^{2}{x}^{2}z-83{y}^{4}z,62xy+37{y}^{3}+5z{x}^{3}+96{y}^{4}z⟩:$
 > $\mathrm{Isolate}\left(J,\left[x,y,z\right],\mathrm{method}='\mathrm{RC}'\right)$

References

 Rouillier, F. "Solving zero-dimensional systems through the rational univariate representation." Journal of Applicable Algebra in Engineering, Communication, and Computing, Vol. 9, No. 5 (1999): 433-461.
 Rouillier, F. and Zimmermann, P. "Efficient isolation of polynomial real roots." Journal of Computational and Applied Mathematics, Vol. 162 No. 1 (2003): 33-50.
 Aubry, P., Lazard, D., and Moreno Maza, M. "On the theories of triangular sets." J. of Symb. Comput., Vol. 28, No. 1-2 (1999): 105-124.
 Xia, B. and Yang, L. "An Algorithm for Isolating the Real Solutions of Semi-algebraic Systems." J. of Symb. Comput. , Vol. 34, No. 5 (2002): 461-477.
 Kobel, A. and Sagraloff, M. and Rouillier, F. "Computing Real Roots of Real Polynomials ... And now For Real!" Proceedings of the 41st International Symposium on Symbolic and Algebraic Computation (ISSAC) (2016): 303-310.
 Moroz, G. "New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems". Proceedings of the IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (2022): 1090-1099.
 Imbach, R. and Moroz, G. "Fast evaluation and root finding for polynomials with floating-point coefficients", Proceedings ISSAC 2023, pp. 325–334, https://doi.org/10.1145/3597066.3597112
 Baker Kearfott, R. Rigorous global search: continuous problems. Nonconvex optimization and its applications (NOIA) Vol. 13, Kluwer Academic Publishers, Dordrecht, Boston, (1996).
 Becker, Ruben, et al. "Complexity analysis of root clustering for a complex polynomial." Proceedings of the 41st International Symposium on Symbolic and Algebraic Computation (ISSAC) (2016).

Compatibility

 • Support for complex solutions in the multivariate case was added in Maple 2024. The method=PW and makereal options were added and the default behavior for the complex option changed. The domain option is now also supported for methods ABND and PW in the univariate case.
 • The maxroots option was introduced in Maple 15.