Abstract: Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schoenhage in 1982. The main drawbacks of Pan's method are that it is quite involved and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted ANEWDSC, which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. ANEWDSC can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task.
Recommendations
Cites work
- scientific article; zbMATH DE number 52177 (Why is no real title available?)
- scientific article; zbMATH DE number 1253988 (Why is no real title available?)
- scientific article; zbMATH DE number 1446863 (Why is no real title available?)
- scientific article; zbMATH DE number 3251532 (Why is no real title available?)
- A 2002 update of the supplementary bibliography on roots of polynomials
- A comparative study of two real root isolation methods
- A fast numerical algorithm for the composition of power series with complex coefficients
- A near-optimal algorithm for computing real roots of sparse polynomials
- A new proof of Vincent's theorem
- A simple but exact and efficient algorithm for complex root isolation
- Almost tight recursion tree bounds for the Descartes method
- Amortized bound for root isolation via Sturm sequences
- An iterated eigenvalue algorithm for approximating roots of univariate polynomials
- Complexity of real root isolation using continued fractions
- Computer Algebra in Scientific Computing
- Continued fraction real root isolation using the Hong root bound
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Efficient isolation of polynomial's real roots.
- Finding a cluster of zeros of univariate polynomials
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- Numerical methods for roots of polynomials. II
- Numerical methods for roots of polynomials. Part I
- On the complexity of computing with planar algebraic curves
- On the complexity of real root isolation using continued fractions
- On the complexity of the Descartes method when using approximate arithmetic
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Quadratic interval refinement for real roots
- Root refinement for real polynomials using quadratic interval refinement
- Solving a Polynomial Equation: Some History and Recent Progress
- SqFreeEVAL: An (almost) optimal real-root isolation algorithm
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- When Newton meets Descartes
- Zeros of polynomials. Translated from the Bulgarian
Cited in
(35)- Zero counting for a class of univariate Pfaffian functions
- Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
- Root radii and subdivision for polynomial root-finding
- Accelerated subdivision for clustering roots of polynomials given by evaluation oracles
- How to count the number of zeros that a polynomial has on the unit circle?
- Computation of dominant real roots of polynomials
- Solving bivariate systems using rational univariate representations
- A new trigonometrical algorithm for computing real root of non-linear transcendental equations
- Computing real roots of a polynomial in Chebyshev series form through subdivision with linear testing and cubic solves
- Representing rational curve segments and surface patches using semi-algebraic sets
- scientific article; zbMATH DE number 3220762 (Why is no real title available?)
- A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
- Algorithms and Computation
- Near optimal subdivision algorithms for real root isolation
- Real polynomial root-finding by means of matrix and polynomial iterations
- A New Root–Finding Algorithm Using Exponential Series
- Minimizing cubic and homogeneous polynomials over integers in the plane
- Computing Real Roots of Real Polynomials ... and now For Real!
- Computing real radicals and \(S\)-radicals of polynomial systems
- Condition numbers for the cube. I: Univariate polynomials and hypersurfaces
- scientific article; zbMATH DE number 1253988 (Why is no real title available?)
- On the complexity of the Descartes method when using approximate arithmetic
- Affine Loop Invariant Generation via Matrix Algebra
- Real and complex polynomial root-finding with eigen-solving and preprocessing
- Efficient isolation of polynomial's real roots.
- msolve. A library for solving polynomial systems
- Novel range functions via Taylor expansions and recursive Lagrange interpolation with application to real root isolation
- New Practical Advances in Polynomial Root Clustering
- Positive root isolation for poly-powers by exclusion and differentiation
- New algorithms for computing a root of non-linear equations using exponential series
- Bounds for polynomials on algebraic numbers and application to curve topology
- From approximate factorization to root isolation
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- First study for ramp secret sharing schemes through greatest common divisor of polynomials
- Computing Chebyshev knot diagrams
This page was built for publication: Computing real roots of real polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491245)
