Bit-size estimates for triangular sets in positive dimension
From MaRDI portal
Publication:657656
DOI10.1016/J.JCO.2011.05.001zbMATH Open1246.13039arXiv1008.3459OpenAlexW1965823846MaRDI QIDQ657656FDOQ657656
A. Kadri, Éric Schost, Xavier Dahan
Publication date: 10 January 2012
Published in: Journal of Complexity (Search for Journal in Brave)
Abstract: We give bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over Q. These estimates are worst case upper bounds; they depend only on the degree and height of the underlying algebraic sets. We illustrate the use of these results in the context of a modular algorithm. This extends results by the first and last author, which were confined to the case of dimension 0. Our strategy is to get back to dimension 0 by evaluation and inter- polation techniques. Even though the main tool (height theory) remains the same, new difficulties arise to control the growth of the coefficients during the interpolation process.
Full work available at URL: https://arxiv.org/abs/1008.3459
Recommendations
Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Numerical computation of solutions to systems of equations (65H10)
Cites Work
- The Magma algebra system. I: The user language
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sharp estimates for the arithmetic Nullstellensatz
- Title not available (Why is that?)
- Accuracy and Stability of Numerical Algorithms
- Solving zero-dimensional systems through the rational univariate representation
- Computing parametric geometric resolutions
- Title not available (Why is that?)
- Sharp estimates for triangular sets
- Title not available (Why is that?)
- Lifting techniques for triangular decompositions
- A Gröbner free alternative for polynomial system solving
- On the theories of triangular sets
- On alternative heights. III
- On the effective Nullstellensatz
- Modern computer algebra
- Definability and fast quantifier elimination in algebraically closed fields
- Title not available (Why is that?)
- A new method for solving algebraic systems of positive dimension
- Complexity results for triangular sets
- Using Galois ideals for computing relative resolvents
- Change of order for regular chains in positive dimension
- Title not available (Why is that?)
- Bounds of traces in complete intersections and degrees in the Nullstellensatz
Cited In (8)
- An application of regular chain theory to the study of limit cycles
- Sharp estimates for triangular sets
- Usage of modular techniques for efficient computation of ideal operations
- A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
- Complexity results for triangular sets
- Algorithms for computing triangular decomposition of polynomial systems
- On the complexity of computing with zero-dimensional triangular sets
- On the Bit-Size of Non-radical Triangular Sets
Uses Software
This page was built for publication: Bit-size estimates for triangular sets in positive dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657656)
