Complexity of triangular representations of algebraic sets

DOI10.1016/J.JALGEBRA.2019.01.007MaRDI QIDQ1714872zbMATH OpenOpenAlexWikidataFDO

Authors Eli Amzallag, Mengxiao Sun, Thieu N. Vo, Gleb Pogudin

Publication date 1 February 2019

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

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

zbMATH Keywords

complexityGröbner basisradical polynomial idealregular chaintriangular setunmixed algebraic set

Mathematics Subject Classification ID

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Symbolic computation and algebraic computation (68W30)

Abstract: Triangular decomposition is one of the standard ways to represent the radical of a polynomial ideal. A general algorithm for computing such a decomposition was proposed by A. Szanto. In this paper, we give the first complete bounds for the degrees of the polynomials and the number of components in the output of the algorithm, providing explicit formulas for these bounds.

Review text

One of the interesting and applied problems in computer algebra is representing the radical of a polynomial ideal. One of the main techniques developed in literature, for this purpose, is triangular decomposition. \textit{A. Szántó} in [Computation with polynomial systems. Ithaca, NY: Cornell University. PhD Thesis (1999), \url{http://www4.ncsu.edu/~aszanto/szanto.pdf}] proposed an algorithm for computing such a decomposition for a given ideal. In the paper under review, the authors present a complete bound on the degrees and the number of components of the decomposition calculated by this algorithm.

Recommendations

• Complexity results for triangular sets
• Irredundant triangular decomposition
• Sharp estimates for triangular sets
• Algorithms for computing triangular decomposition of polynomial systems
• scientific article; zbMATH DE number 1979251

Cites work

• A Gröbner free alternative for polynomial system solving
• An algorithm for the computation of the radical of an ideal
• Complexity results for triangular sets
• Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Definability and fast quantifier elimination in algebraically closed fields
• Doing algebraic geometry with the RegularChains library
• Double-exponential lower bound for the degree of any system of generators of a polynomial prime ideal
• Effective equidimensional decomposition of affine varieties
• scientific article; zbMATH DE number 16648 (Why is no real title available?)
• scientific article; zbMATH DE number 1254030 (Why is no real title available?)
• scientific article; zbMATH DE number 1979251 (Why is no real title available?)
• scientific article; zbMATH DE number 1860740 (Why is no real title available?)
• Lifting techniques for triangular decompositions
• On the complexity of counting components of algebraic varieties
• Sharp estimates for triangular sets

Cited in

(9)

• Complexity results for triangular sets
• On the complexity of computing with zero-dimensional triangular sets
• On the Bit-Size of Non-radical Triangular Sets
• Sharp estimates for triangular sets
• Irredundant triangular decomposition
• Bivariate triangular decompositions in the presence of asymptotes
• Computing with semi-algebraic sets represented by triangular decomposition
• Differential elimination and algebraic invariants of polynomial dynamical systems
• On the algebraic complexity of set equality and inclusion

Describes a project that uses

Uses Software

• Epsilon
• Kronecker
• DifferentialElimination
• RegularChains

This page was built for publication: Complexity of triangular representations of algebraic sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1714872)