×

zbMATH — the first resource for mathematics

On using Lazard’s projection in CAD construction. (English) Zbl 1325.13026
The concept of cylindrical algebraic decomposition (CAD) of the Euclidean \(n\)-space \(E^n\) has been introduced by G. E. Collins in [Lect. Notes Comput. Sci. 33, 134–183 (1975; Zbl 0318.02051)]. It is closely related to the classical simplicial and CW-complexes of algebraic topology and has several applications. Given a finite set \(A\) of \(n\)-variate integral polynomials, a CAD is \(A\)-invariant if the polynomials of \(A\) are sign-invariant in each of the regions of the decomposition. The definition of CAD is based on a sort of induction on the dimension of the Euclidean space and a key point for \(A\)-invariant CAD construction is the choice of a projection of the polynomials of \(A\), i.e. a certain set of \((n-1)\)-variate integral polynomials.
This paper is devoted to the investigation of \(A\)-invariant CAD construction focusing on the projection proposed by D. Lazard [in: Algebraic geometry and its applications. Collections of papers from Shreeram S. Abhyankar’s 60th birthday conference held at Purdue University, West Lafayette, IN, USA, June 1-4, 1990. New York: Springer-Verlag. 467–476 (1994; Zbl 0822.68118)], whose proof presented some flaws. Despite these flaws, the authors show that Lazard’s projection \(P_L(A)\) is valid when the set \(A\) is well-oriented with respect to \(P_L(A)\) (see Definition 3.4).
In Section 2, the authors analyze the flaws of Lazard’s projection and compare it with the projection introduced by S. McCallum [J. Symb. Comput. 5, No. 1–2, 141–161 (1988; Zbl 0648.68054); in: Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6–8, 1993. Wien: Springer. 242–268 (1998; Zbl 0900.68279)] and with the Brown-McCallum projection [C. W. Brown, J. Symb. Comput. 32, No. 5, 447–465 (2001; Zbl 0981.68186)], motivating the interest for a reinstatement of Lazard’s method with several arguments (e.g., see Remark 3.2 and Section 4).
Section 3 contains the main result (Theorem 3.1) which leads to the development of a CAD algorithm using Lazard’s projection (Section 3.2). The rest of Section 3 is devoted to the proof of the main result, especially to the study of a technical lemma (Lemma 3.12) obtained as a consequence of an important theorem of Abhyankar and Jung to which a final Appendix is also devoted.

