Source-linked AI summary
Root isolation for analytic functions using cubic hermite interpolation
Christophe Raffalli
TL;DR
Root isolation seeks intervals that each contain exactly one real root and collectively cover every real root. This paper uses recursive subdivision and a local Hermite comparison, with experiments suggesting linear behavior for certain polynomial families. The authors leave exact or probabilistic algorithms as future work.
Problem
Root isolation seeks disjoint intervals that each contain exactly one real root and together cover every real root; traditional decision tests typically have O(d^2) complexity.
Source: §1 · p. 1Method
The algorithm recursively subdivides intervals and uses a numerical comparison with a local Hermite interpolant instead of symbolic root-counting tests.
Source: §1 · p. 1, Hermite interpolation predicate · p. 5Results
The algorithm is proved to terminate with intervals containing at least one root, and experiments suggest it appears linear for Chebyshev or Mignotte polynomials.
Source: §1 · p. 2Takeaways & Limitations
For special polynomial families, the test can use O(1)-cost evaluations and the resulting algorithm appears linear in experiments.
Source: §1 · p. 2Whether an exact algorithm is possible remains unknown, and the no-missed-roots claim for analytic functions without multiple roots is conjectural.
Source: §1 · p. 2, Hermite interpolation predicate · p. 5
Abstract
from arXiv · showhide
We present a root isolation algorithm for an analytic function. The method combines interval subdivision with a heuristic test based on local cubic Hermite interpolation. Whenever the function is sufficiently close to its cubic Hermite interpolant at a few sample points, we assume that the critical points of the cubic interpolant give a valid root isolation for the original function. Such an algorithm cannot, in general, provide a rigorous certification of the computed intervals. Nevertheless, extensive numerical experiments show that it is highly efficient and almost always produces the correct results. We hope that a probabilistic or exact algorithm can be derived from this work.
1. Introduction
Root isolation seeks disjoint intervals each containing exactly one real root and covering all roots; this paper replaces symbolic tests with local Hermite comparison for analytic functions.
1. Introduction
- The test replaces symbolic root-counting with local Hermite comparison, avoids polynomial expansion, and supports standard precision, including 32-bit GPU visualization experiments.The paper reports improved practical numerical stability from not expanding polynomials.Source: §1 · pp. 1–2
- Classical decision tests typically cost O(d^2), while general-function isolation has less prior work; earlier local interpolation used Chebyshev or Taylor rather than fixed cubic Hermite.For moderate degrees, FFT-based methods are usually not advantageous in practice.Source: §1 · p. 1
- The interpolation test has cost proportional to a few function and derivative evaluations, and the algorithm appears linear in experiments for Chebyshev or Mignotte polynomials.Direct polynomial evaluation generally costs O(d), while evaluation for these special families can cost O(1).Source: §1 · p. 2
- The algorithm is proved to terminate and produce intervals containing at least one root; experiments suggest n = 3 or 6 suffices for many function families.The parameters are ε ∈ ]0, 1[ and n, the number of interpolation-quality test points.Source: §1 · p. 2
- The authors hope the approach can lead to an exact or probabilistic algorithm.The current work presents numerical root isolation rather than such an algorithm.Source: §1 · p. 2
2. Description of the Algorithm
The algorithm uses cubic Hermite interpolation and a sampled quality test to guide interval subdivision. It terminates and returns intervals containing roots when the analytic function has no multiple roots, but whether it misses roots remains conjectural.
Hermite interpolation predicate.
- The method constructs a cubic Hermite interpolant from endpoint values and derivatives, then uses its critical points and n regularly spaced points to test interpolation quality Q.The test points are the real roots of h′ inside the interval and n interior points; the paper notes that the regular spacing choice may not be optimal.Source: Hermite interpolation predicate · pp. 2, 5
- Intervals that fail the (ε, n)-goodness test are subdivided at the tested point with the largest Q; intervals that pass use sign changes of h to return up to three root-containing subintervals.At tested critical points, Q < 1 implies that f and h have the same sign, supporting the lower bound of one root of f in each returned interval.Source: Hermite interpolation predicate · p. 5
- Newton steps for improving performance on clustered roots, as in Mignotte polynomials, were not tested.Source: Hermite interpolation predicate · p. 5
- For analytic functions without multiple roots, the algorithm terminates and returns intervals each containing at least one root, for any ε ∈]0, 1[ and n ∈N∗.This guarantee does not establish that every root is found.Source: Hermite interpolation predicate · p. 5
- Termination follows because sufficiently small intervals become (ε, n)-good, while tested critical-point subdivisions stay a positive distance from either endpoint.The latter bound prevents intervals from shrinking arbitrarily slowly when subdivision occurs at a root of h′.Source: Hermite interpolation predicate · pp. 4–5
- The conjectured completeness claim is unresolved: suitable ε and n may make missed roots rare, but the authors do not know whether an exact algorithm is possible.They report that small parameter values appear sufficient across many polynomial families, independent of degree and interval size.Source: Hermite interpolation predicate · p. 5
3. Experimental Results
The classical-polynomial experiments report consistent speed advantages over Pari/GP and RS, alongside family-specific subdivision behavior. GPU visualizations remain interactive in most cases, with no observed numerical artifacts or incorrect root classifications despite single-precision arithmetic.
3.1. Software availability.
- The Julia root-isolation implementation is independently usable for reproducing the numerical experiments; the visualization code uses CamlSurf and a GLSL rewrite.Source: §3.1 · p. 6
3.2. Tests on classical polynomials.
- The method consistently outperforms Pari/GP and RS, sometimes by a large margin, using 64-bit floats and avoiding polynomial expansion for some computations.Chebyshev polynomials also use a trigonometric formulation.Source: §3.2 · p. 6
- Legendre tests show linear subdivisions but quadratic computing time, while Wilkinson polynomials require more subdivisions yet appear linear in subdivision count.Wilkinson composition with Φλ does not reduce subdivisions and requires much smaller ε.Source: §3.2 · pp. 6–7
- Mignotte tests show relatively constant subdivision counts despite roots near zero; random-root polynomials are faster because expansion would produce very large coefficients.Mignotte degrees reached about 60 for Pn,16 and 30 for Pn,32 in double precision; low-degree tests also show an early-subdivision anomaly.Source: §3.2 · p. 8
3.3. Experiments with visualization of implicit surfaces.
- Barth sextic rendering reaches 100 FPS, while the Labs heptic reaches 20 FPS; most examples exceed 30 FPS, with no observed artifacts or incorrect classifications.The experiments use single-precision arithmetic; the latest Game implementation has no bad pixels at ε = 0.15 and n = 3, even on integrated graphics.Source: Figure 7 · p. 9, §3.3 · pp. 9–10, Figure 8 · p. 10