Triangular decomposition of semi-algebraic systems

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

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

20 Citations (Scopus)

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 languageEnglish
Title of host publicationISSAC '10 Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation , 2010
Place of PublicationNew York, U. S. A.
PublisherAssociation for Computing Machinery
Pages187-194
Number of pages8
ISBN (Print)9781450301503
DOIs
Publication statusPublished - 2010
Event2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, July 25, 2010 - July 28, 2010 - Munich, Germany
Duration: 1 Jan 2010 → …

Conference

Conference2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, July 25, 2010 - July 28, 2010
CountryGermany
CityMunich
Period1/01/10 → …

Fingerprint Dive into the research topics of 'Triangular decomposition of semi-algebraic systems'. Together they form a unique fingerprint.

  • Cite this

    Chen, C., Davenport, J. H., May, J. P., Maza, M. M., 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 (pp. 187-194). Association for Computing Machinery. https://doi.org/10.1145/1837934.1837972