Triangular decomposition of semi-algebraic systems

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

Research output: Contribution to journalArticle

29 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 (full and lazy) of such a decomposition and present corresponding algorithms. Under some simplifying assumptions, the lazy decomposition can be computed in singly exponential time w.r.t. the number of variables. We have implemented our algorithms and present experimental results illustrating their effectiveness.
Original languageEnglish
Pages (from-to)3-26
Number of pages24
JournalJournal of Symbolic Computation
Volume49
Early online date22 Dec 2011
DOIs
Publication statusPublished - Feb 2013

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

  • Cite this