Information Technology Reference
In-Depth Information
where
m
is the
degree
of
p
w.r.t.
x
k
and
c
i
sarepolynomialsin
K
[
x
1
, ..., x
k−
1
]
.We
call
c
m
x
k
the
leading term
of
p
w.r.t.
x
k
and
c
m
the
leading coe
cient
.Forex-
ample, let
p
(
x
1
,...,x
5
)=
x
2
+
x
3
x
4
+(2
x
2
+
x
1
)
x
4
, so, its leading variable, term
and coecient are
x
4
,
(2
x
2
+
x
1
)
x
4
and
2
x
2
+
x
1
, respectively.
An
atomic polynomial formula
over
K
[
x
1
, ..., x
n
]
is of the form
p
(
x
1
,...,x
n
)
0
,
where
∈{
=
,>,≥,
=
}
, while a
polynomial formula
over
K
[
x
1
, ..., x
n
]
is constructed
from atomic polynomial formulae by applying the logical connectives. Conjunc-
tive polynomial formulae are those that are built from atomic polynomial formulae
with the logical operator
∧
. We will denote by
PF
(
{x
1
,...,x
n
}
)
the set of polyno-
mial formulae and by
CPF
(
{x
1
,...,x
n
}
)
the set of conjunctive polynomial formu-
lae, respectively.
In what follows, we will use
Q
to stand for rationales and
for reals, and fix
K
to be
Q
. In fact, all results discussed below can be applied to
R
.
In the following, the
n
indeterminates are divided into two groups:
u
=
(
u
1
, ..., u
t
)and
x
=(
x
1
, ..., x
s
), which are called parameters and variables, re-
spectively, and we sometimes use “,” to denote the conjunction of atomic for-
mulae for simplicity.
R
Definition 1.
A semi-algebraic system is a conjunctive polynomial formula of
the following form:
p
1
(
u
,
x
)=0
, ..., p
r
(
u
,
x
)=0
,
g
1
(
u
,
x
)
0
,
g
k
+1
(
u
,
x
)
>
0
, ..., g
l
(
u
,
x
)
>
0
,
h
1
(
u
,
x
)
≥
0
, ..., g
k
(
u
,
x
)
≥
'
(1)
=0
, ..., h
m
(
u
,
x
)
=0
,
where
r>
1
,l ≥ k ≥
0
,m ≥
0
and all
p
i
's,
g
i
's and
h
i
's are in
Q
[
u
,
x
]
\
Q
.AnSAS
of the form (1) is called
parametric
if t
=0
,otherwise
constant
.
An SAS of the form (1) is usually denoted by a quadruple
[
]
,where
P
,
G
1
,
G
2
,
H
=[
h
1
, ..., h
m
]
.
For a constant SAS
S
, interesting questions are how to compute the number
of real solutions of
S
, and if the number is finite, how to compute these real
solutions. For a parametric SAS, the interesting problem is so-called
real solution
classification
, that is to determine the condition on the parameters such that the
system has the prescribed number of distinct real solutions, possibly infinite.
G
2
=[
g
k
+1
, ..., g
l
]
and
H
P
=[
p
1
, ..., p
r
]
,
G
1
=[
g
1
, ..., g
k
]
,
2.2
Theories on Real Solution Classification
In this subsection, we outline the theories for real root classification of parametric
SASs. For details, please be referred to [31,27].
For an SAS
S
of the form (1), the algorithm for real root classification consists
of three main steps. Firstly, transform the equations of
S
into some sets of
equations in triangular form. A set of equations
T
:
T
1
, ..., T
k
]
is said to be in
triangular form (or a
triangular set
) if the main variable of
T
i
is less in the
order than that of
T
j
if
i<j
. Roughly speaking, if we rename the variables, a
triangular set looks like
Search WWH ::
Custom Search