On the complexity of solving a bivariate polynomial system

DOI10.1145/2442829.2442854zbMATH Open1308.68169arXiv1104.4954OpenAlexW2074967544MaRDI QIDQ5244530FDOQ5244530

Pavel Emeliyanenko, Michael Sagraloff

Publication date: 27 March 2015

Published in: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Abstract: We study the complexity of computing the real solutions of a bivariate polynomial system using the recently proposed algorithm BISOLVE. BISOLVE is a classical elimination method which first projects the solutions of a system onto the $x$- and $y$-axes and, then, selects the actual solutions from the so induced candidate set. However, unlike similar algorithms, BISOLVE requires no genericity assumption on the input nor it needs any change of the coordinate system. Furthermore, extensive benchmarks from cite{bes-bisolve-2011} confirm that the algorithm outperforms state of the art approaches by a large factor. In this work, we show that, for two polynomials $f,ginmathbbZ[x,y]$ of total degree at most $n$ with integer coefficients bounded by $2^{a}u$, BISOLVE computes isolating boxes for all real solutions of the system $f=g=0$ using $Otilde(n^{8}a{u}^2)$ bit operations, thereby improving the previous record bound by a factor of at least $n^2$.

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

Recommendations

• On the complexity of real solving bivariate systems
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• An elimination method for solving bivariate polynomial systems: eliminating the usual drawbacks
• Computer Algebra in Scientific Computing
• On solving systems of bivariate polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Numerical computation of roots of polynomial equations (65H04)

Cited In (21)

• On the complexity of quadratic programming with two quadratic constraints
• Title not available (Why is that?)
• On the complexity of computing the topology of real algebraic space curves
• Computing the topology of a plane or space hyperelliptic curve
• A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
• p-adic algorithm for bivariate Gröbner bases
• Continuous amortization and extensions: with applications to bisection-based root isolation
• Solvability of bivariate polynomial systems under perturbation
• Separating linear forms and rational univariate representations of bivariate systems
• On the complexity of computing with planar algebraic curves
• A generic position based method for real root isolation of zero-dimensional polynomial systems
• On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
• An \(\mathfrak{m}\)-adic algorithm for bivariate Gröbner bases
• A certified numerical algorithm for the topology of resultant and discriminant curves
• Computer Algebra in Scientific Computing
• Complexity of a root clustering algorithm for holomorphic functions
• The complexity of deciding consistency of systems of polynomials in exponent inequalities
• Nearly optimal refinement of real roots of a univariate polynomial
• Condition length and complexity for the solution of polynomial systems
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• Exact symbolic-numeric computation of planar algebraic curves

This page was built for publication: On the complexity of solving a bivariate polynomial system

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