Regular semi-algebraic system

In computer algebra, a regular semi-algebraic system is a particular kind of triangular system of multivariate polynomials over a real closed field.

Introduction

Regular chains and triangular decompositions are fundamental and well-developed tools for describing the complex solutions of polynomial systems. The notion of a regular semi-algebraic system is an adaptation of the concept of a regular chain focusing on solutions of the real analogue: semi-algebraic systems.

Any semi-algebraic system S can be decomposed into finitely many regular semi-algebraic systems S_1, \ldots, S_e such that a point (with real coordinates) is a solution of S if and only if it is a solution of one of the systems S_1, \ldots, S_e.[1]

Formal definition

Let T be a regular chain of {{\mathbf{k}}}[x_1, \ldots, x_n] for some ordering of the variables \mathbf{x} = x_1, \ldots, x_n and a real closed field {{\mathbf{k}}}. Let \mathbf{u} = u_1, \ldots, u_d and \mathbf{y} = y_1, \ldots, y_{n-d} designate respectively the variables of \mathbf{x} that are free and algebraic with respect to T. Let P \subset {{\mathbf{k}}}[\mathbf{x}] be finite such that each polynomial in P is regular w.r.t.\ the saturated ideal of T. Define P_{>} :=\{p>0\mid p\in P\}. Let \mathcal{Q} be a quantifier-free formula of {{\mathbf{k}}}[\mathbf{x}] involving only the variables of \mathbf{u}. We say that R := [\mathcal{Q}, T, P_{>}] is a regular semi-algebraic system if the following three conditions hold.

The zero set of R, denoted by {Z}_{{{\mathbf{k}}}}(R), is defined as the set of points (u, y) \in {{{\mathbf{k}}}}^d \times {{{\mathbf{k}}}}^{n-d} such that \mathcal{Q}(u) is true and t(u, y)=0, p(u, y)>0, for all t\in Tand all p\in P.

See also

References

  1. Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. Triangular decomposition of semi-algebraic systems. Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187–194, 2010.