On the complexity of solving a bivariate polynomial system

DOI10.1145/2442829.2442854MaRDI QIDQ5244530zbMATH OpenOpenAlexFDO

Authors 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)

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

Mathematics Subject Classification ID

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

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$.

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

Cited in

(30)

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

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)