article

Computing a Gröbner basis of a polynomial ideal over a Euclidean domain

Authors:

Äbdelilah Kandri-Rody,

Deepak KapurAuthors Info & Claims

Journal of Symbolic Computation, Volume 6, Issue 1

Pages 37 - 57

https://doi.org/10.1016/S0747-7171(88)80020-8

Published: 01 August 1988 Publication History

Abstract

An algorithm for computing a Grobner basis of a polynomial ideal over a Euclidean domain is presented. The algorithm takes an ideal specified by a finite set of polynomials as its input; it produces another finite basis of the same ideal with the properties that using this basis, every polynomial in the ideal reduces to 0 and every polynomial in the polynomial ring reduces to a unique normal form. The algorithm is an extension of Buchberger's algorithms for computing Grobner bases of polynomial ideals over an arbitrary field and over the integers as well as our algorithms for computing Grobner bases of polynomial ideals over the integers and the Gaussian integers. The algorithm is simpler than other algorithms for polynomial ideals over a Euclidean domain reported in the literature; it is based on a natural way of simplifying polynomials by another polynomial using Euclid's division algorithm on the coefficients in polynomials. The algorithm is illustrated by showing how to compute Grobner bases for polynomial ideals over the integers, the Gaussian integers as well as over algebraic integers in quadratic number fields admitting a division algorithm. A general theorem exhibiting the uniqueness of a reduced Grobner basis of an ideal, determined by an admissible ordering on terms (power products) and other conditions, is discussed.

References

[1]

On constructing bases for ideals in polynomial rings over the integers. J. of Number Theory. v17. 204-225.

[2]

A simplified proof of the characterization theorem for Gröbner bases. A CM-SI G SAM Bulletin. v14/4. 29-34.

[3]

An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal. In: Ph.D. Thesis, Univ. of Innsbruck, Austria.

[4]

A theoretical basis for the reduction of polynomials to canonical forms. ACM-SIGSAM Bulletin. v10/3 i39. 19-29.

[5]

Some properties of Gro'bner bases for polynomial ideals. AOM-SIGSAM Bulletin. v10/4 i40. 19-24.

[6]

A critioal-pair/completion algorithm in reduction rings. In: Borger, E., Hasen-jaeger, G., Rodding, D. (Eds.), Proc. Logic and Machines: Decision Problems and Complexity, pp. 137-161.

[7]

Gröbner bases: An algorithmic method in polynomial ideal theory. In: Bose, N.K. (Ed.), Recent Results in Multidimensional Systems Theory, Reidel. pp. 184-232.

[8]

Algebraic simplification. In: Buchberger, B., Collins, G.E., Loos, R. (Eds.), Computer Algebra: Symbolic and Algebraic Computation, Springer Verlag. pp. 11-43.

[9]

In: The SAC-1 polynomial system, University of Wisconsin, Madison.

[10]

Oxford University Press, Oxford, England.

[11]

Equations and rewrite rules: A survey. In: Book, R. (Ed.), Formal Languages: Perspectives and Open Problems, Academic Press, New York.

[12]

Effective methods in the theory of polynomial ideals. In: Ph.D. Thesis, RPI, Troy, NY.

[13]

On relationship between Buchberger's Gröbner basis algorithm and the Knuth-Bendix completion procedure. In: TIS Report No. 83CRD286, General Electric Research and Development Center, Schenectady, NY.

[14]

Algorithms for computing the Gröbner basis of polynomial ideals over various Euclidean rings. In: Proceedings of EUROSAM ¿84, pp. 195-206.

[15]

Computing the Gröbner basis of polynomial ideals over the integers. In: Proceedings of Third MACSYMA Users' Conference, pp. 436-451.

[16]

An algorithm for computing the Gröbner basis of a polynomial ideal over a Euclidean ring. General Electric Corporate Research and Development Report No. 84CRD045, Schenectady, NY.

[17]

An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebras. In: Proceedings of First International Conference on Rewriting Techniques and Applications, Dijon, France, pp. 345-364.

[18]

Primality of ideals in polynomial rings. In: Proceedings of Third MACSYMA Users' Conference, pp. 459-471.

[19]

The Knuth-Bendix completion procedure and Thue systems. SIAM J. of Computing. v14. 1052-1072.

[20]

An equational approach to theorem proving in first-order predicate calculus. In: Proc. of the IJCAI-85, pp. 1146-1153.

[21]

Existence and construction of a Gröbner basis of a polynomial ideal. In: Proceedings of a workshop on Combinatorial Algorithms in Algebraic Structures, September 30-October 4, 1985, Europaeische Akademie, Otzenhausen, Univ. of Kaiserslautern, W. Germany.

[22]

Simple word problems in universal algebras. In: Leech, J. (Ed.), Computational Problems in Abstract Algebras, Pergamon Press. pp. 263-297.

[23]

Decision procedures for simple equational theories with commutative-associative axioms: Complete sets of commutative-associative reductions. In: Automatic Theorem Proving Project Report ATP-39,

[24]

On uniqueness of term rewriting systems. Louisiana Tech University.

[25]

Canonical representatives for residue classes of a polynomial ideal. In: SYMSAC-76, Yorktown Heights, NY, pp. 339-345.

[26]

Kanonische repraesentanten fuer die restklassen nach einem polynomideal. In: Diplomarbeit, Univ. of Kaiserslautern, W. Germany.

[27]

Canonical forms in finitely presented algebras. In: Proc. of 7th Intl. Conf. on Automated Deduction Springer Verlag LNCS 170,

[28]

Towards A formal implementation of computer algebra. EUROSAM-74. 9-16.

[29]

About the rewriting systems produced by the Knuth-Bendix completion algorithm. Information Processing Letters. v16. 31-34.

