On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers
type: Item
instance of: scholarly article
title: On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers
zbMATH Open document ID: 1243.12005
author: Angelos Mantzaflaris
author: Bernard Mourrain
author: Elias P. Tsigaridas
published in: Theoretical Computer Science
publication date: 2011-05-10T00:00:00Z
full work available at URL: mcf tcs.pdf
review text: This paper develops a new algorithm for real root isolation of a system of multivariate polynomial functions. This algorithm is the multivariate extension of the novel Continued Fraction algorithm for univariate polynomials. The authors present a comprehensive complexity analysis for this algorithm and report the running times for a C++ implementation of this method which is freely available. The problem of computing roots of univariate polynomials is one of the most studied problems in mathematics and computer science. In recent years most efforts have been concentrated on subdivision-based algorithms where the localization of the roots is based on simple tests such as \textit{Descartes' Rule of Signs} or, more recently, on the computation of lower bounds of the positive real roots underlying Continued Fraction subdivision algorithms. The analysis of subdivision methods for the approximation of isolated roots of multivariate systems is much less advanced. In this paper, the authors present a new adaptive algorithm for polynomial system real solving that acts in monomial basis (as opposed to the more standard Bernstein basis representation), and exploits the continued fraction expansion of the coordinates of the real roots. This method yields the best rational approximation of the real roots. Further, all computations are performed with integers, thus this is a division-free algorithm. The authors present a thorough bit complexity analysis of the algorithm, when oracles for lower bounds and real root counting are available. In all cases, the bounds established in this paper for the multivariate case match the best known bounds for the univariate case when this method is restricted to the latter case. The authors also present bounds in the real RAM model for a family of subdivision algorithms in terms of the real \textit{condition number} of the system. In particular, the authors show that the logarithm of the condition number of the system is involved linearly in th…
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 12D10
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5886213
zbMATH Keywords: real root isolation
zbMATH Keywords: subdivision solver
zbMATH Keywords: monomial basis
zbMATH Keywords: homography
zbMATH Keywords: continued fraction
reviewed by: Luis David Garcia Puente
MaRDI profile type: Publication
OpenAlex ID: W2059040957
cites work: A new proof of Vincent's theorem
cites work: Computing roots of polynomials by quadratic clipping
cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
cites work: Q4843630
cites work: Computing nearest Gcd with certification
cites work: A numerical algorithm for zero counting. I: Complexity and accuracy
cites work: A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
cites work: Computing the real roots of a polynomial by the exclusion algorithm
cites work: Almost tight recursion tree bounds for the Descartes method
cites work: Real Algebraic Numbers: Complexity Analysis and Experimentation
cites work: The DMM bound
cites work: Investigation of a subdivision based algorithm for solving systems of polynomial equations.
cites work: Q5727753
cites work: Continued fraction expansion of real roots of polynomial systems
cites work: A Generalization of a Theorem of Bôcher
cites work: Faster algorithms for computing Hong's bound on absolute positiveness
cites work: Subdivision methods for solving polynomial equations
cites work: Q5290272
cites work: Solving a Polynomial Equation: Some History and Recent Progress
cites work: Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
cites work: Complexity of real root isolation using continued fractions
cites work: Computation of the solutions of nonlinear polynomial systems
cites work: Complexity of Bezout's Theorem I: Geometric Aspects
cites work: On the complexity of real root isolation using continued fractions
cites work: Q3728068
cites work: Q4226936
cites work: A Short Proof and a Generalization of Miranda's Existence Theorem
cites work: Approximating the zeros of analytic functions by the exclusion algorithm
cites work: Q4953977
cites work: Tame geometry with application in smooth analysis
DOI: 10.1016/J.TCS.2011.01.009
Recommended article: Continued fraction expansion of real roots of polynomial systems
Recommended article: On the complexity of real root isolation using continued fractions
Recommended article: Q5301690
Recommended article: Complexity of real root isolation using continued fractions
Recommended article: On the roots of expanding integer polynomials
Recommended article: On the Complexity of Computing Real Radicals of Polynomial Systems
Recommended article: Q3729925
Recommended article: Univariate Polynomial Real Root Isolation: Continued Fractions Revisited
Recommended article: On the Real Parts of the Zeros of Complex Polynomials and Applications to Continued Fraction Expansions of Analytic Functions
Recommended article: Real numbers with polynomial continued fraction expansions
description: scientific article; zbMATH DE number 5886213