isolate the real or complex roots of a univariate polynomial or polynomial system
Univariate polynomials with irrational real coefficients
Complex roots for univariate polynomials
Isolate(f, X, digits=d, constraints=icons, output=outpt, maxroots=mxrts, method=mthd)
Isolate(g, X, digits=d, constraints=rcons, output=outpt, maxroots=mxrts, method=ABND, maxprec=mxprc, partialresults=partial)
Isolate(h, X, digits=d, output=outpt, maxroots=mxrts, method=HR, maxprec=mxprc, partialresults=partial, domain=dom)
Isolate(h, X, digits=d, output=outpt, maxroots=mxrts, complex, maxprec=mxprc, partialresults=partial, domain=dom)
Isolate(J, X, digits=d, constraints=icons, output=outpt, maxroots=mxrts, method=mthd)
univariate polynomial with real-valued numeric coefficients
univariate polynomial with real-valued coefficients
univariate polynomial with complex(numeric) coefficients
set or list of polynomials, or a PolynomialIdeal
(optional) name or list of names; the variable(s)
(optional) positive integer; number of significant digits (default: Digits)
(optional) list of polynomials with integer coefficients
(optional) list of polynomials with real coefficients
(optional) type of output: numeric (default), midpoint, or interval
(optional) maximum number of roots to be returned. Default is ∞.
(optional) name of algorithm to use: ABND, HR, RS, or RC. Default is ABND for univariate and RS for multivariate inputs.
(optional) literal name; equivalent to method=HR
(optional) maximum internal working precision. Default is ∞ for complex(numeric) coefficients, otherwise see the description of the option below.
(optional) return regions that could not be completely decided: true or false (default).
(optional) list of two complex(extended_numeric) numbers, bounding the search domain in the complex plane
The digits=d option controls the output precision.
In the case of numeric coefficients and when the method is not HR, 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 57512500 could be represented with the interval 2.299,2.301 at digits=4. In particular, isolating intervals corresponding to a root of magnitude larger than 10d 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, 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 ABND and RS methods.
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 is silently ignored, and method=ABND is used.
The method option specifies the algorithm to use. It can be ABND (default for the univariate case), HR, RS (default for the multivariate case), or RC.
method=HR (or complex) 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 (and univariate inputs) or method=HR. If maxprec or partialresults are given and the method is not HR, then the specified method is ignored and method=ABND is used.
When method=HR, or alternatively, when the complex keyword is specified, all complex roots are computed. This method only supports a single univariate polynomial with numeric or complex(numeric) coefficients. In this case, the result is a list of isolating boxes in the complex plane, of the form r+I⁢s,u+I⁢v, where r≤u and s≤v are rational numbers. For all non-zero roots, d is the relative accuracy (i.e., the number of significant digits for both the real and the imaginary part).
For multivariate polynomial systems, when method=RS is specified, Isolate first computes a Groebner basis followed by a Rational Univariate Representation. The second argument must be an ordered list of variables, and the roots are returned as corresponding lists of values.
The maxprec option specifies the maximum internal working precision of the root solver when the method is not HR. 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 are given, then the computation will be halted if an accuracy of min⁡mxprc,d 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 in conjunction with method=ABND or method=HR (and, thus, univariate polynomials). If maxprec is specified and the method is not HR, 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 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 in conjunction with method=ABND or method=HR (and, thus, univariate polynomials). If partialresults is specified and the method is not HR, the choice of method is silently ignored and method=ABND is used.
When the domain option is specified (only supported for method=HR), then all the roots 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. ∞ or −∞ may be used in the domain boundaries, and the domain can also be a subset of the real axis or the imaginary axis.
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 are 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 and maxprec options.
Polynomials with irrational coefficients are only supported in the univariate case, and only with method=ABND or method=HR (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.
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](..).
Irrational coefficient support for univariate real polynomials is provided with method=ABND. If non-numeric coefficients are given and the method is not HR, 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 max⁡Digits,4⁢d,8⁢n⁢log2⁡n. 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 0,0 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 sub-instances will be solved according to the above rules, and the remaining non-numeric sub-instances will be subject to the maxprec heuristic.
For a single univariate polynomial h with numeric or complex(numeric) coefficients, method=HR (or, alternatively, using the complex keyword) computes isolating rectangles (boxes) for all the complex roots.
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 non-zero 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 by using the domain option; see the description of this option above.
The domain and maxroots options can be used in conjunction. If dom contains mxrts or more roots, then exactly mxrts boxes are returned. If maxprec is also used, then the counts include multiplicities.
f ≔ x4−3⁢x2+2
A multivariate system.
F ≔ x2−2,y−1
R ≔ Isolate⁡F,x,y,output='midpoint'
R ≔ Isolate⁡F,x,y,output='interval',method='RC'
Specify the maximum number of roots returned by using the maxroots option.
R ≔ Isolate⁡x2−2⁢x2−7,x
R ≔ Isolate⁡x2−2⁢x2−7,x,maxroots=1
An example with ill-conditioned constraints.
w ≔ expand⁡mul⁡x−i,i=1..10:
Slightly shift a coefficient:
f ≔ w+x7:
R,C ≔ Isolate⁡f,x,constraints=w,digits=10:
This agrees with higher precision results:
Compare this result to direct evaluation:
Isolate can find roots of polynomials with irrational real coefficients as well.
R ≔ Isolate⁡Pi⁢x2−ⅇ2⁢x+2
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 2:
R ≔ Isolate⁡x2−2⁢x−2
Inspecting the partial results will reveal such instances:
R,partial ≔ Isolate⁡x2−2⁢x−2,partialresults=true
If it is a priori known that the input is indeed square-free, increasing the maximum precision allows to resolve such situations:
a ≔ evalf100⁡2:
Not that a is very close to 2, but not identical.
isolating,unfinished ≔ Isolate⁡x−2⁢x−a,partialresults=true:
isolating,unfinished ≔ Isolate⁡x−2⁢x−a,maxprec=1000,partialresults=true:
Note that the polynomial x2−2⁢x−a has no irrational coefficients, but only such of type numeric (which comprises floats); thus, the following call defaults to complete isolation:
isolating,unfinished ≔ Isolate⁡x2−2⁢x−a,partialresults=true:
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:
isolating,unfinished ≔ Isolate⁡x100−10100⁢x−12,maxprec=100,partialresults=true:
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.