基于ZBDD的布尔多项式Gr(o)bner基算法的实现

摘要

As a rising data structure storing Boolean polynomial in recent years, ZBDD ( zero suppressed binary decision diagram) enables more efficient computing speed and more balanced memory consumption. The Grobner basis algorithm of Boolean polynomial based on it can maintain ZBDD structure unchanged soas to further enhance the efficiency of computations. In this paper, we use C ++ to achieve the Boolean polynomials Grt(o)bner-basis oomputation with the irreducibility processing on Gr(o)bner basis, and the feasibility of the algorithm as well as the improvement on efficiency of the oporations are verified as well.%零压缩二元判定树ZBDD(Zero-suppressed Binary Decision Diagrams)作为一种近年来兴起的存储布尔多项式的数据结构能更有效地平衡内存消耗与计算速度;基于它的布尔多项武Gr(O)bner基算法可以在运算中保持ZBDD结构的不变性从而进一步提高计算效率.用C++实现了布尔多项式的Gr(O)bner基计算并对其进行既约化处理,验证了该算法的可行性以及在运算效率上的提高.