Details:
Title  Parallel computation of Gröbner bases on distributed memory machines  Author(s)  Akira Aiba, Hiroyuki Sawada, Satoshi Terasaki  Type  Article in Journal  Abstract  This paper reports our work on parallelizing an algorithm computing Gröbner bases on a distributed memory parallel machine. When computing Gröbner bases, the efficiency of computation is dominated by the total number of Spolynomials. To decrease the total number of Spolynomials it is necessary to apply a selection strategy that selects the minimum polynomial as a new element of an intermediate base.
On a distributed memory parallel machine, as opposed to a shared memory parallel machine, we have to take into account nontrivial communication costs between processors. To reduce such communication costs, it is better to employ coarse grained parallelism rather than fine grained parallelism.
We adopt a managerworker model. Spolynomials are reduced in worker processes in parallel, and the minimum polynomial is selected in the manager process. To implement the selection strategy in this parallel model, synchronization between worker processes is required for every selection of a new element of the intermediate base. However, in spite of synchronization, introducing the selection strategy produces not only a better absolute computation speed but also better speedup with multiprocessors. We achieved about 8 times speedup with 64 processors for large problems, T6 and Ex17.  ISSN  07477171 
URL 
dx.doi.org/10.1006/jsco.1994.1045 
Language  English  Journal  Journal of Symbolic Computation  Volume  18  Number  3  Pages  207222  Publisher  Academic Press, Inc.  Address  Duluth, MN, USA  Year  1994  Month  September  Translation 
No  Refereed 
Yes 
