Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleTriangular decomposition of semi-algebraic systems
Author(s) Changbo Chen, James H. Davenport, John P. May, Marc Moreno Maza, Bican Xia, Rong Xiao
TypeArticle in Journal
AbstractRegular 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.
KeywordsRegular semi-algebraic system, Regular chain, Lazy decomposition, Triangular decomposition, Border polynomial, Fingerprint polynomial set
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717111002070
LanguageEnglish
JournalJournal of Symbolic Computation
Volume49
Number0
Pages3 - 26
Year2013
NoteThe International Symposium on Symbolic and Algebraic Computation
Edition0
Translation No
Refereed No
Webmaster