On the Correctness of a Distributed Memory
Grobner Basis Algorithm
Soumen Chakrabarti and Katherine Yelick
We present an asynchronous MIMD algorithm for Grobner basis
computation. The algorithm is based on the well-known 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.