|Title||A Case Study of Multi-Threaded Gröbner Basis Completion|
|Type||Article in Conference Proceedings|
|Abstract||We investigate sources of parallelism in the Gröbner Basis algorithm|
for their practical use on the desk-top. Our execution environment is a standard multi-processor workstation, and our parallel programming environment is PARSAC-2 on top of a multi-threaded operating system. We investigate the performance of two main variants of our master parallel algorithm on a standard set of examples. The first version exploits only work parallelism in a strategy compliant way. The second version investigates search parallelism in addition, where large super-linear speedups can be obtained. These speedups are due to improved S-polynomial selection behavior and therefore carry over to single processor machines. Since we obtain our parallel variants by a controlled variation of only a few parameters in the master algorithm, we obtain new insights into the way in which different sources of parallelism interact in Gröbner Basis completion.
|Conferencename||ISSAC'96 (International Symposium on Symbolic and Algebraic Computation)|