@inproceedings{29b650812daa4b32bf0c23f3f792f15e,

title = "Space-efficient Gr{\"o}bner basis computation without degree bounds",

abstract = "The computation of a Gr{\"o}bner basis of a polynomial ideal is known to be exponential space complete. We revisit the algorithm by K{\"u}hnle and Mayr using recent improvements of various degree bounds. The result is an algorithm which is exponential in the ideal dimension (rather than the number of indeterminates). Furthermore, we provide an incremental version of the algorithm which is independent of the knowledge of degree bounds. Employing a space-efficient implementation of Buchberger's S-criterion, the algorithm can be implemented such that the space requirement depends on the representation and Gr{\"o}bner basis degrees of the problem instance (instead of the worst case) and thus is much lower in average.",

keywords = "Gr{\"o}bner basis, ideal dimension, macaulay matrix, multivariate polynomial, polynomial ideal, s-criterion, space complexity",

author = "Mayr, {Ernst W.} and Stephan Ritscher",

year = "2011",

doi = "10.1145/1993886.1993926",

language = "English",

isbn = "9781450306751",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

pages = "257--264",

booktitle = "ISSAC 2011 - Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation",

note = "36th International Symposium on Symbolic and Algebraic Computation, ISSAC 2011 ; Conference date: 08-06-2011 Through 11-06-2011",

}