Exponential space computation of Gröbner bases

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Exponential space computation of Gröbner bases

Full text

Pdf (1.07 MB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1996 international symposium on Symbolic and algebraic computation table of contents

Zurich, Switzerland

Pages: 63 - 71

Year of Publication: 1996

ISBN:0-89791-796-0

Authors

Klaus Kühnle	Institut für Informatik, Technische Universität München, D-80290 München, Germany
Ernst W. Mayr	Institut für Informatik, Technische Universität München, D-80290 München, Germany

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/236869.236900 What is a DOI?

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	Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, v.18 n.3, p.147-150, March 1984 [doi>10.1016/0020-0190(84)90018-8]
	2	BORODIN, A., VON zva GATHEN, J., AND HOPCROFT~ J. Fast parallel matrix and GCD computations. Information and Control 52 (1982), 241-256.
	3	BUCHBERGER, B. Ein Algorithmus zum A uffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Universit,it Innsbruck, 1965.
	4	Bruno Buchberger, A criterion for detecting unnecessary reductions in the construction of Groebner bases, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.3-21, June 01, 1979
	5	Bruno Buchberger, A note on the complexity of constructing Gröbner-Bases, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.137-145, March 28-30, 1983
	6	Leandro Caniglia , André Galligo , Joos Heintz, Some New Effectivity Bounds in Computational Geometry, Proceedings of the 6th International Conference, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.131-151, July 04-08, 1988
	7	CSANKY, L. Fast parallel matrix inversion algorithms. SIAM Journal on Computing 5, 4 (1976), 618-623.
	8	Thomas W. Dubé, The structure of polynomial ideals and Grobner bases, SIAM Journal on Computing, v.19 n.4, p.750-773, Aug. 1990 [doi>10.1137/0219053]
	9	DUBI~, T. W., MISHRA, B., AND YAP, C. K. Admissible orderings and bounds for GrSbner bases normal form algorithms. Technical Report 258, Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, 1986.
	10	Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
	11	Zvi Galil , Victor Pan, Parallel evaluation of the determinant and of the inverse of a matrix, Information Processing Letters, v.30 n.1, p.41-45, January 1989 [doi>10.1016/0020-0190(89)90173-7]
	12	Joos Heintz , Jacques Morgenstern, On the intrinsic complexity of elimination theory, Journal of Complexity, v.9 n.4, p.471-498, Dec. 1993 [doi>10.1006/jcom.1993.1031]
	13	HERMANN, G. Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Mathernatische Annalen 95 (1926), 736-788.
	14	Dung T Huynh, A superexponential lower bound for Gro¨bner bases and church-Rosser Commutative Thue systems, Information and Control, v.68 n.1-3, p.196-206, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80035-3]
	15	IBARRA, O. H., MORAN, S., AND ROSIER, L. E. A note on the parallel complexity of computing the rank of order n matrices. Information Processing Letters 11 (1980), 162.
	16	Ulla Koppenhagen , Ernst W. Mayr, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.55-62, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236899]
	17	KRICK, T., AND LOGAR, A. Membership problem, representation problem and the computation of the radical for one-dimensional ideals. In Effective Methods in A1- gebrazc Geometry (MEGA '90), Progress in Mathematics 94 (1991), Birkh~user Verlag, pp. 203-216.
	18	Daniel Lazard, Gröbner-Bases, Gaussian elimination and resolution of systems of algebraic equations, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.146-156, March 28-30, 1983
	19	MACAULAY, F. S. Algebraic Theory of Modular Systems. Cambridge University Press, Cambridge, 1916.
	20	MAYa, E. W. Polynomial ideals and applications. Mitteilungen der Mathematischen Gesellschaft in Hamburg XII, 4 (1992), 1207-1215.
	21	Ernst W. Mayr, On Polynomial Ideals, Their Complexity, and Applications, Proceedings of the 10th International Symposium on Fundamentals of Computation Theory, p.89-105, August 22-25, 1995
	22	MAYa, E. W., AND MEYER, A. P~. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics ~6, 3 (1982), 305-329.
	23	H. Michael Möller , Ferdinando Mora, Upper and Lower Bounds for the Degree of Groebner Bases, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.172-183, July 09-11, 1984
	24	MORA, T., AND ROBBIANO, L. The GrSbner fan of an ideal. In Computational aspects of commutative algebra, L. Robbiano, Ed. Academic Press, 1989, pp. 49-74.
	25	K Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.338-339, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12164]
	26	V. Pan, Complexity of parallel matrix computations, Theoretical Computer Science, v.54 n.1, p.65-85, 1987 [doi>10.1016/0304-3975(87)90019-3]
	27	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	28	PREPARATA, F. P., AND SARWATE, D. V. An improved parallel processor bound in fast matrix inversion. Information Processing Letters 7, 2 (1978), 148-150.
	29	RITTER, G., AND WEISPFENNING, V. On the number of term orders. Applicable Algebra in Engineemng, Communication and Computing 2 (1991), 55-79.
	30	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
	31	Lorenzo Robbiano, On the theory of graded structures, Journal of Symbolic Computation, v.2 n.2, p.139-170, June 1986 [doi>10.1006/jsco.1996.0006]
	32	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	33	V. Weispfenning, Constructing universal Groebner bases, Proceedings of the 5th international conference, AAECC-5 on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.408-417, June 1987, Menorca, Spain

CITED BY 3

	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Ulla Koppenhagen , Ernst W. Mayr, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.55-62, July 24-26, 1996, Zurich, Switzerland
	Quocnam Tran , Moshe Y. Vardi, Groebner bases computation in Boolean rings for symbolic model checking, Proceedings of the 18th conference on Proceedings of the 18th IASTED International Conference: modelling and simulation, p.440-445, May 30-June 01, 2007, Montreal, Canada