×

Open weak CAD and its applications. (English) Zbl 1410.68410

Summary: The concept of open weak CAD is introduced. Every open CAD is an open weak CAD. On the contrary, an open weak CAD is not necessarily an open CAD. An algorithm for computing projection polynomials of open weak CADs is proposed. The key idea is to compute the intersection of projection factor sets produced by different projection orders. The resulting open weak CAD often has smaller number of sample points than open CADs. The algorithm can be used for computing sample points for all open connected components of \(f \neq 0\) for a given polynomial \(f\). It can also be used for many other applications, such as testing semi-definiteness of polynomials and copositive problems. In fact, we solved several difficult semi-definiteness problems efficiently by using the algorithm. Furthermore, applying the algorithm to copositive problems, we find an explicit expression of the polynomials producing open weak CADs under some conditions, which significantly improves the efficiency of solving copositive problems.

MSC:

68W30 Symbolic computation and algebraic computation
14P05 Real algebraic sets
14Q10 Computational aspects of algebraic surfaces
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anai, H.; Weispfenning, V., Reach set computations using real quantifier elimination, (HSCC (2001)), 63-76 · Zbl 0991.93008
[2] Andersson, L.-E.; Chang, G.; Elfving, T., Criteria for copositive matrices using simplices and barycentric coordinates, Linear Algebra Appl., 220, 9-30 (1995) · Zbl 0826.15016
[3] Basu, S.; Pollack, R.; Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination, J. ACM, 43, 6, 1002-1045 (1996) · Zbl 0885.68070
[4] Basu, S.; Pollack, R.; Roy, M.-F., A new algorithm to find a point in every cell defined by a family of polynomials, (Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), Springer), 341-350 · Zbl 0900.68278
[5] Bochnak, J.; Coste, M.; Roy, M.-F., Real Algebraic Geometry, vol. 36 (2013), Springer Science & Business Media
[6] Brown, C., Improved projection for cylindrical algebraic decomposition, J. Symb. Comput., 32, 5, 447-465 (2001) · Zbl 0981.68186
[7] Chen, C.; Maza, M. M., Cylindrical algebraic decomposition in the regularchains library, (Mathematical Software - ICMS 2014. Mathematical Software - ICMS 2014, Lecture Notes in Computer Science, vol. 8592 (2014)), 425-433 · Zbl 1437.14007
[8] Collins, G. E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, (Automata Theory and Formal Languages. Automata Theory and Formal Languages, 2nd GI Conference Kaiserslautern, May 20-23 (1975), Springer), 134-183
[9] Collins, G. E., Quantifier elimination by cylindrical algebraic decomposition—twenty years of progress, (Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), Springer), 8-23 · Zbl 0900.03053
[10] Collins, G. E.; Hong, H., Partial cylindrical algebraic decomposition for quantifier elimination, J. Symb. Comput., 12, 3, 299-328 (1991) · Zbl 0754.68063
[11] Faugère, J.-C.; Moroz, G.; Rouillier, F.; El Din, M. S., Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities, (Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation (2008), ACM), 79-86 · Zbl 1487.68235
[12] Hadeler, K., On copositive matrices, Linear Algebra Appl., 49, 79-89 (1983) · Zbl 0506.15016
[13] Han, J., An Introduction to the Proving of Elementary Inequalities, vol. 123 (2011), Harbin Institute of Technology Press
[14] Han, J., Multivariate discriminant and iterated resultant, Acta Math. Sin. Engl. Ser., 32, 6, 659-667 (2016) · Zbl 1382.13004
[15] Han, J.; Dai, L.; Xia, B., Constructing fewer open cells by GCD computation in CAD projection, (Proc. ISSAC’2014 (2014), ACM), 240-247 · Zbl 1325.68286
[16] Han, J.; Jin, Z.; Xia, B., Proving inequalities and solving global optimization problems via simplified CAD projection, J. Symb. Comput., 72, 206-230 (2016) · Zbl 1337.90052
[17] Hiriart-Urruty, J.-B.; Seeger, A., A variational approach to copositive matrices, SIAM Rev., 52, 4, 593-629 (2010) · Zbl 1207.15037
[18] Hong, H., An improvement of the projection operator in cylindrical algebraic decomposition, (International Symposium of Symbolic and Algebraic Computation (ISSAC-90) (1990), ACM), 261-264
[19] Hong, H., Simple solution formula construction in cylindrical algebraic decomposition based quantifier elimination, (International Conference on Symbolic and Algebraic Computation ISSAC-92 (1992)), 177-188 · Zbl 0919.03029
[20] Hong, H.; Safey El Din, M., Variant quantifier elimination, J. Symb. Comput., 47, 7, 883-901 (Jul. 2012)
[21] Liska, R.; Steinberg, S., Applying quantifier elimination to stability analysis of difference schemes, Comput. J., 36, 5, 497-503 (1993) · Zbl 0780.68075
[22] McCallum, S., An improved projection operator for cylindrical algebraic decomposition (1984), University of Wisconsin-Madison, Ph.D. thesis
[23] McCallum, S., An improved projection operation for cylindrical algebraic decomposition of three-dimensional space, J. Symb. Comput., 5, 1, 141-161 (1988) · Zbl 0648.68054
[24] McCallum, S., An improved projection operation for cylindrical algebraic decomposition, (Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), Springer), 242-268 · Zbl 0900.68279
[25] McCallum, S., On projection in CAD-based quantifier elimination with equational constraint, (Proc. ISSAC (1999)), 145-149
[26] Murty, K. G.; Kabadi, S. N., Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39, 2, 117-129 (1987) · Zbl 0637.90078
[27] Parrilo, P. A., Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization (2000), CIT, Ph.D. thesis
[28] Renegar, J., On the computational complexity and geometry of the first order theory of the reals, J. Symb. Comput., 13, 3, 255-352 (1992) · Zbl 0798.68073
[29] Safey El Din, M., Testing sign conditions on a multivariate polynomial and applications, Math. Comput. Sci., 1, 1, 177-207 (2007) · Zbl 1126.14068
[30] Safey El Din, M.; Schost, É., Polar varieties and computation of one point in each connected component of a smooth real algebraic set, (Proc. ISSAC’2003 (2003), ACM), 224-231 · Zbl 1072.68693
[31] Strzeboński, A., Solving systems of strict polynomial inequalities, J. Symb. Comput., 29, 3, 471-480 (2000) · Zbl 0962.68183
[32] Strzebonski, A., Cylindrical algebraic decomposition using validated numerics, J. Symb. Comput., 41, 9, 1021-1038 (2006) · Zbl 1124.68123
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.