Chen, C., Davenport, J. H., Moreno Maza, M., Xia, B. and Xiao, R., 2011. Computing with semi-algebraic sets represented by triangular decomposition. In: 36th International Symposium on Symbolic and Algebraic Computation, ISSAC 2011, June 8, 2011 - June 11, 2011, 2011-01-01. New York: Association for Computing Machinery (ACM), pp. 75-82. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC)
This article is a continuation of our earlier work , which introduced triangular decompositions of semi-algebraic systems and algorithms for computing them. Our new contributions include theoretical results based on which we obtain practical improvements for these decomposition algorithms. We exhibit new results on the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its "true boundary" (Definition 2). In order to optimize these algorithms, we also propose a technique, that we call relaxation, which can simplify the decomposition process and reduce the number of redundant components in the output. Moreover, we present procedures for basic set-theoretical operations on semi-algebraic sets represented by triangular decomposition. Experimentation confirms the effectiveness of our techniques.
|Item Type ||Conference or Workshop Items (UNSPECIFIED)|
|Creators||Chen, C., Davenport, J. H., Moreno Maza, M., Xia, B. and Xiao, R.|
|Departments||Faculty of Science > Computer Science|
|Publisher Statement||Chen_ISSAC2011_75.pdf: © ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ISSAC 2011 - Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. New York: Association for Computing Machinery, pp.75-82, http://dx.doi.org/10.1145/1993886.1993903|
Actions (login required)