Solving bivariate systems using rational univariate representations

DOI10.1016/j.jco.2016.07.002zbMath1351.65033OpenAlexW2464473992MaRDI QIDQ325154

Michael Sagraloff, Marc Pouget, Guillaume Moroz, Yacine Bouzidi, Sylvain Lazard, Fabrice Rouillier

Publication date: 17 October 2016

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2016.07.002

zbMATH Keywords

complexityalgorithmtriangular decompositionbivariate systemscoprime polynomialsrational univariate representations

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04) Solving polynomial systems; resultants (13P15)

Related Items

An algebraic framework for computing the topology of offsets to rational curves, A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers, 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, \texttt{PTOPO}: computing the geometry and the topology of parametric curves, The complexity of subdivision for diameter-distance tests, p-adic algorithm for bivariate Gröbner bases, Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers, A Symbolic Computation Approach Towards the Asymptotic Stability Analysis of Differential Systems with Commensurate Delays, Bivariate triangular decompositions in the presence of asymptotes, Fast computation of generic bivariate resultants, Certified numerical algorithm for isolating the singularities of the plane projection of generic smooth space curves, Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one, Bounds for polynomials on algebraic numbers and application to curve topology

Uses Software

• Kronecker
• modpn
• ISOLATE

Cites Work

• Unnamed Item
• Unnamed Item
• Separating linear forms and rational univariate representations of bivariate systems
• Root refinement for real polynomials using quadratic interval refinement
• Computing real roots of real polynomials
• The \texttt{modpn} library: bringing fast polynomial arithmetic into \texttt{Maple}
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• Fast modular transforms
• Solving zero-dimensional systems through the rational univariate representation
• An elementary approach to subresultants theory.
• Fast algorithms for zero-dimensional polynomial systems using duality
• PRIMES is in P
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• On the complexity of computing with planar algebraic curves
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• Modern Computer Algebra
• Improved algorithm for computing separating linear forms for bivariate systems
• Using Algebraic Geometry
• A simple but exact and efficient algorithm for complex root isolation
• Algorithms in real algebraic geometry
• Sylvester-Habicht sequences and fast Cauchy index computation
• A Gröbner free alternative for polynomial system solving