×

Complexity of triangular representations of algebraic sets. (English) Zbl 1408.14193

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. A. Szántó in [Computation with polynomial systems. Ithaca, NY: Cornell University. PhD Thesis (1999), 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.

MSC:

14Q20 Effectivity, complexity and computational aspects of algebraic geometry
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alvandi, P.; Chen, C.; Marcus, S.; Maza, M. M.; Schost, É.; Vrbik, P., Doing algebraic geometry with the RegularChains library, (Hong, H.; Yap, C., Mathematical Software. Mathematical Software, ICMS 2014 (2014), Springer: Springer Berlin-Heidelberg), 472-479 · Zbl 1437.13003
[2] Bürgisser, P.; Scheiblechner, P., On the complexity of counting components of algebraic varieties, J. Symbolic Comput., 44, 9, 1114-1136 (2009) · Zbl 1169.14041
[3] Chistov, A., Double-exponential lower bound for the degree of any system of generators of a polynomial prime ideal, St. Petersburg Math. J., 20, 6, 983-1001 (2009) · Zbl 1206.13031
[4] Dahan, X.; Moreno Maza, M.; Schost, E.; Wu, W.; Xie, Y., Lifting techniques for triangular decompositions, (ISSAC’05 (2005), ACM: ACM New York), 108-115 · Zbl 1360.14146
[5] Dahan, X.; Schost, E., Sharp estimates for triangular sets, (Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation. Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, ISSAC ’04 (2004), ACM: ACM New York, NY, USA), 103-110 · Zbl 1134.13308
[6] Gallo, G.; Mishra, B., Efficient algorithms and bounds for Wu-Ritt characteristic sets, (Effective Methods in Algebraic Geometry (1991), Springer), 119-142 · Zbl 0747.13019
[7] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complexity, 17, 1, 154-211 (2001) · Zbl 1003.12005
[8] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24, 3, 239-277 (1983) · Zbl 0546.03017
[9] Hubert, E., Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems, (Proceedings of the 2nd International Conference on Symbolic and Numerical Scientific Computation. Proceedings of the 2nd International Conference on Symbolic and Numerical Scientific Computation, SNSC’01 (2003), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 1-39 · Zbl 1022.12004
[10] Jeronimo, G.; Sabia, J., Effective equidimensional decomposition of affine varieties, J. Pure Appl. Algebra, 169, 2, 229-248 (2002) · Zbl 1055.14061
[11] Laplagne, S., An algorithm for the computation of the radical of an ideal, (Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation. Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC ’06 (2006), ACM: ACM New York, NY, USA), 191-195 · Zbl 1356.68285
[12] Lecerf, G., Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions, (Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (2000)), 209-216 · Zbl 1326.68360
[13] Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, J. Complexity, 19, 4, 564-596 (2003) · Zbl 1230.68222
[14] Ovchinnikov, A.; Pogudin, G.; Vo, T. N., Bounds for elimination of unknowns in systems of differential-algebraic equations (2018), Preprint
[15] Schost, E., Complexity results for triangular sets, ISSAC 2002. ISSAC 2002, J. Symbolic Comput., 36, 3-4, 555-594 (2003) · Zbl 1074.68082
[16] Szántó, A., Complexity of the Wu-Ritt decomposition, (Second International Symposium on Parallel Symbolic Computation. Second International Symposium on Parallel Symbolic Computation, PASCO ’97, Maui, HI, USA, July 20-22 (1997), ACM Press: ACM Press ew York, NY), 139-149 · Zbl 0937.68161
[17] Szántó, A., Computation with Polynomial Systems (1999), Cornell University, Ph.D. thesis
[18] Wang, D., Epsilon: a library of software tools for polynomial elimination, (Mathematical Software (2002), World Scientific), 379-389 · Zbl 1012.68232
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.