Bit-size estimates for triangular sets in positive dimension

DOI10.1016/J.JCO.2011.05.001MaRDI QIDQ657656zbMATH OpenOpenAlexFDO

Authors Xavier Dahan, A. Kadri, Éric Schost

Publication date 10 January 2012

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

Full work available at URL https://arxiv.org/abs/1008.3459

zbMATH Keywords

bit sizeheight functionregular chaintriangular sets

Mathematics Subject Classification ID

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)

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.

Review text

Bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over \(Q\) are given. The estimates are worst case upper bounds and depend on the degree and height of the underlying algebraic sets. The use of these results is demonstrated in the context of a modular algorithm. This work extends the results confined to the case of dimension \(0\), provided by \textit{X. Dahan} and \textit{E. Schost}, in: ISSAC 2004. Proceedings of the 2004 international symposium on symbolic and algebraic computation, Santander, Spain, July 4--7, 2004. 103--110 (2004; Zbl 1134.13308)]. The proposed strategy goes back to dimension \(0\) by evaluation and interpolation 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.

Recommendations

• Sharp estimates for triangular sets
• On the Bit-Size of Non-radical Triangular Sets
• Complexity results for triangular sets
• scientific article; zbMATH DE number 2151241
• A new method for solving algebraic systems of positive dimension

Cites work

• A Gröbner free alternative for polynomial system solving
• A new method for solving algebraic systems of positive dimension
• Accuracy and Stability of Numerical Algorithms
• Bounds of traces in complete intersections and degrees in the Nullstellensatz
• Change of order for regular chains in positive dimension
• Complexity results for triangular sets
• Computing parametric geometric resolutions
• Definability and fast quantifier elimination in algebraically closed fields
• scientific article; zbMATH DE number 3838204 (Why is no real title available?)
• scientific article; zbMATH DE number 47995 (Why is no real title available?)
• scientific article; zbMATH DE number 108109 (Why is no real title available?)
• scientific article; zbMATH DE number 1206418 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 939802 (Why is no real title available?)
• scientific article; zbMATH DE number 3230405 (Why is no real title available?)
• Lifting techniques for triangular decompositions
• Modern computer algebra
• On alternative heights. III
• On the effective Nullstellensatz
• On the theories of triangular sets
• Sharp estimates for the arithmetic Nullstellensatz
• Sharp estimates for triangular sets
• Solving zero-dimensional systems through the rational univariate representation
• The Magma algebra system. I: The user language
• Using Galois ideals for computing relative resolvents

Cited in

(8)

• Complexity results for triangular sets
• On the complexity of computing with zero-dimensional 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
• An application of regular chain theory to the study of limit cycles
• Algorithms for computing triangular decomposition of polynomial systems
• On the Bit-Size of Non-radical Triangular Sets
• Sharp estimates for triangular sets

Describes a project that uses

Uses Software

• Kronecker
• mctoolbox
• Magma
• ISOLATE

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)