On the asymptotic and practical complexity of solving bivariate systems over the reals

DOI10.1016/j.jsc.2008.04.009zbMath1169.13306arXiv1203.1017OpenAlexW2130952444WikidataQ57908732 ScholiaQ57908732MaRDI QIDQ1025391

Elias P. Tsigaridas, Ioannis Z. Emiris, Dimitrios I. Diochnos

Publication date: 18 June 2009

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.1017

zbMATH Keywords

complexitypolynomial systemMaple softwarereal solving

Mathematics Subject Classification ID

Related Items (27)

A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers ⋮ Solving bivariate systems using rational univariate representations ⋮ Certified numerical real root isolation for bivariate nonlinear systems ⋮ On the complexity of computing the topology of real algebraic space curves ⋮ Computing the topology of a plane or space hyperelliptic curve ⋮ On the topology and isotopic meshing of plane algebraic curves ⋮ Exact symbolic-numeric computation of planar algebraic curves ⋮ \texttt{PTOPO}: computing the geometry and the topology of parametric curves ⋮ Algorithm for Connectivity Queries on Real Algebraic Curves ⋮ p-adic algorithm for bivariate Gröbner bases ⋮ Nearly optimal refinement of real roots of a univariate polynomial ⋮ Certified rational parametric approximation of real algebraic space curves with local generic position method ⋮ Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers ⋮ The nearest complex polynomial with a zero in a given complex domain ⋮ Computing the nearest polynomial with a zero in a given domain by using piecewise rational functions ⋮ A note on the complexity of real algebraic hypersurfaces ⋮ Separating linear forms and rational univariate representations of bivariate systems ⋮ A generic position based method for real root isolation of zero-dimensional polynomial systems ⋮ A new method to compute the singularities of offsets to rational plane curves ⋮ Bivariate triangular decompositions in the presence of asymptotes ⋮ From approximate factorization to root isolation with application to cylindrical algebraic decomposition ⋮ Univariate real root isolation in an extension field and applications ⋮ On the complexity of computing with planar algebraic curves ⋮ Exact line and plane search for tensor optimization ⋮ Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one ⋮ A worst-case bound for topology computation of algebraic curves ⋮ Multiplicity-preserving triangular set decomposition of two polynomials

Uses Software

• Maple
• SYNAPS
• ISOLATE
• insulate

Cites Work

• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Singular points of algebraic curves
• Subdivision methods for solving polynomial equations
• A polynomial-time algorithm for the topological type of real algebraic curve
• Solving zero-dimensional systems through the rational univariate representation
• Subresultants revisited.
• Efficient topology determination of implicitly defined algebraic plane curves.
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• The implicit structure of ridges of a smooth parametric surface
• Almost tight recursion tree bounds for the Descartes method
• Solving projective complete intersection faster
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
• Quadratic interval refinement for real roots
• Real Algebraic Numbers: Complexity Analysis and Experimentation
• RESOLUTION OF MULTIPLE ROOTS OF NONLINEAR POLYNOMIAL SYSTEMS
• On the exact computation of the topology of real algebraic curves
• Computer Algebra in Scientific Computing
• Algorithms in real algebraic geometry
• Sylvester-Habicht sequences and fast Cauchy index computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the asymptotic and practical complexity of solving bivariate systems over the reals