Research

Computing with semi-algebraic sets represented by triangular decomposition


Reference:

Chen, C., Davenport, J. H., Moreno Maza, M., Xia, B. and Xiao, R., 2011. Computing with semi-algebraic sets represented by triangular decomposition. In: ISSAC '11 Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. New York: Association for Computing Machinery (ACM), pp. 75-82. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC)

Related documents:

[img]
Preview
PDF (Chen_ISSAC2011_75.pdf) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (6MB) | Preview

    Official URL:

    http://dx.doi.org/10.1145/1993886.1993903

    Abstract

    This article is a continuation of our earlier work [3], 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.

    Details

    Item Type Book Sections
    CreatorsChen, C., Davenport, J. H., Moreno Maza, M., Xia, B. and Xiao, R.
    DOI10.1145/1993886.1993903
    DepartmentsFaculty of Science > Computer Science
    Publisher StatementChen_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
    StatusPublished
    ID Code24950

    Export

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...