A generic position based method for real root isolation of zero-dimensional polynomial systems
From MaRDI portal
Publication:480656
DOI10.1016/J.JSC.2014.09.017zbMATH Open1304.13048arXiv1312.0462OpenAlexW2048055604MaRDI QIDQ480656FDOQ480656
Publication date: 9 December 2014
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Abstract: We improve the local generic position method for isolating the real roots of a zero-dimensional bivariate polynomial system with two polynomials and extend the method to general zero-dimensional polynomial systems. The method mainly involves resultant computation and real root isolation of univariate polynomial equations. The roots of the system have a linear univariate representation. The complexity of the method is for the bivariate case, where , resp., is an upper bound on the degree, resp., the maximal coefficient bitsize of the input polynomials. The algorithm is certified with probability 1 in the multivariate case. The implementation shows that the method is efficient, especially for bivariate polynomial systems.
Full work available at URL: https://arxiv.org/abs/1312.0462
Recommendations
- Root isolation for bivariate polynomial systems with local generic position method
- Local Generic Position for Root Isolation of Zero-Dimensional Triangular Polynomial Systems
- An efficient real root isolation algorithm for a zero-dimensional triangular polynomial system
- Certified numerical real root isolation for bivariate polynomial systems
- An elimination method for solving bivariate polynomial systems: eliminating the usual drawbacks
Symbolic computation and algebraic computation (68W30) Polynomials, factorization in commutative rings (13P05)
Cites Work
- Efficient isolation of polynomial's real roots.
- Root isolation for bivariate polynomial systems with local generic position method
- Introduction to Interval Analysis
- Title not available (Why is that?)
- Algorithms in real algebraic geometry
- On the asymptotic and practical complexity of solving bivariate systems over the reals
- Solving zero-dimensional systems through the rational univariate representation
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks
- On the complexity of solving a bivariate polynomial system
- Computer Algebra in Scientific Computing
- A Gröbner free alternative for polynomial system solving
- Title not available (Why is that?)
- Real Algebraic Numbers: Complexity Analysis and Experimentation
- On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- An algorithm for isolating the real solutions of semi-algebraic systems
- On the theory of resolvents and its applications.
- Title not available (Why is that?)
- Subdivision methods for solving polynomial equations
- Exact symbolic-numeric computation of planar algebraic curves
- Title not available (Why is that?)
- When Newton meets Descartes
- A worst-case bound for topology computation of algebraic curves
- Complete numerical isolation of real roots in zero-dimensional triangular systems
- Title not available (Why is that?)
- Root isolation of zero-dimensional polynomial systems with linear univariate representation
- Computing primitive elements of extension fields
- On the boolean complexity of real root refinement
- Radical computations of zero-dimensional ideals and real root counting.
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Parallel computation of real solving bivariate polynomial systems by zero-matching method
- Title not available (Why is that?)
- Computer Algebra in Scientific Computing
Cited In (12)
- On the complexity of computing the topology of real algebraic space curves
- Representing rational curve segments and surface patches using semi-algebraic sets
- A heuristic method for certifying isolated zeros of polynomial systems
- On \(G^2\) approximation of planar algebraic curves under certified error control by quintic Pythagorean-hodograph splines
- Certified numerical real root isolation for bivariate nonlinear systems
- Globally certified \(G^1\) approximation of planar algebraic curves
- Title not available (Why is that?)
- On the topology and isotopic meshing of plane algebraic curves
- Isotopic meshing of a real algebraic space curve
- Local Generic Position for Root Isolation of Zero-Dimensional Triangular Polynomial Systems
- Continuous detection of the variations of the intersection curve of two moving quadrics in 3-dimensional projective space
- Resultant elimination via implicit equation interpolation
Uses Software
This page was built for publication: A generic position based method for real root isolation of zero-dimensional polynomial systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q480656)
