On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers

DOI10.1016/j.tcs.2011.01.009zbMath1243.12005OpenAlexW2059040957MaRDI 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

zbMATH Keywords

continued fractionmonomial basishomographyreal root isolationsubdivision solver

Mathematics Subject Classification ID

Related Items (9)

Continuous amortization and extensions: with applications to bisection-based root isolation ⋮ Moment closure approximations of the Boltzmann equation based on \(\varphi \)-divergences ⋮ Certified numerical real root isolation for bivariate nonlinear systems ⋮ The complexity of subdivision for diameter-distance tests ⋮ Nearly optimal refinement of real roots of a univariate polynomial ⋮ Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers ⋮ 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 ⋮ 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

This page was built for publication: On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers