Irredundant triangular decomposition

DOI10.1145/3208976.3208996MaRDI QIDQ5120211zbMATH OpenOpenAlexWikidataFDO

Authors Gleb Pogudin, Agnes Szanto

Publication date 9 September 2020

Published in Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational aspects of higher-dimensional varieties (14Q15) Symbolic computation and algebraic computation (68W30)

Abstract: Triangular decomposition is a classic, widely used and well-developed way to represent algebraic varieties with many applications. In particular, there exist sharp degree bounds for a single triangular set in terms of intrinsic data of the variety it represents, and powerful randomized algorithms for computing triangular decompositions using Hensel lifting in the zero-dimensional case and for irreducible varieties. However, in the general case, most of the algorithms computing triangular decompositions produce embedded components, which makes it impossible to directly apply the intrinsic degree bounds. This, in turn, is an obstacle for efficiently applying Hensel lifting due to the higher degrees of the output polynomials and the lower probability of success. In this paper, we give an algorithm to compute an irredundant triangular decomposition of an arbitrary algebraic set $W$ defined by a set of polynomials in C[x_1, x_2, ..., x_n]. Using this irredundant triangular decomposition, we were able to give intrinsic degree bounds for the polynomials appearing in the triangular sets and apply Hensel lifting techniques. Our decomposition algorithm is randomized, and we analyze the probability of success.

Recommendations

• Complexity of triangular representations of algebraic sets
• scientific article; zbMATH DE number 2151241
• Algorithms for computing triangular decomposition of polynomial systems
• Complexity results for triangular sets
• A generalized Euclidean algorithm for computing triangular representations of algebraic varieties

Cited in

(10)

• A generalized Euclidean algorithm for computing triangular representations of algebraic varieties
• Complexity of triangular representations of algebraic sets
• Multiplicity-preserving triangular set decomposition of two polynomials
• Hierarchical Comprehensive Triangular Decomposition
• scientific article; zbMATH DE number 1421059 (Why is no real title available?)
• Bivariate triangular decompositions in the presence of asymptotes
• Computing with semi-algebraic sets represented by triangular decomposition
• Lifting techniques for triangular decompositions
• Persistent components in Canny's generalized characteristic polynomial
• Two new ways to formally prove Dandelin-Gallucci's theorem

This page was built for publication: Irredundant triangular decomposition

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