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

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

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)

• Numerical solution of bivariate and polyanalytic polynomial systems
• On the complexity of quadratic programming with two quadratic constraints
• Computing the topology of a plane or space hyperelliptic curve
• On the complexity of computing the topology of real algebraic space curves
• scientific article; zbMATH DE number 1567790 (Why is no real title available?)
• 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
• Root isolation for bivariate polynomial systems with local generic position method
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• On solving systems of bivariate polynomials
• Solvability of bivariate polynomial systems under perturbation
• An elimination method for solving bivariate polynomial systems: eliminating the usual drawbacks
• 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 bit complexity of solving bilinear polynomial systems
• On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
• A certified numerical algorithm for the topology of resultant and discriminant curves
• An \(\mathfrak{m}\)-adic algorithm for bivariate Gröbner bases
• Computer Algebra in Scientific Computing
• The complexity of deciding consistency of systems of polynomials in exponent inequalities
• Separating linear forms for bivariate systems
• Nearly optimal refinement of real roots of a univariate polynomial
• Complexity of a root clustering algorithm for holomorphic functions
• Improved algorithm for computing separating linear forms for bivariate systems
• On the complexity of real solving bivariate systems
• 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)