Strategy-Accurate Parallel Buchberger Algorithms. - Attardi, Giuseppe (Journal of symbolic computation.)
We describe two parallel versions of the Buchberger algorithm for computing Gröbner bases, one for the general case and one for homogeneous ideals, which exploit coarse grain parallelism. For the general case, to avoid the growth in number and complexity of the polynomials to reduce, the algorithm adheres strictly to the same strategies as the best sequential implementation. A suitable communication procotol has been designed to ensure proper synchronization of the various processes and to limit their idle time. We provide a detailed analysis the maximum potential degree of parallelism that is achievable with such architecture. The analysis corresponds to the results of our experimental implementation and also explains similar results obtained by other authors.