In this short note, we extend Faugére’s F4-algorithm for computing Gröbner bases to polynomial rings with coefficients in an Euclidean ring. Instead of successively reducing single S-polynomials as in Buchberger’s algorithm, the F4-algorithm is based on the simultaneous reduction of several polynomials.
@article{bwmeta1.element.doi-10_2478_s11533-010-0064-x,
author = {Afshan Sadiq},
title = {The F4-algorithm for Euclidean rings},
journal = {Open Mathematics},
volume = {8},
year = {2010},
pages = {1156-1159},
zbl = {1210.13030},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0064-x}
}
Afshan Sadiq. The F4-algorithm for Euclidean rings. Open Mathematics, Tome 8 (2010) pp. 1156-1159. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0064-x/
[1] Adams W.W., Loustaunau P., An Introduction to Gröbner Bases, Grad. Stud. Math., 3, American Mathematical Scociety, Providence, 2003
[2] Buchberger B., Bruno BuchbergerŠs PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, J. Symbolic Comput., 2006, 41(3–4), 475–511 http://dx.doi.org/10.1016/j.jsc.2005.09.007
[3] Cox D.A., Little J., O’shea D., Using Algebraic Geometry, 2nd ed., Grad. Texts in Math., 185, Springer, New York, 2005
[4] Faugére J.-Ch., A new efficient algorithm for computing Gröbner bases (F 4), J. Pure Appl. Algebra, 1999, 139(1–3), 61–88 http://dx.doi.org/10.1016/S0022-4049(99)00005-5
[5] Greuel G.-M., Pfister G., A Singular Introduction to Commutative Algebra, 2nd ed., Springer, Berlin, 2008
[6] Greuel G.-M., Pfister G., Schönemann H., Singular - A Computer Algebra System for Polynomial Computations, free software under GNU General Public Licence (1990-to date), available at http://www.singular.uni-kl.de