A geometric approach to cylindrical algebraic decomposition

Chen, Rizeng

doi:10.1090/mcom/4099

A geometric approach to cylindrical algebraic decomposition
HTML articles powered by AMS MathViewer

by Rizeng Chen;

Math. Comp.

DOI: https://doi.org/10.1090/mcom/4099

Published electronically: June 3, 2025

PDF | Request permission

Abstract:

Cylindrical algebraic decomposition is a classical construction in real algebraic geometry. Although there are many algorithms to compute a cylindrical algebraic decomposition, their practical performance is still very limited. In this paper, we revisit this problem from a more geometric perspective, where the construction of cylindrical algebraic decomposition is related to the study of morphisms between real varieties. It is showed that the geometric fiber cardinality (geometric property) decides the existence of semi-algebraic continuous sections (semi-algebraic property). As a result, all equations can be systematically exploited in the projection phase, leading to a new simple algorithm whose efficiency is demonstrated by experimental results.

References

Dennis S. Arnon, George E. Collins, and Scott McCallum, Cylindrical algebraic decomposition. I. The basic algorithm, SIAM J. Comput. 13 (1984), no. 4, 865–877. MR 764184, DOI 10.1137/0213054
Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509, DOI 10.1007/978-3-662-03718-8
Christopher W. Brown and James H. Davenport, The complexity of quantifier elimination and cylindrical algebraic decomposition, ISSAC 2007, ACM, New York, 2007, pp. 54–60. MR 2396184, DOI 10.1145/1277548.1277557
Eberhard Becker, Sums of squares and quadratic forms in real algebraic geometry, De la géométrie algébrique réelle (Paris, 1990) Cahiers Sém. Hist. Math. Sér. 2, vol. 1, Univ. Paris VI, Paris, 1991, pp. 41–57. MR 1122204
Göran Björck and Ralf Fröberg, A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic $n$-roots, J. Symbolic Comput. 12 (1991), no. 3, 329–336. MR 1128248, DOI 10.1016/S0747-7171(08)80153-8
Magali Bardet, Jean-Charles Faugère, and Bruno Salvy, On the complexity of the $F_5$ Gröbner basis algorithm, J. Symbolic Comput. 70 (2015), 49–70. MR 3320794, DOI 10.1016/j.jsc.2014.09.025
B. Buchberger and H. Hong, Speeding-Up Quantifier Elimination by Gröbner Bases. Citeseer, 1991.
Christopher W. Brown and Scott McCallum, On using bi-equational constraints in CAD construction, ISSAC’05, ACM, New York, 2005, pp. 76–83. MR 2280532, DOI 10.1145/1073884.1073897
Michael Ben-Or, Dexter Kozen, and John Reif, The complexity of elementary algebra and geometry, J. Comput. System Sci. 32 (1986), no. 2, 251–264. 16th annual ACM-SIGACT symposium on the theory of computing (Washington, D.C., 1984). MR 851192, DOI 10.1016/0022-0000(86)90029-2
Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. MR 2248869
Christopher W. Brown, Improved projection for cylindrical algebraic decomposition, J. Symbolic Comput. 32 (2001), no. 5, 447–465. MR 1858003, DOI 10.1006/jsco.2001.0463
C. W. Brown, QEPCAD B: a program for computing with semi-algebraic sets using CADs, ACM Sigsam Bulletin 37 (2003), no. 4, 97–108.
B. Buchberger, Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, Ph. D. Thesis, Math. Inst., University of Innsbruck, 1965.
Eberhard Becker and Thorsten Wöermann, On the trace formula for quadratic forms, Recent advances in real algebraic geometry and quadratic forms (Berkeley, CA, 1990/1991; San Francisco, CA, 1991) Contemp. Math., vol. 155, Amer. Math. Soc., Providence, RI, 1994, pp. 271–291. MR 1260713, DOI 10.1090/conm/155/01385
David A. Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, 4th ed., Undergraduate Texts in Mathematics, Springer, Cham, 2015. An introduction to computational algebraic geometry and commutative algebra. MR 3330490, DOI 10.1007/978-3-319-16721-3
Changbo Chen and Marc Moreno Maza, Cylindrical algebraic decomposition in the RegularChains library, Mathematical software—ICMS 2014, Lecture Notes in Comput. Sci., vol. 8592, Springer, Heidelberg, 2014, pp. 425–433. MR 3334799, DOI 10.1007/978-3-662-44199-2_{6}5
C. Chen and M. Moreno Maza, An incremental algorithm for computing cylindrical algebraic decompositions, In Computer Mathematics: 9th Asian Symposium (ASCM2009), Fukuoka, December 2009, 10th Asian Symposium (ASCM2012), Beijing, October 2012, Contributed Papers and Invited Talks, Springer, 2014, pp. 199–221.
Changbo Chen, Marc Moreno Maza, Bican Xia, and Lu Yang, Computing cylindrical algebraic decomposition via triangular decomposition, ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 95–102. MR 2742696, DOI 10.1145/1576702.1576718
George E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975) Lecture Notes in Comput. Sci., Vol. 33, Springer, Berlin-New York, 1975, pp. 134–183. MR 403962
George E. Collins, Quantifier elimination by cylindrical algebraic decomposition—twenty years of progress, Quantifier elimination and cylindrical algebraic decomposition (Linz, 1993) Texts Monogr. Symbol. Comput., Springer, Vienna, 1998, pp. 8–23. MR 1634188, DOI 10.1007/978-3-7091-9459-1_{2}
David A. Cox, Stickelberger and the eigenvalue theorem, Commutative algebra, Springer, Cham, [2021] ©2021, pp. 283–298. MR 4394411, DOI 10.1007/978-3-030-89694-2_{8}
James H. Davenport and Joos Heintz, Real quantifier elimination is doubly exponential, J. Symbolic Comput. 5 (1988), no. 1-2, 29–35. MR 949111, DOI 10.1016/S0747-7171(88)80004-X
Matthew England, Russell Bradford, and James H. Davenport, Improving the use of equational constraints in cylindrical algebraic decomposition, ISSAC’15—Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2015, pp. 165–172. MR 3388296
Matthew England, Russell Bradford, and James H. Davenport, Cylindrical algebraic decomposition with equational constraints, J. Symbolic Comput. 100 (2020), 38–71. MR 4079042, DOI 10.1016/j.jsc.2019.07.019
David Eisenbud and Joe Harris, The geometry of schemes, Graduate Texts in Mathematics, vol. 197, Springer-Verlag, New York, 2000. MR 1730819
David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960, DOI 10.1007/978-1-4612-5350-1
Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero $(F_5)$, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. MR 2035234, DOI 10.1145/780506.780516
J.-C. Faugère, Fgb: a library for computing Gröbner bases, In International Congress on Mathematical Software, Springer, 2010, pp. 84–87.
Ryoya Fukasaku, Hidenao Iwane, and Yosuke Sato, Real quantifier elimination by computation of comprehensive Gröbner systems, ISSAC’15—Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2015, pp. 173–180. MR 3388297
Gert-Martin Greuel and Gerhard Pfister, A Singular introduction to commutative algebra, Second, extended edition, Springer, Berlin, 2008. With contributions by Olaf Bachmann, Christoph Lossen and Hans Schönemann; With 1 CD-ROM (Windows, Macintosh and UNIX). MR 2363237
A. Grothendieck, Éléments de géométrie algébrique. IV. Étude locale des schémas et des morphismes de schémas. II, Inst. Hautes Études Sci. Publ. Math. 24 (1965), 231 (French). MR 199181
A. Grothendieck, Éléments de géométrie algébrique. IV. Étude locale des schémas et des morphismes de schémas. III, Inst. Hautes Études Sci. Publ. Math. 28 (1966), 255. MR 217086
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 463157
Z. Huang, M. England, J. H. Davenport, and L. C. Paulson, Using machine learning to decide when to precondition cylindrical algebraic decomposition with Groebner bases, In 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), IEEE, 2016, pp. 45–52.
H. Hong, An improvement of the projection operator in cylindrical algebraic decomposition, In Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1990, pp. 261–264.
H. Hong, Comparison of Several Decision Algorithms for the Existential Theory of the Reals, Citeseer, 1991.
Wolfram Research, Inc. Mathematica, Version 13.3, Champaign, IL, 2023.
Michael Kalkbrener, On the stability of Gröbner bases under specializations, J. Symbolic Comput. 24 (1997), no. 1, 51–58. MR 1459670, DOI 10.1006/jsco.1997.0113
Gregor Kemper, A course in commutative algebra, Graduate Texts in Mathematics, vol. 256, Springer, Heidelberg, 2011. MR 2766370, DOI 10.1007/978-3-642-03545-6
Y. N. Lakshman, A single exponential bound on the complexity of computing Gröbner bases of zero-dimensional ideals, Effective methods in algebraic geometry (Castiglioncello, 1990) Progr. Math., vol. 94, Birkhäuser Boston, Boston, MA, 1991, pp. 227–234. MR 1106425
D. Lazard, An improved projection for cylindrical algebraic decomposition, Algebraic geometry and its applications (West Lafayette, IN, 1990) Springer, New York, 1994, pp. 467–476. MR 1272048
Qing Liu, Algebraic geometry and arithmetic curves, Oxford Graduate Texts in Mathematics, vol. 6, Oxford University Press, Oxford, 2002. Translated from the French by Reinie Erné; Oxford Science Publications. MR 1917232
Y. N. Lakshman and Daniel Lazard, On the complexity of zero-dimensional algebraic systems, Effective methods in algebraic geometry (Castiglioncello, 1990) Progr. Math., vol. 94, Birkhäuser Boston, Boston, MA, 1991, pp. 217–225. MR 1106424
Huu Phuoc Le and Mohab Safey El Din, Solving parametric systems of polynomial equations over the reals through Hermite matrices, J. Symbolic Comput. 112 (2022), 25–61. MR 4357373, DOI 10.1016/j.jsc.2021.12.002
Dong Lu, Yao Sun, and Dingkang Wang, A survey on algorithms for computing comprehensive Gröbner systems and comprehensive Gröbner bases, J. Syst. Sci. Complex. 32 (2019), no. 1, 234–255. MR 3913945, DOI 10.1007/s11424-019-8357-z
Frédéric Mangolte, Real algebraic varieties, Springer Monographs in Mathematics, Springer, Cham, [2020] ©2020. Translated from the 2017 French original [ 3727103] by Catriona Maclean. MR 4179588, DOI 10.1007/978-3-030-43104-4
Ernst Mayr, Membership in polynomial ideals over ${\scr Q}$ is exponential space complete, STACS 89 (Paderborn, 1989) Lecture Notes in Comput. Sci., vol. 349, Springer, Berlin, 1989, pp. 400–406. MR 1027419, DOI 10.1007/BFb0029002
Scott McCallum and Christopher W. Brown, On delineability of varieties in CAD-based quantifier elimination with two equational constraints, ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 71–78. MR 2742693, DOI 10.1145/1576702.1576715
Scott McCallum, An improved projection operation for cylindrical algebraic decomposition of three-dimensional space, J. Symbolic Comput. 5 (1988), no. 1-2, 141–161. MR 949117, DOI 10.1016/S0747-7171(88)80010-5
Scott McCallum, An improved projection operation for cylindrical algebraic decomposition, Quantifier elimination and cylindrical algebraic decomposition (Linz, 1993) Texts Monogr. Symbol. Comput., Springer, Vienna, 1998, pp. 242–268. MR 1634198
Scott McCallum, On projection in CAD-based quantifier elimination with equational constraint, Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (Vancouver, BC), ACM, New York, 1999, pp. 145–149. MR 1802078, DOI 10.1145/309831.309892
Scott McCallum, On propagation of equational constraints in CAD-based quantifier elimination, Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2001, pp. 223–230. MR 2049752, DOI 10.1145/384101.384132
Ernst W. Mayr and Albert R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math. 46 (1982), no. 3, 305–329. MR 683204, DOI 10.1016/0001-8708(82)90048-2
Scott McCallum, Adam Parusiński, and Laurentiu Paunescu, Validity proof of Lazard’s method for CAD construction, J. Symbolic Comput. 92 (2019), 52–69. MR 3907347, DOI 10.1016/j.jsc.2017.12.002
Ernst W. Mayr and Stephan Ritscher, Degree bounds for Gröbner bases of low-dimensional polynomial ideals, ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2010, pp. 21–27. MR 2920532, DOI 10.1145/1837934.1837945
Ernst W. Mayr and Stephan Ritscher, Dimension-dependent bounds for Gröbner bases of polynomial ideals, J. Symbolic Comput. 49 (2013), 78–94. MR 2997841, DOI 10.1016/j.jsc.2011.12.018
Paul Christian Pedersen, Counting real zeros, ProQuest LLC, Ann Arbor, MI, 1991. Thesis (Ph.D.)–New York University. MR 2686451
Daniel Perrucci and Marie-Françoise Roy, Elementary recursive quantifier elimination based on Thom encoding and sign determination, Ann. Pure Appl. Logic 168 (2017), no. 8, 1588–1604. MR 3650356, DOI 10.1016/j.apal.2017.03.001
P. Pedersen, M.-F. Roy, and A. Szpirglas, Counting real zeros in the multivariate case, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 203–224. MR 1230868, DOI 10.1007/978-1-4612-2752-6_{1}5
Claus Scheiderer, A course in real algebraic geometry—positivity and sums of squares, Graduate Texts in Mathematics, vol. 303, Springer, Cham, [2024] ©2024. MR 4824192, DOI 10.1007/978-3-031-69213-0
Günter Scheja and Uwe Storch, Lehrbuch der Algebra. Teil 2, Mathematische Leitfäden. [Mathematical Textbooks], B. G. Teubner, Stuttgart, 1988 (German). Unter Einschluss der linearen Algebra. [Including linear algebra]. MR 934019, DOI 10.1007/978-3-322-80092-3
Akira Suzuki and Josuke Sato, A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases, ISSAC 2006, ACM, New York, 2006, pp. 326–331. MR 2289138, DOI 10.1145/1145768.1145821
Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley-Los Angeles, Calif., 1951. 2nd ed. MR 44472
Wolmer V. Vasconcelos, Flatness testing and torsionfree morphisms, J. Pure Appl. Algebra 122 (1997), no. 3, 313–321. MR 1481094, DOI 10.1016/S0022-4049(97)00062-5
D. Wilson, R. Bradford, and J. H. Davenport, Speeding up cylindrical algebraic decomposition by Gröbner bases, In International Conference on Intelligent Computer Mathematics, Springer, 2012, 280–294.
Dongming Wang, Rina Dong, and Chenqi Mou, Decomposition of polynomial sets into characteristic pairs, Math. Comp. 89 (2020), no. 324, 1993–2015. MR 4081926, DOI 10.1090/mcom/3504
Volker Weispfenning, The complexity of linear problems in fields, J. Symbolic Comput. 5 (1988), no. 1-2, 3–27. MR 949110, DOI 10.1016/S0747-7171(88)80003-8
Volker Weispfenning, Comprehensive Gröbner bases, J. Symbolic Comput. 14 (1992), no. 1, 1–29. MR 1177987, DOI 10.1016/0747-7171(92)90023-W
V. Weispfenning, A new approach to quantifier elimination for real algebra, Quantifier elimination and cylindrical algebraic decomposition (Linz, 1993) Texts Monogr. Symbol. Comput., Springer, Vienna, 1998, pp. 376–392. MR 1634206

AMS Website Down

Mathematics of Computation

A geometric approach to cylindrical algebraic decomposition
HTML articles powered by AMS MathViewer

Abstract: