Triangular decomposition of semi-algebraic systems

Changbo Chen; James H. Davenport; John P. May; Marc Moreno Maza; Bican Xia; Rong Xiao

doi:10.1145/1837934.1837972

Triangular decomposition of semi-algebraic systems

Changbo Chen, James H. Davenport, John P. May, Marc Moreno Maza, Bican Xia, Rong Xiao

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

24 Citations (SciVal)

Abstract

Regular chains and triangular decompositions are fundamental and well-developed tools for describing the complex solutions of polynomial systems. This paper proposes adaptations of these tools focusing on solutions of the real analogue: semi-algebraic systems. We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications of such a decomposition and present corresponding algorithms. Under some assumptions, one type of decomposition can be computed in singly exponential time w.r.t. the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.

Original language	English
Title of host publication	ISSAC '10 Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation , 2010
Place of Publication	New York, U. S. A.
Publisher	Association for Computing Machinery
Pages	187-194
Number of pages	8
ISBN (Print)	9781450301503
DOIs	https://doi.org/10.1145/1837934.1837972
Publication status	Published - 2010
Event	2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, July 25, 2010 - July 28, 2010 - Munich, Germany Duration: 1 Jan 2010 → …

Conference

Conference	2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, July 25, 2010 - July 28, 2010
Country/Territory	Germany
City	Munich
Period	1/01/10 → …

Access to Document

10.1145/1837934.1837972

Cite this

Triangular decomposition of semi-algebraic systems. / Chen, Changbo; Davenport, James H.; May, John P. et al.
ISSAC '10 Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation , 2010. New York, U. S. A.: Association for Computing Machinery, 2010. p. 187-194.

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

Chen, C, Davenport, JH, May, JP, Maza, MM, Xia, B & Xiao, R 2010, Triangular decomposition of semi-algebraic systems. in ISSAC '10 Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation , 2010. Association for Computing Machinery, New York, U. S. A., pp. 187-194, 2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, July 25, 2010 - July 28, 2010, Munich, Germany, 1/01/10. https://doi.org/10.1145/1837934.1837972

@inproceedings{3c3ce50547554dceb854ca12cb229f9d,

title = "Triangular decomposition of semi-algebraic systems",

abstract = "Regular chains and triangular decompositions are fundamental and well-developed tools for describing the complex solutions of polynomial systems. This paper proposes adaptations of these tools focusing on solutions of the real analogue: semi-algebraic systems. We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications of such a decomposition and present corresponding algorithms. Under some assumptions, one type of decomposition can be computed in singly exponential time w.r.t. the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.",

author = "Changbo Chen and Davenport, {James H.} and May, {John P.} and Maza, {Marc Moreno} and Bican Xia and Rong Xiao",

year = "2010",

doi = "10.1145/1837934.1837972",

language = "English",

isbn = "9781450301503",

pages = "187--194",

booktitle = "ISSAC '10 Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation , 2010",

publisher = "Association for Computing Machinery",

address = "USA United States",

note = "2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, July 25, 2010 - July 28, 2010 ; Conference date: 01-01-2010",

}

TY - GEN

T1 - Triangular decomposition of semi-algebraic systems

AU - Chen, Changbo

AU - Davenport, James H.

AU - May, John P.

AU - Maza, Marc Moreno

AU - Xia, Bican

AU - Xiao, Rong

PY - 2010

Y1 - 2010

N2 - Regular chains and triangular decompositions are fundamental and well-developed tools for describing the complex solutions of polynomial systems. This paper proposes adaptations of these tools focusing on solutions of the real analogue: semi-algebraic systems. We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications of such a decomposition and present corresponding algorithms. Under some assumptions, one type of decomposition can be computed in singly exponential time w.r.t. the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.

AB - Regular chains and triangular decompositions are fundamental and well-developed tools for describing the complex solutions of polynomial systems. This paper proposes adaptations of these tools focusing on solutions of the real analogue: semi-algebraic systems. We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications of such a decomposition and present corresponding algorithms. Under some assumptions, one type of decomposition can be computed in singly exponential time w.r.t. the number of variables. We implement our algorithms and the experimental results illustrate their effectiveness.

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

UR - http://doi.acm.org/10.1145/1837934.1837972

U2 - 10.1145/1837934.1837972

DO - 10.1145/1837934.1837972

M3 - Chapter in a published conference proceeding

SN - 9781450301503

SP - 187

EP - 194

BT - ISSAC '10 Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation , 2010

PB - Association for Computing Machinery

CY - New York, U. S. A.

T2 - 2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, July 25, 2010 - July 28, 2010

Y2 - 1 January 2010

ER -

Triangular decomposition of semi-algebraic systems

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this