|
|
|
|
|
|
 |
 |
|
Revisiting strong Gröbner bases over Euclidean domains
|
|
|
|
|
|
| Organization: | Wolfram Research, Inc. |
|
|
|
|
|
|
2009-10-02
|
|
|
|
|
|
Manuscript from 2003, revised 2010
Abstract:
Buchberger and Kandri-Rody and Kapur defined a strong Gröbner basis for a polynomial ideal over a Euclidean domain in a way that gives rise to canonical reductions. This retains what is perhaps the most important property of Gröbner bases over fields. A difficulty is that these can be substantially harder to compute than their field counterparts. We extend their results for computing these bases to give an algorithm that is effective in practice. In particular we show how to use S-polynomials (rather than "critical pairs") so that the algorithm becomes quite similar to that for fields, and thus known strategies for the latter may be employed. We also show how Buchberger's important criteria for detection of unneeded S-polynomials can be extended to work over a Euclidean domain. We then provide simple examples as well as applications to solving equations in quotient rings, Hensel lifting, Hermite normal form computations, and reduction of univariate polynomial lattices. These serve to demonstrate why Gröbner basis computations over such rings are indeed worthy of consideration.
|
|
|
|
|
|
|
|
|
|
|
|
Groebner bases, Euclidean domains, strong Groebner bases, Euclidean rings, polynomial algebra
|
|
|
 |
|
|
| integer_Groebner_bases.pdf (194.8 KB) - PDF Document | | integer_Groebner_bases.nb (308.9 KB) - Mathematica Notebook |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
