Description 

• The RootFinding:-Isolate command can now be used to isolate the roots of univariate polynomials with arbitrary real coefficients.

Isolating roots of univariate polynomials with real coefficients 

• Prior to 2019, RootFinding:-Isolate could only determine the roots of polynomials with rational or float coefficients. This restriction is now lifted for univariate polynomials:

• In particular, Isolate can now be used to find roots of polynomials with algebraic coefficients. We illustrate this in an example where we manually study the real solutions of a bivariate equation system of the form :

• The common roots of both polynomials are the intersections of their corresponding algebraic curves:

• Elimination theory for algebraic equation systems tells us that all x-coordinates of the common solutions are roots of the resultant polynomial of and with respect to :

• This resultant is a univariate polynomial with irrational roots, some of which may be complex. The roots are candidate values for the x-coordinate of simultaneous solutions. Note that we store symbolic expressions for the solutions, not just approximations:

• However, some of the candidates might be spurious. We can use the new interface for RootFinding:-Isolate to determine the roots along the fibers of and when we substitute the candidates:

• Indeed, there is a common solution close to , :

• However, let's look at the candidate at :

• This clearly is a spurious candidate; the roots of and are distinct.

• The example code above can help to filter spurious solutions, but it is not a complete solver for bivariate systems; it allows to filter out suspicious candidates, but does not validate all solutions. Such verification is provided by the multivariate solvers in the RootFinding package:

• However, the multivariate polynomial solver requires coefficients of type numeric (that is, rationals or floats). Consider the case where we slightly change by replacing with in the last term:

• The more naive approach above, while uncertified, will work nevertheless:

• Finally, we show how the combination of the constraints and output options of RootFinding:-Isolate can provide certified information, and will allow us to programmatically exclude spurious candidates even with irrational coefficients.

• Indeed, evaluated over all isolating intervals for does not contain zero, which confirms that and have no common zero at . In contrast,

• shows that , evaluated at the isolating intervals for the root of , contains zero. This still does not validate the simultaneous zero of both systems, but is a strong hint. Techniques along these lines can serve to filter candidates numerically before trying time-consuming symbolic simplification and zero-testing, and can be used as cornerstones for complete solvers.

• Note that the aforementioned routines crucially rely on inputs that are served as symbolic expressions rather than approximations:

• Even a tiny perturbation of the candidate solution in will produce distinct roots of and in . Thus, the direct handling of arbitrary real coefficients is not only convenient, but required for correctness.

Performance improvements for root isolation and root refinement 

• The new default algorithm of Isolate also features vastly improved performance for ill-conditioned polynomials with clustered roots. The root finding method eventually converges quadratically to regions containing roots, rather than just linearly. For example, the following class of polynomials has a cluster of roots extremely close to :

• The same technique allows even more dramatic improvements for root finding requests with high accuracy even on well-conditioned problems: