TY - UNPB
T1 - Complexity of Triangular Representations of Algebraic Sets
AU - Pogudin, Gleb
AU - Vo Ngoc, Thieu
AU - Amzallag, Eli
AU - Sun, Mengxiao
PY - 2016/12
Y1 - 2016/12
N2 - Motivated by order bounds for algorithms for algebraic differential equations (for example, effective differential elimination and Nullstellensatz), representing the radical of a given polynomial ideal or, equivalently, the corresponding affine variety, using triangular sets is of primary interest. An algorithm to construct such a representation was proposed by A. Szanto. In this paper, we give the first complete bound for the degrees for the polynomials in the output of the algorithm and provide an explicit formula for the bound. In addition, we bound the number of components in the output and compare our degree bounds to those of Groebner bases computation.
AB - Motivated by order bounds for algorithms for algebraic differential equations (for example, effective differential elimination and Nullstellensatz), representing the radical of a given polynomial ideal or, equivalently, the corresponding affine variety, using triangular sets is of primary interest. An algorithm to construct such a representation was proposed by A. Szanto. In this paper, we give the first complete bound for the degrees for the polynomials in the output of the algorithm and provide an explicit formula for the bound. In addition, we bound the number of components in the output and compare our degree bounds to those of Groebner bases computation.
UR - https://arxiv.org/abs/1609.09824
U2 - 10.48550/arXiv.1609.09824
DO - 10.48550/arXiv.1609.09824
M3 - Preprint
T3 - arXiv.org
BT - Complexity of Triangular Representations of Algebraic Sets
ER -