On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers
From MaRDI portal
Publication:533873
DOI10.1016/j.tcs.2011.01.009zbMath1243.12005MaRDI QIDQ533873
Angelos Mantzaflaris, Elias P. Tsigaridas, Mourrain, Bernard
Publication date: 10 May 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/inria-00530756/file/mcf_tcs.pdf
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
12D10: Polynomials in real and complex fields: location of zeros (algebraic theorems)
Related Items
Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers, Continuous amortization and extensions: with applications to bisection-based root isolation, Moment closure approximations of the Boltzmann equation based on \(\varphi \)-divergences, A generic position based method for real root isolation of zero-dimensional polynomial systems, A quadratic clipping step with superquadratic convergence for bivariate polynomial systems, Nearly optimal refinement of real roots of a univariate polynomial, Certified numerical real root isolation for bivariate nonlinear systems, The complexity of subdivision for diameter-distance tests, Real Root Isolation of Polynomial Equations Based on Hybrid Computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- Computing roots of polynomials by quadratic clipping
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Faster algorithms for computing Hong's bound on absolute positiveness
- Subdivision methods for solving polynomial equations
- Computing the real roots of a polynomial by the exclusion algorithm
- Computation of the solutions of nonlinear polynomial systems
- Approximating the zeros of analytic functions by the exclusion algorithm
- Tame geometry with application in smooth analysis
- A new proof of Vincent's theorem
- Investigation of a subdivision based algorithm for solving systems of polynomial equations.
- Complexity of real root isolation using continued fractions
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- On the complexity of real root isolation using continued fractions
- The DMM bound
- Almost tight recursion tree bounds for the Descartes method
- Computing nearest Gcd with certification
- Continued fraction expansion of real roots of polynomial systems
- A Short Proof and a Generalization of Miranda's Existence Theorem
- Complexity of Bezout's Theorem I: Geometric Aspects
- Solving a Polynomial Equation: Some History and Recent Progress
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Real Algebraic Numbers: Complexity Analysis and Experimentation
- A Generalization of a Theorem of Bôcher
