IMAS 23417
INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Unidad Ejecutora - UE
artículos
Título:
Intrinsic complexity for constructing zero-Dimensional Grobner bases
Autor/es:
PARDO, L.M.; HASHEMI, A.; SOLERNÓ, PABLO; HEINTZ, J.
Revista:
LECTURE NOTES IN COMPUTER SCIENCE
Editorial:
Springer Nature
Referencias:
Año: 2020 vol. 122 p. 245 - 265
ISSN:
0302-9743
Resumen:
In this paper, we give a thorough revision of Lakshman´s paper by fixing some serious flaws in his approach. Furthermore, following this analysis, an intrinsic complexity bound for the construction of zero-dimensional Groebner bases is given. Our complexity bound is in terms of the degree of the input ideal as well as the degrees of its generators. Finally, as an application of the presented method, we exhibit and analyze a (Monte Carlo) probabilistic algorithm to compute the degree of an equi-dimensional ideal.
