𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Complexity of Gröbner Bases Conversion

✍ Scribed by Michael Kalkbrener

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
201 KB
Volume
28
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, the complexity of the conversion problem for Gröbner bases is investigated. It is shown that for adjacent Gröbner bases F and G, the maximal degree of the polynomials in G, denoted by deg(G), is bounded by a quadratic polynomial in deg(F ). For non-adjacent Gröbner bases, however, the growth of degrees can be doubly exponential.

📜 SIMILAR VOLUMES

On the Stability of Gröbner Bases Under
On the Stability of Gröbner Bases Under Specializations
✍ MICHAEL KALKBRENER 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 344 KB

Let R be a Noetherian commutative ring with identity, K a field and π a ring homomorphism from R to K. We investigate for which ideals in R[x 1 , . . . , xn] and admissible orders the formation of leading monomial ideals commutes with the homomorphism π.

Converting Bases with the Gröbner Walk
Converting Bases with the Gröbner Walk
✍ S. COLLART; M. KALKBRENER; D. MALL 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 299 KB

We present an algorithm which converts a given Gröbner basis of a polynomial ideal I to a Gröbner basis of I with respect to another term order. The conversion is done in several steps following a path in the Gröbner fan of I. Each conversion step is based on the computation of a Gröbner basis of a

Gröbner Bases of Modules over Reduction
Gröbner Bases of Modules over Reduction Rings
✍ S. Stifter 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 374 KB

Reduction rings are rings in which the Gröbner bases approach is possible, i.e., the Gröbner basis of an ideal in a reduction ring can be computed using Buchberger's algorithm. We show that one can also compute Gröbner bases of modules over reduction rings. Our approach is much more general than oth

A Note on Gröbner Bases and Integration
A Note on Gröbner Bases and Integration of Rational Functions
✍ Günter Czichowski 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 136 KB

It will be shown that for rational functions the logarithmic part of the integral can be computed in a very simple manner by Buchberger's algorithm.