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

DOI10.1016/J.TCS.2011.01.009zbMATH Open1243.12005OpenAlexW2059040957MaRDI QIDQ533873FDOQ533873

Authors: Angelos Mantzaflaris, Bernard Mourrain, Elias P. Tsigaridas 

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

Recommendations

• Continued fraction expansion of real roots of polynomial systems
• On the complexity of real root isolation using continued fractions
• Complexity of real root isolation using continued fractions
• Complexity of real root isolation using continued fractions
• On the roots of expanding integer polynomials
• On the complexity of computing real radicals of polynomial systems
• scientific article; zbMATH DE number 3960882
• Univariate Polynomial Real Root Isolation: Continued Fractions Revisited
• On the Real Parts of the Zeros of Complex Polynomials and Applications to Continued Fraction Expansions of Analytic Functions
• Real numbers with polynomial continued fraction expansions

zbMATH Keywords

continued fractionhomographymonomial basisreal root isolationsubdivision solver

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)

Cites Work

• A Short Proof and a Generalization of Miranda's Existence Theorem
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Title not available (Why is that?)
• Title not available (Why is that?)
• Almost tight recursion tree bounds for the Descartes method
• Computing nearest gcd with certification
• Title not available (Why is that?)
• Title not available (Why is that?)
• Real Algebraic Numbers: Complexity Analysis and Experimentation
• A Generalization of a Theorem of Bôcher
• Investigation of a subdivision based algorithm for solving systems of polynomial equations.
• Solving a Polynomial Equation: Some History and Recent Progress
• Complexity of Bezout's Theorem I: Geometric Aspects
• Approximating the zeros of analytic functions by the exclusion algorithm
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Subdivision methods for solving polynomial equations
• Tame geometry with application in smooth analysis
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster algorithms for computing Hong's bound on absolute positiveness
• The DMM bound: multivariate (aggregate) separation bounds
• Computing the real roots of a polynomial by the exclusion algorithm
• Computation of the solutions of nonlinear polynomial systems
• A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
• Computing roots of polynomials by quadratic clipping
• A numerical algorithm for zero counting. I: Complexity and accuracy
• Continued fraction expansion of real roots of polynomial systems

Cited In (13)

• Subtropical real root finding
• A quadratic clipping step with superquadratic convergence for bivariate polynomial systems
• Continuous amortization and extensions: with applications to bisection-based root isolation
• Continued fraction expansion of real roots of polynomial systems
• The complexity of subdivision for diameter-distance tests
• Real Root Isolation of Polynomial Equations Based on Hybrid Computation
• On the complexity of real root isolation using continued fractions
• Moment closure approximations of the Boltzmann equation based on \(\varphi \)-divergences
• Certified numerical real root isolation for bivariate nonlinear systems
• 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
• Nearly optimal refinement of real roots of a univariate polynomial
• Univariate Polynomial Real Root Isolation: Continued Fractions Revisited

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533873)