Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Cylindrical algebraic decomposition is one of the most important tools for computing with semi-algebraic sets, while triangular decomposition is among the most important approaches for manipulating constructible sets. In this paper, for an arbitrary finite set F ⊂ [y₁,...,y_n] we apply comprehensive triangular decomposition in order to obtain an F-invariant cylindrical decomposition of the n-dimensional complex space, from which we extract an F-invariant cylindrical algebraic decomposition of the n-dimensional real space. We report on an implementation of this new approach for constructing cylindrical algebraic decompositions.

REFERENCES

• 1: 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]
• 2: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 3: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: F. Boulier, F. Lemaire, and M. Moreno Maza. Well known theorems on triangular systems and the D5 principle. In Proc. of Transgressive Computing 2006, Granada, Spain, 2006.
• 5: Christopher W. Brown, Improved projection for cylindrical algebraic decomposition, Journal of Symbolic Computation, v.32 n.5, p.447-465, November 2001 [doi>10.1006/jsco.2001.0463]
• 6: Christopher W. Brown, Simple CAD construction and its applications, Journal of Symbolic Computation, v.31 n.5, p.521-547, May 2001 [doi>10.1006/jsco.2000.0394]
• 7: Christopher W. Brown , James H. Davenport, The complexity of quantifier elimination and cylindrical algebraic decomposition, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277557]
• 8: B. Caviness and J. Johnson, editors. Quantifier Elimination and Cylindical Algebraic Decomposition, Texts and Mongraphs in Symbolic Computation. Springer, 1998.
• 9: C. Chen, O. Golubitsky, F. Lemaire, M. Moreno Maza, and W. Pan. Comprehensive Triangular Decomposition, volume 4770 of LNCS, pages 73--101. Springer, 2007.
• 10: Jin-San Cheng , Xiao-Shan Gao , Chee-Keng Yap, Complete numerical isolation of real zeros in zero-dimensional triangular systems, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277562]
• 11: G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Springer Lecture Notes in Computer Science, 33:515--532, 1975.
• 12: George E. Collins , Hoon Hong, Partial cylindrical algebraic decomposition for quantifier elimination, Journal of Symbolic Computation, v.12 n.3, p.299-328, Sept. 1991 [doi>10.1016/S0747-7171(08)80152-6]
• 13: George E. Collins , Jeremy R. Johnson , Werner Krandick, Interval arithmetic in cylindrical algebraic decomposition, Journal of Symbolic Computation, v.34 n.2, p.145-157, August 2002 [doi>10.1006/jsco.2002.0547]
• 14: Xavier Dahan , Marc Moreno Maza , Eric Schost , Wenyuan Wu , Yuzhen Xie, Lifting techniques for triangular decompositions, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.108-115, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073901]
• 15: Andreas Dolzmann , Andreas Seidl , Thomas Sturm, Efficient projection orders for CAD, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.111-118, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005303]
• 16: A. Dolzmann, T. Sturm, and V. Weispfenning. Real quantifier elimination in practice. In Algorithmic Algebra and Number Theory, pages 221--247, 1998.
• 17: H. Hong, An improvement of the projection operator in cylindrical algebraic decomposition, Proceedings of the international symposium on Symbolic and algebraic computation, p.261-264, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96943]
• 18: Hoon Hong, Simple solution formula construction in cylindrical algebraic decomposition based quantifier elimination, Papers from the international symposium on Symbolic and algebraic computation, p.177-188, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143306]
• 19: É. Hubert. Notes on triangular sets and triangulation-decomposition algorithms. I. Polynomial systems. In Symbolic and numerical scientific computation (Hagenberg, 2001), volume 2630 of LNCS, pages 1--39. Springer, 2003.
• 20: F. Lemaire, M. Moreno Maza, and Y. Xie. The RegularChains library. In Ilias S. Kotsireas, editor, Maple Conference 2005, pages 355--368, 2005.
• 21: Xin Li , Marc Moreno Maza , Wei Pan, Computations modulo regular chains, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea [doi>10.1145/1576702.1576736]
• 22: X. Li, M. Moreno Maza, R. Rasheed, and É. Schost. The Modpn library: Bringing fast polynomial arithmetic into Maple. In Proc. MICA'08, 2008.
• 23: Xin Li , Marc Moreno Maza , Éric Schost, Fast arithmetic for triangular sets: from theory to practice, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277585]
• 24: Scott McCallum, An improved projection operation for cylindrical algebraic decomposition of three-dimensional space, Journal of Symbolic Computation, v.5 n.1-2, p.141-161, February/April 1988 [doi>10.1016/S0747-7171(88)80010-5]
• 25: S. McCallum. Solving polynomial strict inequalities using cylindrical algebraic decomposition. The Computer Journal, 36(5):432--438, 1993.
• 26: M. Moreno Maza. On triangular decompositions of algebraic varieties. Technical Report TR 4/99, NAG Ltd, Oxford, UK, 1999. Presented at the MEGA-2000 Conference, Bath, England.
• 27: Adam Strzeboński, Solving systems of strict polynomial inequalities, Journal of Symbolic Computation, v.29 n.3, p.471-480, March 2000 [doi>10.1006/jsco.1999.0327]
• 28: D. M. Wang. Elimination Methods. Springer, New York, 2000.
• 29: W. T. Wu. A zero structure theorem for polynomial equations solving. MM Research Preprints, 1:2--12, 1987.
• 30: Bican Xia , Lu Yang, An algorithm for isolating the real solutions of semi-algebraic systems, Journal of Symbolic Computation, v.34 n.5, p.461-477, November 2002 [doi>10.1006/jsco.2002.0572]
• 31: Bican Xia , Ting Zhang, Real solution isolation using interval arithmetic, Computers & Mathematics with Applications, v.52 n.6-7, p.853-860, September, 2006 [doi>10.1016/j.camwa.2006.06.003]
• 32: L. Yang, X. Hou, and B. Xia. A complete algorithm for automated discovering of a class of inequality--type theorems. Science in China, Series F, 44(6):33--49, 2001.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Theory

Keywords:
cad, regular chain, triangular decomposition