MSC:
13P05 Polynomials, factorization in commutative rings
68W30 Symbolic computation and algebraic computation
03G15 Cylindric and polyadic algebras; relation algebras
14Q99 Computational aspects in algebraic geometry
Software:
QEPCAD
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Abhyankar, S. S., On the ramification of algebraic functions, Am. J. Math., 77, 575-592, (1955) · Zbl 0064.27501
[2] Abhyankar, S. S., Algebraic geometry for scientists and engineers, (1990), American Math. Society Providence · Zbl 0709.14001
[3] Arnon, D. S.; Collins, G. E.; McCallum, S., Cylindrical algebraic decomposition I: the basic algorithm, SIAM J. Comput., 13, 865-877, (1984) · Zbl 0562.14001
[4] Arnon, D. S.; Collins, G. E.; McCallum, S., Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM J. Comput., 13, 878-889, (1984) · Zbl 0562.14001
[5] Benedetti, R.; Risler, J.-J., Algebraic and semi-algebraic sets, (1990), Hermann Paris · Zbl 0694.14006
[6] Black, C. W.M., The parametric representation of the neighborhood of a singular point of an analytic surface, Proc. Am. Acad. Arts Sci., 37, 281-330, (1902) · JFM 33.0656.02
[7] Bradford, R.; Davenport, J. H.; England, M.; McCallum, S.; Wilson, D., Cylindrical algebraic decompositions for Boolean combinations, (Kauers, M., Proceedings of the 2013 International Symposium on Symbolic and Algebraic Computation, ISSAC’13, (2013), ACM New York), 125-132 · Zbl 1359.68327
[8] Brown, C. W., Simplification of truth-invariant cylindrical algebraic decompositions, (Gloor, O., Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, ISSAC’98, (1998), ACM New York), 295-301 · Zbl 0918.68058
[9] Brown, C. W., Improved projection for cylindrical algebraic decomposition, J. Symb. Comput., 32, 447-465, (2001) · Zbl 0981.68186
[10] Collins, G. E., (Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition, Lect. Notes Comput. Sci., vol. 33, (1975), Springer-Verlag Berlin), 134-183
[11] Collins, G. E., Quantifier elimination by cylindrical algebraic decomposition - twenty years of progress, (Caviness, B. F.; Johnson, J. R., Quantifier Elimination and Cylindrical Algebraic Decomposition, (1998), Springer-Verlag Vienna), 8-23 · Zbl 0900.03053
[12] Collins, G. E.; Hong, H., Partial cylindrical algebraic decomposition for quantifier elimination, J. Symb. Comput., 12, 299-328, (1991) · Zbl 0754.68063
[13] Hensel, K., Ueber eine neue theorie der algebraischen funktionen zweier variablen, Acta Math., 23, 339-416, (1900) · JFM 31.0424.02
[14] Hong, H., An improvement of the projection operator in cylindrical algebraic decomposition, (Watanabe, S.; Nagata, M., Proceedings of the 1990 International Symposium on Symbolic and Algebraic Computation, ISSAC’90, (1990), ACM New York), 261-264
[15] Jung, H. W.E., Darstellung der funktionen eines algebraischen koerpers zweier unabhaengigen veraenderlichen x,y in der umgebung einer stelle x=a, y=b, J. Reine Angew. Math., 133, 289-314, (1908) · JFM 39.0493.01
[16] Kiyek, K.; Vicente, J. L., On the jung-abhyankar theorem, Arch. Math. (Basel), 83, 123-134, (2004) · Zbl 1085.13009
[17] Kobb, G., Sur la theorie des fonctions algebrique de deux variables, J. Math. Pures Appl. IV, 8, 385-412, (1892) · JFM 24.0376.01
[18] Lazard, D., An improved projection for cylindrical algebraic decomposition, (Baja, C. L., Algebraic Geometry and Its Applications, (1994), Springer-Verlag New York) · Zbl 0822.68118
[19] Luengo, I., A new proof of the jung-abhyankar theorem, J. Algebra, 85, 399-409, (1983) · Zbl 0528.13019
[20] McCallum, S., An improved projection operation for cylindrical algebraic decomposition, (1984), University of Wisconsin-Madison, PhD thesis
[21] McCallum, S., An improved projection operation for cylindrical algebraic decomposition of three-dimensional space, J. Symb. Comput., 5, 141-161, (1988) · Zbl 0648.68054
[22] McCallum, S., An improved projection operation for cylindrical algebraic decomposition, (Caviness, B. F.; Johnson, J. R., Quantifier Elimination and Cylindrical Algebraic Decomposition, (1998), Springer-Verlag Vienna), 242-268 · Zbl 0900.68279
[23] McCallum, S., On projection in CAD-based quantifier elimination with equational constraint, (Dooley, S., Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC’99, (1999), ACM New York), 145-149
[24] McCallum, S., On propagation of equational constraints in CAD-based quantifier elimination, (Mourrain, B., Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, ISSAC’01, (2001), ACM New York), 223-230 · Zbl 1356.68287
[25] McCallum, S.; Hong, H., On Lazard’s valuation and CAD construction, (2015)
[26] Parusinski, A.; Rond, G., The abhyankar-jung theorem, J. Algebra, 365, 29-41, (2012) · Zbl 1268.13008
[27] Walker, R. J., Algebraic curves, (1978), Springer-Verlag New York
[28] Whitney, H., Complex analytic varieties, (1972), Addison-Wesley Menlo Park · Zbl 0265.32008
[29] Zariski, O., Algebraic surfaces, (1935), Springer-Verlag New York, Heidelberg, Berlin · JFM 61.0704.01
[30] Zariski, O., On equimultiple subvarieties of algebroid hypersurfaces, Proc. Natl. Acad. Sci. USA, 72, 1425-1426, (1975) · Zbl 0304.14008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.