Computing real roots of real polynomials
From MaRDI portal
Publication:491245
DOI10.1016/J.JSC.2015.03.004zbMATH Open1330.65072DBLPjournals/jsc/SagraloffM16arXiv1308.4088OpenAlexW2112074285WikidataQ60303620 ScholiaQ60303620MaRDI QIDQ491245FDOQ491245
Authors: Michael Sagraloff, K. Mehlhorn 
Publication date: 24 August 2015
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1308.4088
Recommendations
complexity analysisroot findingroot isolationapproximate arithmeticcertified computationroot refinement
Numerical computation of solutions to single equations (65H05) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)
Cites Work
- SqFreeEVAL: An (almost) optimal real-root isolation algorithm
- Efficient isolation of polynomial's real roots.
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Zeros of polynomials. Translated from the Bulgarian
- Numerical methods for roots of polynomials. Part I
- On the complexity of computing with planar algebraic curves
- Numerical methods for roots of polynomials. II
- On the complexity of the Descartes method when using approximate arithmetic
- Almost tight recursion tree bounds for the Descartes method
- Amortized bound for root isolation via Sturm sequences
- Title not available (Why is that?)
- A simple but exact and efficient algorithm for complex root isolation
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Solving a Polynomial Equation: Some History and Recent Progress
- Title not available (Why is that?)
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- Root refinement for real polynomials using quadratic interval refinement
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- Title not available (Why is that?)
- A new proof of Vincent's theorem
- Complexity of real root isolation using continued fractions
- On the complexity of real root isolation using continued fractions
- When Newton meets Descartes
- Quadratic interval refinement for real roots
- Computer Algebra in Scientific Computing
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- A 2002 update of the supplementary bibliography on roots of polynomials
- A fast numerical algorithm for the composition of power series with complex coefficients
- Finding a cluster of zeros of univariate polynomials
- A near-optimal algorithm for computing real roots of sparse polynomials
- A comparative study of two real root isolation methods
- Title not available (Why is that?)
- Continued fraction real root isolation using the Hong root bound
- An iterated eigenvalue algorithm for approximating roots of univariate polynomials
Cited In (35)
- 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
- Title not available (Why is that?)
- Representing rational curve segments and surface patches using semi-algebraic sets
- Algorithms and Computation
- A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
- 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
- Title not available (Why is that?)
- Affine Loop Invariant Generation via Matrix Algebra
- On the complexity of the Descartes method when using approximate arithmetic
- 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
- New algorithms for computing a root of non-linear equations using exponential series
- Positive root isolation for poly-powers by exclusion and differentiation
- Bounds for polynomials on algebraic numbers and application to curve topology
- From approximate factorization to root isolation
- First study for ramp secret sharing schemes through greatest common divisor of polynomials
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- Computing Chebyshev knot diagrams
- Zero counting for a class of univariate Pfaffian functions
Uses Software
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)
