A parallel implementation of the cylindrical algebraic decomposition algorithm

ABSTRACT

In this paper, we describe a parallelization scheme for Collins' cylindrical algebraic decomposition algorithm for quantifier elimination in the theory of real closed fields. We first discuss a parallel implementation of the computer algebra system SAC2 in which a complete sequential implementation of Collins' algorithm already exists. We report some initial results on the speedup obtained, drawing on a suite of examples previously given by Arnon.

REFERENCES

• 1: Dennis S. Arnon, Topologically reliable display of algebraic curves, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.219-227, July 25-29, 1983, Detroit, Michigan, United States
• 2: Dennis S. Arnon, Bibliography of quantifier elimination for real closed fields, Journal of Symbolic Computation, v.5 n.1-2, p.267-274, February/April 1988 [doi>10.1016/S0747-7171(88)80016-6]
• 3: Dennis S. Arnon, A cluster-based cylindrical algebraic decomposition algorithm, Journal of Symbolic Computation, v.5 n.1-2, p.189-212, February/April 1988 [doi>10.1016/S0747-7171(88)80012-9]
• 4: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
• 5: Dennis S. Arnon , Maurice Mignotte, On mechanical quantifier elimination for elementary algebra and geometry, Journal of Symbolic Computation, v.5 n.1-2, p.237-259, February/April 1988 [doi>10.1016/S0747-7171(88)80014-2]
• 6: Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
• 7: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• 8: Carriero, N., Gelernter, D.: "How to write parallel programs--A guide to the perplexed", Comp. Sci. Tech Report No. DCS/RR-628, Yale University (May 1988)
• 9: Collins, G.: "Quantifier elimination for real closed fields by cylindrical algebraic decomposition", Lecture Notes in Computer Science, 33, Springerverlag, 134-183. (1975)
• 10: Dershowitz, N.: "A note on simplification orderings", Info. Proc. Letters, 9, 212-215. (1979)
• 11: Johnson, J.: Some Issues i~ Designing Alegbraic Algorithms for the CRAY X-MP, Master's thesis, Univ. Delaware, Newark, DE. (1987)
• 12: Kahn, P. J.: "Counting types of rigid frameworks", Inventiones Math., 55, 297-308. (1979)
• 13: Kozen, D., Yap, C-K.: "Algebraic cell decomposition'', FOCS 87, 515-521. (October 1987)
• 14: Renegar, J.: "A faster PSPACE algorithm for deciding the existential theory of the reals", FOCS 88, 291-295. (October 1988)
• 15: Schwartz, J., Sharir, M.: "On the 'Piano Movers' problem II: General techniques for computing topological properties of real algebraic manifolds", A dvauces in Appl. Math., 4,298-351. (1983)",
• 16: Sequent Computer Co.: A Guide to Parallel Programming, 2nd ed., Beaverton, OR. (1987)
• 17: Tarski, A.: A decision method for elementary algebra and geometry (2nd ed.), UC Berkeley Press, Berkeley ( 1951)

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory