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