Abstract
We present an asynchronous MIMD algorithm for Gröbner 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.
This work was supported in part by the Advanced Research Projects Agency of the Department of Defense monitored by the Office of Naval Research under contract DABT63-92-C-0026, by AT&T, and by a National Science Foundation through an Infrastructure Grant (number CDA-8722788) and Research Initiation Award (number CCR-9210260). The information presented here does not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Attardi and C. Traverso. A Network Implementation of Buchberger Algorithm. Technical Report 1177, University di Pisa, January 1991.
L. Bachmair, N. Dershowitz, and J. Hsiang. Orderings for Equational Proofs. In Proceedings of the Symposium on Logic in Computer Science, pages 346–357. IEEE, 1986.
M. P. Bonacina. Distributed Automated Deduction. PhD thesis, Department of Computer Science, SUNY at Stony Brook, December 1992.
B. Buchberger. Gröbner basis: an algorithmic method in polynomial ideal theory. In N. K. Bose, editor, Multidimensional Systems Theory, chapter 6, pages 184–232. D. Reidel Publishing Company, 1985.
B. Buchberger. A Criterion for detecting Unnecessary Reductions in the construction of Gröbner Bases. In Proceedings of the EUROSAM '79, An International Symposium on Symbolic and Algebraic Manipulation, pages 3–21, Marseille, France, June 1979.
N. J. Burnett. The Architecture of the CM-5. In IEEE Colloquium on ”Medium Grain Distributed Computing” (Digest 070), pages 1–2, London, 26 March 1992.
S. Chakrabarti. A distributed memory Gröbner basis algorithm. Master's thesis, University of California, Berkeley, December 1992.
S. Chakrabarti and K. Yelick. Implementing an Irregular Application on a Distributed Memory Multiprocessor. In Principles and Practices of Parallel Programming, May 1993.
K. M. Chandy and J. Misra. Parallel Program Design: a Foundation. Addison-Wesley Publishing Company, Reading, Mass., 1988.
N. Dershowitz and Z. Manna. Proving Termination with Multiset Orderings. Communications of the ACM, 22: 465–476, 1979.
E. W. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976.
A. Giovini, T. Mora, G. Niesi, L. Robbiano, and C. Traverse. “One sugar cube, please” OR Selection strategies in the Buchberger algorithm. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, pages 49–54, Bonn, Germany, 15–17 July 1992.
D. J. Hawley. A Buchberger algorithm for Distributed Memory Multi-processors. In Proceedings of the 1st International ACPC Conference on Parallel Computation, pages 385–390, Salzburg, Austria, 30 September–2 October 1991. Springer-Verlag.
B. Mishra and C. Yap. Notes on Gröbner basis. In Information Sciences 48, pages 219–252. Elsevier Science Publishing Company, 1989.
Nathan Jacobson. Basic Algebra — Volume 2. W. H. Freeman and Company, New York, 1989.
C. G. Ponder. Evaluation of “performance enhancements” in algebraic manipulation systems. Technical Report UCB/CSD 88/438, University of California, Berkeley, 1988. Chapter 7, Parallel Algorithms for Gröbner Basis Reduction.
K. Siegl. Parallel Gröbner basis computation in ∥MAPLE∥. Technical Report 92-11, Research Institute for Symbolic Computation, Linz, Austria, 1992.
J. K. Slaney and E. W. Lusk. Parallelizing the Closure Computation in Automated Deduction. In Proceedings of the 10th International Conference on Automated Deduction, pages 28–29. Springer-Verlag, LNCS 449, 1990.
J.-P. Vidal. The computation of Gröbner bases on a shared memory multiprocessor. Technical Report CMU-CS-90-163, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, 1990.
T. von Eicken, D. E. Culler, S. C. Goldstein, and K. E. Schauser. Active messages: A mechanism for integrated communication and computation. In Proceedings of the 19th Annual International Symposium on Computer Architecture, pages 256–266, 1992.
K. Yelick. Using abstraction in explicitly parallel programs. Technical Report MIT/LCS/TR-507, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, July 1991.
K. A. Yelick and S. J. Garland. A parallel completion procedure for term rewriting systems. In Conference on Automated Deduction, Saratoga Springs, NY, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chakrabarti, S., Yelick, K. (1993). On the correctness of a distributed memory Gröbner basis algorithm. In: Kirchner, C. (eds) Rewriting Techniques and Applications. RTA 1993. Lecture Notes in Computer Science, vol 690. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-21551-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-662-21551-7_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56868-1
Online ISBN: 978-3-662-21551-7
eBook Packages: Springer Book Archive