On efficiency of involutive criteria in computing Boolean Groebner bases
Gerdt V.P., Zinin M.V.
Laboratory of Information Technologies
Joint Institute for Nuclear Research
141980 Dubna, Russia
Email: gerdt@jinr.ru mzinin@gmail.com
Abstract
In our paper [1] we presented an involutive algorithm based on the Pommaret division for
construction of Boolean Groebner bases. That algorithm does not use any criteria to avoid
useless reductions. In the present talk we modify the algorithm by inclusion four involutive
criteria which in the aggregate are equivalent [2] to the Buchberger criteria. Our
experimental study of computational efficiency of the criteria shows that they are of less
importance in comparison to the involutive basis computation in commutative polynomial rings
[3]. As this takes place, we reveal that application of the 2nd and/or 3rd criterion is
heuristically more important in Boolean rings then that of the other two criteria.
[1] V.P.Gerdt and M.V. Zinin. A Pommaret Division Algorithm for Computing Groebner Bases in
Boolean Rings. Proceedings of ISSAC 2008, to appear.
[2] J.Apel and R.Hemmecke. Detecting unnecessary reductions in an involutive basis
computation. Journal of Symbolic Computation, 40(4-5): 1131--1149, 2005.
[3] V.P.Gerdt and D.A.Yanovich. Effectiveness of Involutive Criteria in Computation of
Polynomial Janet Bases. Programming and Computer Software, 32(3): 134—138, 2006