Search

Abstract: Buchberger’s Gröbner basis theory plays a fundamental role in symbolic computation. The resulting algorithms essentially carry out several -polynomial reductions. In his Ph.D. thesis and later publication Buchberger showed that sometimes one can skip -polynomial reductions if the leading terms of polynomials satisfy certain criteria. A question naturally arises: Are Buchberger’s criteria also necessary for skipping -polynomial reductions? In this paper, after making the question more precise (in terms of a chain condition), we show the answer to be “almost, but not quite”: necessary when there are four or more polynomials, but not necessary when there are exactly three polynomials. For that case, we found an extension to Buchberger’s criteria that is necessary as well as sufficient. [Copyright &y& Elsevier]

Abstract: We consider the check of the involutive basis property in a polynomial context. In order to show that a finite generating set of a polynomial ideal is an involutive basis one must confirm two properties. Firstly, the set of leading terms of the elements of has to be complete. Secondly, one has to prove that is a Gröbner basis of . The latter is the time critical part but can be accelerated by application of Buchberger’s criteria including the many improvements found during the last two decades. Gerdt and Blinkov [Gerdt, V.P., Blinkov, Y.A., 1998. Involutive bases of polynomial ideals. Mathematics and Computers in Simulation 45, 519–541] were the first who applied these criteria in involutive basis computations. We present criteria which are also transferred from the theory of Gröbner bases to involutive basis computations. We illustrate that our results exploit the Gröbner basis theory slightly more than those of Gerdt and Blinkov. Our criteria apply in all cases where those of Gerdt/Blinkov do, but we also present examples where our criteria are superior. Some of our criteria can also be used in algebras of solvable type, e.g., Weyl algebras or enveloping algebras of Lie algebras, in full analogy to the Gröbner basis case. We show that the application of criteria enforces the termination of the involutive basis algorithm independent of the prolongation selection strategy. [Copyright &y& Elsevier]