[30]

In: On the computation of Gröbner bases in commutative rings, Fern University, W. Germany.

[31]

New constructive methods in classical ideal theory. J. of Algebra. v100. 138-178.

[32]

Rewrite rule theory and abstract data type analysis. In: Calmet, (Ed.), Proc. Computer Algebra, EUROCAM, 1982, Springer Verlag. pp. 77-90.

[33]

Quadratic fields with and without Euclid's algorithm. Math. Annalen. v109. 349-352.

[34]

On the D-bases of ideals in polynomial rings over principal ideal domains. In: Proc. of the workshop Combinatorial Algorithms in Algebraic Structures at Europaeische Akademie,

[35]

Complete set of reductions for some equational theories. JACM. v28. 233-264.

[36]

Constructive aspects of Noetherian rings. Proc. American Math. Society. v44/4. 436-441.

[37]

Algorithmic aspects of polynomial residue class rings. In: Ph.D. Thesis, Computer Science Tech., University of Wisconsin, Madison.

[38]

A canonical form of polynomials in the presence of side relations. Technion Haifa Israel, Tech, Rep, PH-76-25.

[39]

In: Lifting canonical algorithms from a ring R to the ring R{x}, Dept. of Computer and Information Sciences, Univ. of Delaware.

[40]

A canonical basis for the ideals of a polynomial domain. American Mathematical Monthly. v59/6. 379-386.

[41]

Ueber B. Buchberger'a verfahern systeme algebraischer gleichungen zu loesen. J. of Number Theory. v10. 475-488.

[42]

In: Modern Algebra, Vols. I. Fredrick Ungar Publishing Co, New York.

[43]

Generalized Gröbner bases in commutative polynomial rings. In: Bachelor Thesis, Lab. for Computer Science, MIT.

Cited By

Hofstadler CVerron T(2023)Signature Gröbner bases in free algebras over ringsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597071(298-306)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597071
Francis MVerron TChyzak FLabahn G(2021)On Two Signature Variants of Buchberger's Algorithm over Principal Ideal DomainsProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465522(139-146)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465522
Ceria MMora T(2020)Toward involutive bases over effective ringsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-020-00448-631:5-6(359-387)Online publication date: 14-Aug-2020
https://dl.acm.org/doi/10.1007/s00200-020-00448-6
Show More Cited By

Index Terms

Computing a Gröbner basis of a polynomial ideal over a Euclidean domain
1. Mathematics of computing
  1. Mathematical analysis
    1. Nonlinear equations
    2. Numerical analysis
      1. Computations on polynomials

Recommendations

The Gröbner basis of the ideal of vanishing polynomials

We construct an explicit minimal strong Grobner basis of the ideal of vanishing polynomials in the polynomial ring over Z/m for m>=2. The proof is done in a purely combinatorial way. It is a remarkable fact that the constructed Grobner basis is ...
Computing comprehensive Gröbner systems and comprehensive Gröbner bases simultaneously
ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

In Kapur et al (ISSAC, 2010), a new method for computing a comprehensive Grobner system of a parameterized polynomial system was proposed and its efficiency over other known methods was effectively demonstrated. Based on those insights, a new approach ...
The Gröbner basis algorithm and subresultant theory
ISSAC '94: Proceedings of the international symposium on Symbolic and algebraic computation

We investigate the possibility of constructing for Gro¨bner bases a concept similar to the one provided by subresultants for polynomial remainder sequences. Namely, we try to express the Gro¨bner basis polynomials obtained during the algorithm in terms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Symbolic Computation

Journal of Symbolic Computation Volume 6, Issue 1

August 1988

129 pages

ISSN:0747-7171

Editor:
Bruno Buchberger
Johannes Kepler Univ., Linz, Austria

Issue’s Table of Contents

Copyright © Academic Press Limited © 1988.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 August 1988

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hofstadler CVerron T(2023)Signature Gröbner bases in free algebras over ringsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597071(298-306)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597071
Francis MVerron TChyzak FLabahn G(2021)On Two Signature Variants of Buchberger's Algorithm over Principal Ideal DomainsProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465522(139-146)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465522
Ceria MMora T(2020)Toward involutive bases over effective ringsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-020-00448-631:5-6(359-387)Online publication date: 14-Aug-2020
https://dl.acm.org/doi/10.1007/s00200-020-00448-6
Eder CPfister GPopescu AYap CEl Din M(2017)On Signature-Based Gröbner Bases Over Euclidean RingsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087614(141-148)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087614
Markwig TRen YWienand O(2017)Standard bases in mixed power series and polynomial rings over ringsJournal of Symbolic Computation10.1016/j.jsc.2016.08.00979:P1(119-139)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.jsc.2016.08.009
Zhang YAbramov SZima EGao X(2016)Contraction of Ore Ideals with ApplicationsProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930890(413-420)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930890
Kapur DNarendran PWang L(2003)An E-unification algorithm for analyzing protocols that use modular exponentiationProceedings of the 14th international conference on Rewriting techniques and applications10.5555/1759148.1759162(165-179)Online publication date: 9-Jun-2003
https://dl.acm.org/doi/10.5555/1759148.1759162
Madlener KReinert B(1993)Computing Gröbner bases in monoid and group ringsProceedings of the 1993 international symposium on Symbolic and algebraic computation10.1145/164081.164139(254-263)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1145/164081.164139
Pan L(1989)On the D-bases of polynomial ideals over principal ideal domainstJournal of Symbolic Computation10.1016/S0747-7171(89)80006-97:1(55-69)Online publication date: 3-Jan-1989
https://dl.acm.org/doi/10.1016/S0747-7171%2889%2980006-9

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents