Details:
Title  On the Correctness of a Distributed Memory Gröbner Basis Algorithm  Author(s)  Soumen Chakrabarti, Katherine A. Yelick  Type  Technical Report, Misc  Abstract  We present an asynchronous MIMD algorithm for Gröbner basis computation. The algorithm is based on the wellknown sequential algorithm of Buchberger. Two factors make the correctness of our algorithm nontrivial: the nondeterminism that is inherent with asynchronous parallelism, and the distribution of data structures which leads to inconsistent views of the global state of the system. We demonstrate that by describing the algorithm as a nondeterministic sequential algorithm, and presenting the optimized parallel algorithm through a series of refinements to that algorithm, the algorithm is easier to understand and the correctness proof becomes manageable. The proof does, however, rely on algebraic properties of the polynomials in the computation, and does not follow directly from the proof of Buchberger's algorithm. 
Language  English  Year  1993  Edition  0  Translation 
No  Refereed 
No 
