PARALLEL COMPUTATION OF GROBNER BASES ON DISTRIBUTED-MEMORY MACHINES

This paper reports our work on parallelizing an algorithm computing Gr obner bases on a distributed memory parallel machine. When computing G robner bases, the efficiency of computation is dominated by the total number of S-polynomials. To decrease the total number of S-polynomials it is necessary to apply a selection strategy that selects the minimu m polynomial as a new element of an intermediate base. On a distribute d memory parallel machine, as opposed to a shared memory parallel mach ine, we have to take into account non-trivial communication costs betw een processors. To reduce such communication costs, it is better to em ploy coarse grained parallelism rather than fine grained parallelism. We adopt a manager-worker model. S-polynomials are reduced in worker p rocesses in parallel, and the minimum polynomial is selected in the ma nager process. To implement the selection strategy in this parallel mo del, synchronization between worker processes is required for every se lection of a new element of the intermediate base. However, in spite o f synchronization, introducing the selection strategy produces not onl y a better absolute computation speed but also better speedup with mul ti-processors. We achieved about 8 times speedup with 64 processors fo r large problems, T-6 and Ex-17.