Computing with semi-algebraic sets represented by triangular decomposition

Changbo Chen, James H Davenport, Marc Moreno Maza, Bican Xia, Rong Xiao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)
75 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationISSAC '11 Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Pages75-82
Number of pages8
ISBN (Print)9781450306751
DOIs
Publication statusPublished - 2011
Event36th International Symposium on Symbolic and Algebraic Computation, ISSAC 2011, June 8, 2011 - June 11, 2011 - San Jose, CA, USA United States
Duration: 1 Jan 2011 → …

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
PublisherAssociation for Computing Machinery

Conference

Conference36th International Symposium on Symbolic and Algebraic Computation, ISSAC 2011, June 8, 2011 - June 11, 2011
CountryUSA United States
CitySan Jose, CA
Period1/01/11 → …

Fingerprint

Semi-algebraic Sets
Triangular
Decompose
Computing
Decomposition Algorithm
Experimentation
Continuation
Simplify
Optimise
Polynomial
Output

Cite this

Chen, C., Davenport, J. H., Moreno Maza, M., Xia, B., & 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 (pp. 75-82). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). New York: Association for Computing Machinery. https://doi.org/10.1145/1993886.1993903

Computing with semi-algebraic sets represented by triangular decomposition. / Chen, Changbo; Davenport, James H; Moreno Maza, Marc; Xia, Bican; Xiao, Rong.

ISSAC '11 Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. New York : Association for Computing Machinery, 2011. p. 75-82 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Chen, C, Davenport, JH, Moreno Maza, M, Xia, B & 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. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, Association for Computing Machinery, New York, pp. 75-82, 36th International Symposium on Symbolic and Algebraic Computation, ISSAC 2011, June 8, 2011 - June 11, 2011, San Jose, CA, USA United States, 1/01/11. https://doi.org/10.1145/1993886.1993903
Chen C, Davenport JH, Moreno Maza M, Xia B, Xiao R. 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. 2011. p. 75-82. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). https://doi.org/10.1145/1993886.1993903
Chen, Changbo ; Davenport, James H ; Moreno Maza, Marc ; Xia, Bican ; Xiao, Rong. / Computing with semi-algebraic sets represented by triangular decomposition. ISSAC '11 Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. New York : Association for Computing Machinery, 2011. pp. 75-82 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).
@inproceedings{eb4f208f9b964eceaedc864ace0cafed,
title = "Computing with semi-algebraic sets represented by triangular decomposition",
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.",
author = "Changbo Chen and Davenport, {James H} and {Moreno Maza}, Marc and Bican Xia and Rong Xiao",
year = "2011",
doi = "10.1145/1993886.1993903",
language = "English",
isbn = "9781450306751",
series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
publisher = "Association for Computing Machinery",
pages = "75--82",
booktitle = "ISSAC '11 Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation",
address = "USA United States",

}

TY - GEN

T1 - Computing with semi-algebraic sets represented by triangular decomposition

AU - Chen, Changbo

AU - Davenport, James H

AU - Moreno Maza, Marc

AU - Xia, Bican

AU - Xiao, Rong

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79959639349&partnerID=8YFLogxK

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

U2 - 10.1145/1993886.1993903

DO - 10.1145/1993886.1993903

M3 - Conference contribution

SN - 9781450306751

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 75

EP - 82

BT - ISSAC '11 Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation

PB - Association for Computing Machinery

CY - New York

ER -