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

complexitytriangular setregular chainradical polynomial idealunmixed algebraic setGröbner basis

Mathematics Subject Classification ID

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

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.

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

• 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?)
• 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
• Lifting techniques for triangular decompositions
• On the complexity of counting components of algebraic varieties
• Sharp estimates for triangular sets

Cited in

(8)

• Computing with semi-algebraic sets represented by triangular decomposition
• On the complexity of computing with zero-dimensional triangular sets
• On the algebraic complexity of set equality and inclusion
• Complexity results for 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

Describes a project that uses

Uses Software

• Epsilon
• Kronecker
• RegularChains
• DifferentialElimination

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)