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

Abstract

This paper is concerned with exact real solving of well-constrained, bivariate polynomial systems. The main problem is to isolate all common real roots in rational rectangles, and to determine their intersection multiplicities. We present three algorithms and analyze their asymptotic bit complexity, obtaining a bound of $\sOB(N^{14})$ for the purely projection-based method, and $\sOB(N^{12})$ for two subresultant-based methods: this notation ignores polylogarithmic factors, where $N$ bounds the degree and the bitsize of the polynomials. The previous record bound was $\sOB(N^{14})$. Our main tool is signed subresultant sequences. We exploit recent advances on the complexity of univariate root isolation, and extend them to sign evaluation of bivariate polynomials over two algebraic numbers, and real root counting for polynomials over an extension field. Our algorithms apply to the problem of simultaneous inequalities; they also compute the topology of real plane algebraic curves in $\sOB(N^{12})$, whereas the previous bound was $\sOB(N^{14})$. All algorithms have been implemented in MAPLE, in conjunction with numeric filtering. We compare them against FGB/RS, system solvers from SYNAPS, and MAPLE libraries INSULATE and TOP, which compute curve topology. Our software is among the most robust, and its runtimes are comparable, or within a small constant factor, with respect to the C/C++ libraries. Key words: real solving, polynomial systems, complexity, MAPLE software

arXiv comment17 pages, 4 algorithms, 1 table, and 1 figure with 2 sub-figures

Cited by in corpus (18)

• On the Complexity of Real Root Isolation
• The DMM bound: multivariate (aggregate) separation bounds
• From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition
• $p$-adic algorithm for bivariate Gröbner bases
• A Worst-case Bound for Topology Computation of Algebraic Curves
• On the Complexity of Solving a Bivariate Polynomial System
• A Generic Position Based Method for Real Root Isolation of Zero-Dimensional Polynomial Systems
• Algorithm for connectivity queries on real algebraic curves
• Multiplicity Preserving Triangular Set Decomposition of Two Polynomials
• A new method to compute the singularities of offsets to rational plane curves
• On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
• Computing the symmetries of a ruled rational surface
• Univariate real root isolation in an extension field
• Lexicographic Groebner bases of bivariate polynomials modulo a univariate one
• Solving sparse polynomial systems using Groebner bases and resultants
• On the Complexity of Computing the Topology of Real Algebraic Space Curves
• An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks
• Computing the topology of a planar or space hyperelliptic curve