✦ LIBER ✦

Modular algorithms for computing Gröbner bases

✍ Scribed by Elizabeth A. Arnold

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 190 KB
Volume: 35
Category: Article
ISSN: 0747-7171
DOI: 10.1016/s0747-7171(02)00140-2

No coin nor oath required. For personal study only.

✦ Synopsis

Intermediate coefficient swell is a well-known difficulty with Buchberger's algorithm for computing Gröbner bases over the rational numbers. p-Adic and modular methods have been successful in limiting intermediate coefficient growth in other computations, and in particular in the Euclidian algorithm for computing the greatest common divisor (GCD) of polynomials in one variable. In this paper we present two modular algorithms for computing a Gröbner basis for an ideal in Q[x 1 , . . . , x ν ] which extend the modular GCD algorithms. These algorithms improve upon previously proposed modular techniques for computing Gröbner bases in that we test primes before lifting, and also provide an algorithm for checking the result for correctness. A complete characterization of unlucky primes is also given. Finally, we give some preliminary timings which indicate that these modular algorithms can provide considerable time improvements in examples where intermediate coefficient growth is a problem.

📜 SIMILAR VOLUMES

Multiplicative Bases, Gröbner Bases, and

Multiplicative Bases, Gröbner Bases, and Right Gröbner Bases

✍ Edward L. Green 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 314 KB

In this paper, we study conditions on algebras with multiplicative bases so that there is a Gröbner basis theory. We introduce right Gröbner bases for a class of modules. We give an elimination theory and intersection theory for right submodules of projective modules in path algebras. Solutions to h

A New Algorithm for Discussing Gröbner B

A New Algorithm for Discussing Gröbner Bases with Parameters

✍ Antonio Montes 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 372 KB

Let F be a set of polynomials in the variables x = x 1 , . . . , xn with coefficients in R[a], where R is a UFD and a = a 1 , . . . , am a set of parameters. In this paper we present a new algorithm for discussing Gröbner bases with parameters. The algorithm obtains all the cases over the parameters

Regular Gröbner Bases

✍ Jonas MÅnsson; Patrik Nordbeck 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 366 KB

In this paper we introduce the concept of bi-automaton algebras, generalizing the automaton algebras previously defined by Ufnarovski. A bi-automaton algebra is a quotient of the free algebra, defined by a binomial ideal admitting a Gröbner basis which can be encoded as a regular set; we call such a

Computation of Gröbner bases for two-loo

Computation of Gröbner bases for two-loop propagator type integrals

✍ O.V. Tarasov 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 192 KB

The Gro¨bner basis technique for calculating Feynman diagrams proposed in (Acta Phys. Pol. B 29(1998) 2655) is applied to the two-loop propagator type integrals with arbitrary masses and momentum. We describe the derivation of Gro¨bner bases for all integrals with 1PI topologies and present explicit

Counting and Gröbner Bases

✍ K. Kalorkoti 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 239 KB

We show how the complexity of counting relates to the well known phenomenon that computing Gröbner bases under a lexicographic order is generally harder than total degree orders. We give simple examples of polynomials for which it is very easy to compute their Gröbner basis using a total degree orde

Canonical comprehensive Gröbner bases

✍ Volker Weispfenning 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 204 KB

Comprehensive Gröbner bases for parametric polynomial ideals were introduced, constructed, and studied by the author in 1992. Since then the construction has been implemented in the computer algebra systems ALDES/SAC-2, MAS, REDUCE and MAPLE. A comprehensive Gröbner basis is a finite subset G of a p