Parallelization of Boolean Groebner Basis Algorithm

Varun Narayanan
Prahladh Harsha
Tuesday, 10 May 2016, 16:00 to 17:30
A-201 (STCS Seminar Room)
Groebner basis for a multivariate polynomial ideal is a finite basis of polynomials that has many useful properties. Large memory requirements and computation time for most practical problems hinder the use of Groebner basis in many areas. Distributing the memory over many cores will take care of the large memory requirements of the algorithm. In this talk we discuss one approach to parallel implementation of Buchberger's algorithm for computing the basis for boolean polynomials with efficient memory usage without considering the computation time. We propose improvements on the data structure, Zero Suppressed Decision Diagram, to facilitate efficient storage as well as communication of polynomials among multiple cores. The code is implemented using OpenMPI in C++ and is compared with PolyBoRi package in Sage.