×

The virtues of laziness: Complexity of the tangent cone algorithm. (English) Zbl 0821.13012

The study of computational problems in the ideal theory of local rings led to the notion of standard bases. These are a version of Gröbner bases for orderings which are not well orderings. In most cases appearing in applications, the tangent cone algorithm computes a standard basis of a given ideal [T. Mora, G. Pfister and C. Traverso, “An introduction to the tangent cone algorithm”, In: C. M. Hoffman (ed.), Issues in robotics and nonlinear geometry, JAI Press (1992)]. Roughly speaking, this is a variant of the Buchberger algorithm with suitable modifications to avoid infinitely long reductions.
The complexity of the tangent cone algorithm is unknown. In the present paper the authors introduce a “very lazy” version of the algorithm which allows early interruptions based on a priori knowledge, for example, of the upper bound of the degrees of elements in a standard basis. In this case the algorithm is shown to have the same complexity as the Buchberger one.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68Q25 Analysis of algorithms and problem complexity
13A15 Ideals and multiplicative ideal theory in commutative rings
13H99 Local rings and semilocal rings
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gräbe, H.: The tangent cone algorithm and homogeneization, Preprint · Zbl 0813.13027
[2] Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of polynomial equations, Proc. EUROCAL 83, Lect. Notes. Comp. Sci.162, 146-156 (1983) · Zbl 0539.13002
[3] Mora, T.: La queste del Saint Gra(AL): a computational approach to local algebra, Disc. Appl. Math.33, 161-190 (1991) · Zbl 0752.13016 · doi:10.1016/0166-218X(91)90114-C
[4] Mora, T., Pfister, G., Traverso, C: An introduction to the tangent cone algorithm. In: C. M. Hoffmann (ed.) Issues in robotics and non-linear geometry, JAI Press (1992)
[5] Moreno, G.: An Ackermannian polynomial ideal, Proc. AAECC 9, Lect. Notes Comp. Sci.539, 269-280(1991) · Zbl 0781.13017
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.