Monomial orderings and Gröbner bases

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Monomial orderings and Gröbner bases

Full text

Pdf (891 KB)

Source

ACM SIGSAM Bulletin archive
Volume 25 , Issue 1 (January 1991) table of contents

Pages: 10 - 23

Year of Publication: 1991

ISSN:0163-5824

Author

Fritz Schwarz

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 19, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/122525.122526 What is a DOI?

ABSTRACT

Let there be given a set of monomials in n variables and some order relations between them. The following fundamental problem of monomial ordering is considered. Is it possible to decide whether these ordering relations are consistent and if so to extend them to an admissible ordering for all monomials? The answer is given in terms of the algorithm MACOT which constructs a matrix of so called cotes which establishes the desired ordering relations. The main area of application of this algorithm, i.e. the construction of Gröbner bases for different orderings and of universal Gröbner bases is treated in the last section.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. Buchberger, <i>Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems</i>, Aequationes Mathematicae 4, 374--383(1970), page 184--232.
	2	B. Buchberger, <i>Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory</i> in <i>Multidimensional Systems Theory</i>, N. K. Bose, ed., Reidel Publisihing Company, 1985.
	3	J. M. Thomas, <i>Matrices of Integers Ordering Derivatives</i>, Transactions of the AMS <b>33</b>, 389--410 (1931).
	4	A. M. Ostrowski, <i>On multiplication and factorization of polynomials. I. Lexicographic orderings and extreme aggregates of terms. II. Irreducibility discussion</i>, Aequationes Mathematicae <b>13</b>, 201--228(1975) and <b>14,</b> 1--32(1976).
	5	Lorenzo Robbiano, Term Orderings on the Polynominal Ring, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.513-517, April 01-03, 1985
	6	D. Bayer, M. Stillman, <i>A Theorem on Refining Division Orders by the Reverse Lexicographic Order</i>, Duke Mathematical Journal <b>55</b>, 312(1987)
	7	Volker Weispfenning, Admissible orders and linear forms, ACM SIGSAM Bulletin, v.21 n.2, p.16-18, May 1987 [doi>10.1145/24554.24557]
	8	A. Galligo, <i>Théorème de division et stabilité en géometrique analytique locale</i>, Annales de l'Institut Fourier de Grenoble <b>29,</b> 107--184(1979).
	9	C. Kollreider, <i>Polynomial reduction: the influence of the ordering of terms on a reduction algorithm</i>, Camp. Linz Bericht Nr. 124 (1978).
	10	E. Burger, <i>Über homogene lineare Ungleichungssysteme</i>, Zeitschrift für angewandte Mathematik und Mechanik <b>36,</b> 135--139 (1956).
	11	F. Winkler , B. Buchberger , F. Lichtenberger , H. Rolletschek, ALGORITHM 628: an algorithm for constructing canonical bases of polynomial ideals, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.66-78, March 1985 [doi>10.1145/3147.214316]
	12	Richard D. Jenks , Robert S. Sutor , Stephen M. Watt, Scratchpad II: An Abstract Datatype System for Mathematical Computation, Proceedings of the International Symposium on Trends in Computer Algebra, p.12-37, May 19-21, 1987
	13	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	14	M. E. Dyer, <i>The Complexity of Vertex Enumeration Methods</i>, Mathematics of Operations Research <b>8</b>, 381--402(1983).
	15	T. H. Matheiss, D. S. Rubin, <i>A Survey and Comparison of Methods for Finding all Vertices of Convex Polyhedral Sets</i>, Mathematics of Operations Research 5, 167--185 (1980).

CITED BY 3

	Fritz Schwarz, Reduction and completion algorithms for partial differential equations, Papers from the international symposium on Symbolic and algebraic computation, p.49-56, July 27-29, 1992, Berkeley, California, United States
	Volker Weispfenning, Differential term-orders, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.245-253, July 06-08, 1993, Kiev, Ukraine
	C. J. Rust , G. J. Reid, Rankings of partial derivatives, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.9-16, July 21-23, 1997, Kihei, Maui, Hawaii, United States