Research

Triangular decomposition of semi-algebraic systems


Reference:

Chen, C., Davenport, J. H., May, J. P., Moreno Maza, M., Xia, B. and Xiao, R., 2013. Triangular decomposition of semi-algebraic systems. Journal of Symbolic Computation, 49, pp. 3-26.

Related documents:

This repository does not currently have the full-text of this item.
You may be able to access a copy if URLs are provided below. (Contact Author)

Official URL:

http://dx.doi.org/10.1016/j.jsc.2011.12.014

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.

Details

Item Type Articles
CreatorsChen, C., Davenport, J. H., May, J. P., Moreno Maza, M., Xia, B. and Xiao, R.
DOI10.1016/j.jsc.2011.12.014
DepartmentsFaculty of Science > Computer Science
RefereedYes
StatusPublished
ID Code28671

Export

Actions (login required)

View Item