数理解析研究所講究録1085 巻 1999 年 60-70

60

Symbolic Analysis of Discrete-Time
Polynomial Systems
穴井宏和 (Hirokazu ANAI)$*$High Performance Computing Research Center,

FUJITSU LABORATORIES LTD.

4-1-1 Kamikodanaka, Nakahara-ku, Kawasaki 211-8588, JAPANTEL: $+81-44- 754_{-}2670/\mathrm{F}\mathrm{A}\mathrm{X}:+81- 44- 754-2666$

Abstract
In this paper we focus on the analysis of discrete-time polynomial systems. We
present the modified algorithms for testing observability and accessibility based on themethods proposed in [6]. Our method not only quantifier elimination but also utilize
Gr\"obner basis and real root counting techniques for decision problem computation too
and incorporates the strategy to improve efficiency in checking equivalence of ideals.
Then we also have shown that the invertibility check of the polynomial systems canbe achieved by using Gr\"obner basis technique. And the procedure for invertibility checkyields the inverse if one exists at the same time. So backward accessibility and transitivity
can be tested in the analogous way of our algorithm for forward accessibility check infinite time step.

1

Introduction

It is important for any in-depth analysis of the systems to understand the fundamental
properties of the systems such as observability or controllability etc. In [6], D.Ne\v{s}i\v{c}presented the two algorithms arising in analysis of discrete-time polynomial systems.
One is the algorithm for checking “observability $(OB)$ ” and the other is that for checking“forward accessibility $(FA)$ ”.
As for observability test, D.Ne\v{s}i\v{c} used the same scheme used in Sontang’s work [9]and presented actually constructive symbolic algorithm, which always stops in finite
time, by utilizing computer algebra methods such as
bner Basis $(GB)$ and quantifier
elimination $(QE)$ .
As for forward accessibility test, there is the work by B.Jakubczyk . al. [5] in 1990,
where the Lie algebra methods were used to test accessibility. Here we take another$Gr\dot{\mathit{0}}$$et$*e-mail: anai@flab.

$\mathrm{f}\mathrm{u}\mathrm{j}$itsu.

$\mathrm{c}\mathrm{o}$

. jp

61
approach used in [6] which is applicable to only polynomial systems. D.Ne\v{s}i\v{c} presented
the constructive symbolic algorithm for checking forward accessibility, which is based on
ideas of invariant algebraic set, by Gr\"obner basis and quantifier elimination.
However, there is some room for the method proposed by D.Ne\v{s}i\v{c} to make an improvement in view of the computational complexity. And if we have the inverse of the“polynomial maps, we can actually realize the method to check backward accessibility”$(BA)$ ” and “transitivity $(TR)$ in the same way as FA check. In this paper we present
the improved (algebraic) algorithms for checking OB and FA and extend the applicabilityof our FA check algorithms for checking to BA and TR check by introducing concrete.
procedure to compute inverse of polynomial systems by using$\mathrm{G}\mathrm{B}$

Preliminary

2

and forWe denote the ring of polynomials in over a field $K$ by $K[x]$ . We use
bynumbers
naturalfields of real numbers and rational numbers respectively and denoteN.
In this paper we consider the following class of polynomial systems:$\mathrm{R}$$x$$x(k+1)$$=$$f(x(k), u(k))$$y(k)$$=$$h(x(k))$$\mathrm{Q}$(1)$y(k)\in \mathrm{R}$ and $u(k)\in \mathrm{R}$ are the state, output and input of thewhere, $f_{n}(x, u))$ and assume
respectively. Let $f(x, u)=(f_{1}(X, u),$system (1) at time(due to the applicability of symbolic computationthat $f_{i}(x, u)\in \mathrm{Q}[x, u]$ andpackages). Note that, in general, is a nonlinear.
$x(k)\in \mathrm{R}^{n},$$\cdots$$k$$h\in \mathrm{Q}[x]$$f$We mostly will follow the notations in [6]. We denote the composition of$f_{u(1)^{\mathrm{O}}}\dot{f}_{u(0}\triangleright)=.f(f(x.(‘ 0)., u(.0^{\cdot})),$

$f$

by

$u(1))$and its truncation of
Let a sequence of controls ( $i.e$ . inputs) be $U–(u(\mathrm{O}), u(1),$, $u(s-1))$ . We denoteto a sequence of length is denoted as $U_{s}=$atthe output of system (1) which is reached from the initial statebytime step under the action of a control sequence .
$\cdots)$$U$$(u(\mathrm{O}), u(1),$$s$$y(S, x(\mathrm{O}),$$\cdots$$x(\mathrm{O})$$U_{s})$$U_{s}$$s$Definition 1 (Observability) The system (1) is observable if for each pair of initialwhich yields $y(N, \xi, U_{N})\neq$, there exists an integer $N$ and an input sequence
states( $N,$ UN).
.
$\xi,$$y$$U_{N}$$\eta$$\eta,$‘..,$\cdot$‘.

$)$. Hereof invertibility for polynomial
We employ the following
is the set of all (rational) polynomials in and called a rational function field in .
$\mathrm{m}\dot{\mathrm{a}}\mathrm{p}\mathrm{s}’$$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\dot{\mathrm{i}}\mathrm{o}\mathrm{n}$$\mathrm{Q}(u)$

$u$

$u$

Definition 2 Let $X=\{x_{1}, \cdots, x_{n}\}$ . We consider an -tuple $f=(f_{1}(X), \cdots , f_{n}(X))$
rise to a map.
$n$$\in(\mathrm{Q}(u)[X])^{n}$$fgive\mathit{8}$$\varphi_{f}$:$(\mathrm{Q}(u))^{n}$$arrow$$(\mathrm{Q}(u))^{n}$$(a_{1}, \cdots, a_{n})$$rightarrow$$(f_{1}(a), \cdots, f_{n}(a))$,

62
where $a=(a_{1}, \cdots, a_{n})\in(\mathrm{Q}(u))^{n}$ .
such thatis.called invertible if there exit$\varphi_{f}$$\mathrm{Q}(u)[X]$$g_{i}(f_{1}, \cdots, f_{n})=X_{i}$so thatinverse ofwhere$\varphi_{g}\circ\varphi_{f}=id_{(\mathrm{Q}(u))}n$

$f$

by

$f^{-1}$.

$id_{(\mathrm{Q}(u))}n$for$g_{1},$$\cdots$,$g_{m}$$\in$.

$1\leq i\leq n$

is an identity on$(\mathrm{Q}(u))^{n}$. We denote the

We denote by
the set of states attainable fromin forward steps,
and by $R^{+}(x(0))$ the set of states attainable fromin any nonnegative number offorward steps. Replacing forward steps by backward steps we similarly obtain
and $R^{-}(x(0))$ , which consists of states controllable toin steps, and controllable
toin any nonnegative number of steps, respectively. We denote the set of reachable
states from an initial state
at step by$R_{k}^{+}(x(0))$$x(\mathrm{O})$$k$$x(\mathrm{O})$$R_{k}^{-}(x(0))$$k$$x(\mathrm{O})$$x(\mathrm{O})$$k$$x(\mathrm{O})$$V_{r}^{k}(x(0))=\{x|_{X=}f_{u}(k-1)\circ\cdots\circ f_{\tau l}(0)(x(0)), u(i)\in \mathrm{R}\}$

we can rewrite. The set of states attainable fromanyinnumber of positive and negative steps is called the orbit ofand is denoted by$R(x(0))$ .
$R_{k}^{+}(x(0))= \{z|z\in\bigcup_{i}^{k}V_{r}^{i}(X(\mathrm{O}))\}$$x(\mathrm{O})$$x(\mathrm{O})$Definition 3 (Accessibility) The system (1) is forward accessible from theif $R^{+}(x(0))$ has a non-empty interior $(i.e. dimR^{+}(x(\mathrm{o}))=n)$ .
When the system (1) is invertible, we can define followings: the system (1) is backward accessible from
if $R^{-}(x(0))$ has a non-empty interior. It is called transitive from(or forward-backward accessible) if its orbit
has a non empty
interior.
Finally, the system is forward (backward) accessible if it is forward (backward) accessible from any states, and it is called transitive if it is transitive from any.
$x(\mathrm{O})\in \mathrm{R}^{n}$$x(\mathrm{O})\in \mathrm{R}^{n}$$x(\mathrm{O})$$R(x(\mathrm{O}))$$x\in \mathrm{R}^{n}$$x\in \mathrm{R}^{n}$

There is a following straightforward criterion for accessibility of the discrete time system(in [5]), which is based on the rank of Jacobian of a map $F_{k-1}=f_{u(k-}1$ )).
From the proposition shown in [5], we have$0\cdots \mathrm{o}f_{u(0}$Proposition 4 For fixed
iff there exists an input$x$and , the interior of attainable set
from$(u_{0}, \cdots , u_{k-1})^{T}$such that$k$$R_{k}^{+}(x)$$x$

is nonempty$\mathit{8}equence\mathrm{u}_{k-}1=$

rank$\frac{\partial F_{k-1}}{\partial \mathrm{u}_{k-1}}=n$The system (1) is forward accessible fromsuch that
rank

$x$

.

iff there exists an$\frac{\partial F_{k-1}}{\partial \mathrm{u}_{k-1}}=n$for$k\geq 1$$\mathrm{u}_{k-1}=(u_{0}, \cdots, u_{k-1})^{T}$.

Hereafter, we consider the case of(single input single output) system (1). The
algorithm for SISO case is also directly applicable to MIMO (multi input multi output)$\mathrm{s}\mathrm{I}\mathrm{S}\mathrm{O}$

case.

63

3

Checking observability

In this section we review the algorithm for checking observability proposed in [6]. We) which generate the same output sequence(such thatconsider all states
independently of the applied input sequence. Here we call such states “indistinguishable”
states.
$\xi,$$\xi\neq\eta$$\eta\in \mathrm{R}^{n}$

Framework: We construct a set which involves all the indistinguishable states; If two
can not be distinguished by any input sequence, as a necessary
distinct statescondition, we have$\xi,$$\eta\in \mathrm{R}^{n}$(2)$h(\xi)=h(\eta)$

generate the same output up to second time step
at first time step. If the two states
independently of the applied input sequence, we necessarily have$\xi,$$\eta$(3)$h(f(\xi, u))=h(f(\eta, u))$in addition to (2). If we denote$h(f(x, u))=h_{m}(x)u^{m}+\cdots+h_{1}(x)u+h_{0}(x)$ ,then the condition (3) is equivalent to$h_{i}(\xi)=h_{i}(\eta)$

Then, the states$\xi,$$\eta$

for$\forall i=0,1,$$\cdots$(4), $m$ .

which have the same output for the first three steps satisfy$h(f\circ f(\xi, u))=h(f\circ f(\eta, u))$

.

(5)

Let
$h_{i}(f(x, u))=h_{p_{i},i}(x)u^{p}i+\cdots+h_{1,i}(x)u+h_{0,i}(X)$.

Then the condition (5) is equivalent to$h_{p_{i},i}(\xi)=h_{p_{i},i}(\eta)$

for$\forall i=0,1,$ $\cdots,$ $m$(6).

We can obtain the necessary condition of indistinguishable states for any time step bycontinuing the same procedure as above.
We consider the sequence of ideals corresponding to that of necessary condition ofindistinguishable states as follows;$J_{1}=\langle h(\xi)-h(\eta)\rangle$$J_{2}=\langle h(\xi)-h(\eta), h0(\xi)-h0(\eta), \cdots, h_{1}(\xi)-h_{1}(\eta)\rangle$$J_{3}=\langle h(\xi)-h(\eta),$ $h\mathrm{o}(\xi)-h0(\eta),$$\cdots,$$h_{1}(\xi)-h1(\eta)$$h_{0,0}(\xi)-h_{0,0}(\eta),$ $\cdots,$ $h_{p_{m},m}(\xi)-h_{p_{m}},m(\eta)\rangle$,

64Then by the construction we have the ascending chain of ideals$J_{1}\subset J_{2}\subset J_{3}\subset\cdots$.

(7)

The ascending chain (7) must terminate in finite length $i.e$ . there exists an integer $N$
such that $J_{N}=J_{N+1}$ (by Noetherian property of the polynomial ring). Let the varietyof the ideal
be $V(J_{N})$ . We consider the set$J_{N}$$S_{z}=V(J_{N})\cap\{(\xi, \eta)|\xi\neq\eta\}$.

Then all the indistinguishable states belong to the set. Let the set of equations
obtained by setting all generators of the ideal
equal to zero be
Next we checkthe decision problem:$S_{z}$$J_{N}$$E_{J_{N}}$(8)$\exists\xi\exists\eta(E_{J_{N}}\wedge\xi\neq\eta)$

If the answer to (8) is false, the system is observable, otherwise (answer is true;
the system is not observable.
$(S_{z}=\emptyset)$$S_{z}\neq\emptyset)$

Realization: Here we need two symbolic method, that is, GB and. Testing thecoincidence of the ideals
andforis achieved by comparing their reduced GBwith respect to the same ordering. And we can determine the decisionbyusing QE since
is obviously a semi-algebraic set in.
$\mathrm{Q}\mathrm{E}$$J_{i+1}$$J_{i}$$\forall i$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}.(8)$$S_{z}$

4[6].

$\mathrm{R}^{n}\cross \mathrm{R}^{n}$

Checking forward accessibility
In this section we review the algorithm for checking forward accessibility proposed in

Framework: First consider the composition;$F=f_{u_{n-}}10\cdots \mathrm{o}fu_{0}$and its Jacobian:$J= \frac{\partial F}{\partial \mathrm{u}_{n-1}}$

where$\mathrm{u}=(u_{0}, \cdots, u_{n-1})^{T}$.

. Let the determinant of$detJ= \sum N_{0}$$i_{0}=0$

...

$J$

be

$N_{n-1 ’\sum}b_{i_{0},i,\cdots,in-1}(_{X}1)u_{01}^{i\mathrm{o}\ldots n-}u_{n}^{i}-1$.

$i_{n-1}=0$

and. We define critical variety
by $V_{C}=V(J_{C})$ .
From proposition 4, if there exists a state such that the determinant of is non-zeropolynomial in , then the system (1) is forward accessible from . So the critical variety
contains all states
which satisfy $dimV_{r}^{n}(X)<n$ . Here we define the key
notion “invariant set” in this algorithm.
$J_{C}=\langle b_{0,\cdots,0}, \cdots, b_{N_{0},\cdots,N_{n-1}}\rangle$$V_{C}$

$J$

$x$

$x$

$\mathrm{u}$$V_{C}$$x\in \mathrm{R}^{n}$65
Definition 5
is an invariant set if $f(x(\mathrm{O}), u)\in S_{I}$ for all$u\in$ R.
is called maximal invariant set if it satisfies that if
is an invariant set, then $V_{I}=V^{*}$ .
$S_{I}\subset V_{C}$$V_{I}\subset V_{C}$and, where$x(\mathrm{O})\in S_{I}$$V_{I}\subset V^{*}$$V^{*}\in V_{C}$Theorem 6
Consider a system (1) and assume that $detJ\neq 0$ . Then thesystem is forward accessible if and only if.
$(\mathrm{N}\mathrm{e}\mathrm{s}\mathrm{i}\acute{\mathrm{c}}[6])$$V_{I}=\emptyset$

Now we mention the computation of$V_{I}$. Consider the ideal$J_{C}\circ f_{u}(x)=J_{C}(f(X, u))$And let

$J_{C}=\langle g_{1}, \cdots, g_{s}\rangle$$J_{C}$. We use the notation.

then we have$Jc^{\mathrm{o}fu}(x)$$=$$\langle g_{1}(f(X, u)), \cdots, g_{s}(f(_{X}, u))\rangle$$=$$\langle g_{1^{\mathrm{O}}}f_{u}(x), \cdots, g_{S}\mathrm{o}fu(x)\rangle$.

.

where note that $g_{j}\circ f_{u}(X)=g_{j}(f(X, u))\in \mathrm{Q}[x_{1}, \cdots, x_{n}][u]$ . So let$g_{j} \circ f_{u}(X)=\sum_{i=0}^{N_{j}}aj,i(x)u^{i}$,$j=1,2,$$\cdots,$ $s$.

An. consider the ideal$\mathrm{d}$$J_{C}^{(1)}=\mathcal{G}_{1}\cdot \mathcal{G}2\ldots..\mathcal{G}_{s}$where$\mathcal{G}_{j}=\langle a_{j,0}, a_{j,1}, \cdots, a_{j,N_{\mathrm{j}}}\rangle$. (The products of two ideals

is defined byidealsis defined byin the same way by taking composition$\mathcal{I}_{1}+\mathcal{I}_{2}=\langle a_{1}, \cdots , a_{N}, b_{1}, \cdots , b_{M}\rangle.)$$\mathcal{I}_{1},\mathcal{I}_{2}$and. The sum of two
We can form the ideal$\mathcal{I}_{1}=\langle a_{1}, \cdots, a_{N}\rangle$$\mathcal{I}_{1}\cdot \mathcal{I}_{2}=\langle a_{i}b_{j}|1\leq i\leq N, 1\leq j\leq M\rangle$$\acute{\mathcal{I}}_{2}=\langle b_{1}, \cdots , b_{M}\rangle$$J_{C}^{(k)}$$JC^{\mathrm{O}}f_{u(}k-1)\circ\cdots \mathrm{o}fu(0)(x)$’$k-1$ , with coefficients
regarding its generators as polynomials in $u(i),$ $i=0,1,$
polynomials in and achieving the same manner as before.
(
Let $J_{0}=J_{C}$ andfor $t=0,1,2,$ . Continuing the same procedure
we have an ascending chain of ideals$\cdots,$$x$$J_{t}= \sum_{k=0}^{t}J_{c^{k)}}$$\cdots$(9)$J\mathrm{o}\subset J_{1}\subset J_{2}\subset\cdots$

The ascending chain (9) must terminate in finite length $i.e$ . there exists an integer $N$ suchthat $J_{N}=J_{N+1}$ (by Noetherian property of the polynomial ring). Let $J_{I}= \sum_{k=0}^{N}Ji$ .
Then the maximal invariant setofis given by $V(J_{I})$ .
Let the set of equations obtained by setting all generators of the ideal
equal tozero beNext we check the decision problem:$V_{I}$$V_{C}$$J_{I}$$E_{J_{I}}$(10)$\exists x(E_{J_{I}})$

If the answer to (10) is false, the system is forward accessible, otherwise (answer) the system is not forward accessible.
is true;$(V_{I}=\emptyset)$$V_{I}\neq\emptyset$

Realization: Here we need two symbolic method, that is, GB and. Testing thecoincidence of the ideals
andforis achieved by comparing their reduced GBwith respect to the same ordering. And we can determine the decision problem (10) by.
using$\mathrm{Q}\mathrm{E}$$J_{i}$$\mathrm{Q}\mathrm{E}$$J_{i+1}$$\forall i$

66

5

Improvements of algorithms

Since GB and QE are guaranteed to terminate in finite time, two algorithms proposedin [6] terminate in finite time. But the computational complexity of the methods is not
small. So, it is very important to improve the algorithm in view of the complexity when,in particular, we consider the industrial applications. In this section, we will present the
improvements of the algorithms.

5.1

First improvement

In [6], as for OB check, the case where we do not have to use QE is indicated; If theat some step is $\{\xi-\eta\}$ , the system is observableobtain reduced GB of the ideal
since it implies that $J_{k}=J_{k+1}$ and $V(J_{k})=V(\xi-\eta)$ . This is a trivial case where we do.
not have to use
Here we propose the algorithms for observability and forward accessibility test which
does not use directly QE for decision problems. We use GB and real root counting
method for multivariate polynomial systems before applying QE to them.
$k$$J_{k}$$\mathrm{Q}\mathrm{E}$: The decision problem (8) can be checked by using GB as follow; We introduce
new slack variable and consider the ideal$\underline{\mathrm{O}\mathrm{B}}$$t$$I_{d}$$I_{d}=\langle J_{N}\cap(\xi-\eta)b-1\rangle$

(11)

.

.
be
Let the GB of with respect to the block ordering, the system is observable. If
is not equal to {1},Ifis equal to {1},may have no real roots, then the system
has some roots in C. But in this casehas a real root or not. Since we alreadyis observable. So next we check whether
is -dimentiomal or not immediately. If
is 0, we can determine whether
haveby using the method by P.Pedersen
dimensional, we count the number of real roots ofet. $al.[8]$ . Then if the number of real roots is equal to , the system is observable. If
is not -dimensional, we use QE as proposed by D.Ne\v{s}i\v{c}.
This yields the more efficient algorithm than original one since in many case actuallyis equal to {1} by the construction and, in general, complexity of GB and real root.
counting is smaller than that of$\{\xi, \eta\}\prec\prec\{t\}$$I_{d}$$(S_{z}=\emptyset)$$G_{d}$$G_{d}$$G_{d}$$G_{d}$$G_{d}$$G_{d}$$G_{d}$$G_{d}$$0$$G_{d}$$G_{d}$$0$$G_{d}$$0$$G_{d}$$\mathrm{Q}\mathrm{E}$Remark 1 In actual procedure, we construct the chain of Gr\"obner basisof the$(i=1,2, \cdots)$ . Hence, in order to obtain the Gr\"obnerof , we compute theGr\"obner basis of the ideal $I_{d}’=\langle G_{N}\cap(\xi-\eta)t-1\rangle$ .
$G_{i}$$basi\mathit{8}G_{d}$$J_{i}$$I_{d}$: The decision problem (10) can be checked by the same way as above; if the Gr\"obner
is not equal to {1},basisof
is {1}, the system (1) is forward accessible. If
roots,
maythen the system is
has no real
has some roots in C. But in this caseis -dimentiomal or not. If
is O-dimensional,
observable. So next we check whether
similarly. If
is not -dimensional, we use
we count the number of real roots of. This leads to the improvement of efficiency by the same reasons as explained for FA
check.

$\underline{\mathrm{F}\mathrm{A}}$$G_{I}$$G_{I}$$J_{I}$$G_{I}$$G_{d}$$G_{I}$$G_{I}$$\mathrm{Q}\mathrm{E}$$0$$G_{I}$$G_{I}$$0$67
Second improvement

5.2

Here we mention the improvement for the efficiency of the computation of ascending
chain and its equivalence check appearing two algorithms.
: We denote the set of polynomiais which are added toin order to construct. (Here for convenience’ sake let);
for $k=1,2,$
at step by$J_{k-1}$$\underline{\mathrm{O}\mathrm{B}}$$k$$J_{k}$$A_{k}$$J_{0}=\langle\rangle.$$\cdots$$A_{1}=\{h(\xi)-h(\eta)\}$$A_{2}=\{h_{0}(\xi)-h0(\eta), \cdots, h_{1}(\xi)-h_{1}(\eta)\}$$A_{\mathrm{s}=}\{h_{0,0}(\xi)-h_{0,0}(\eta), \cdots, h_{p_{m},m}(\xi)-h_{pm’ m}(\eta)\}$:Now we can rewrite$J_{1}=\langle A_{1}\rangle$$J_{2}=J_{1}+\langle A_{2}\rangle$$J_{3}=J_{2}+\langle A_{3}\rangle=\langle A_{1}\rangle+\langle A_{2}\rangle+\langle^{\text{ノ}}A3\rangle$:, the sum of two ideals stands
where for two ideals
and
.
for
In the case of nonlinear systems $(i.e. deg(f)>1)$ , the degree of polynomials inwhich are adjoined to construct the next ideal of ascending chain
become large according to $deg(h)^{i}$ . Here we propose the improvement using normal form computation inorder to circumvent the degree explosion of polynomials in $A_{k}(k=1,2, \cdots)$ successively
when we compute GB of $J_{k+1}$ .
Consider k-th step. We have computed Gr\"obner basis $G_{k-1}$ of $J_{k-1}$ . Let $A_{k}=$. Now what we do is to compute Gr\"obner basis of . First we compute the. And we denote the set of thenormal form of with respect to $G_{k-1}$ for all $i=1,$
normal forms which is not equal to by $A_{k}’=\{a_{1}’, \cdots, a_{s}’,\}$ where $s’\leq s$ . Here if every
normal form of. is $0(i.e. A_{k}’=\emptyset)$ , then we have $G_{k-1}=G_{k}$ . Otherwise, consider theideal,$\mathcal{I}_{1}=\langle p_{1}, \cdots,p_{s}\rangle$$\mathcal{I}_{2}=\langle q_{1}, \cdots, q_{t}\rangle$$\mathcal{I}_{1}+\mathcal{I}_{2}=\langle p_{1}, \cdots,p_{s}, q_{1}, \cdots, q_{t}\rangle$$A_{i}$$J_{i}$$\{a_{1}, \cdots, a_{s}\}$$J_{k}$$\cdots,$$a_{i}$$s$$0$$a_{i}$$J_{k}’=G_{k}-1+\langle A_{k}’\rangle$

then we obviously have by the properties of Gr\"obner basis :Corollary 7 The Gr\"obner basis$G_{k}$

of$J_{k}=J_{k1}-+\langle A_{k}\rangle$.

of$J_{k}’=G_{k-1}+\langle A_{k}’\rangle$

is equivalent to the Gr\"obner basis

By this corollary we can construct the Gr\"obner basis
by computing Gr\"obner basisof instead of . This leads to the improvement of the efficiency owing to the following
reasons; The computation of Gr\"obner basis of
is much more efficient than that of
may be smaller (are mostly small)because the number and degree of polynomials ofthan those of
and we use
instead of . Furthermore, in general, computational$G_{k}$$J_{k}’$$J_{k}$$J_{k}$$J_{k}’$$A_{k}’$$A_{k}$$G_{k}$$J_{k}$

68
cost of normal form computation is much small compared to the complexity of Gr\"obnerbasis computation.
at step: The set of polynomials which are added to $J_{k-1}$ in order to construct. We can improve the procedure for checking equivalence offor $k=1,2,$
isin the same manner as the case OB check. This leads to the improvement ofidealsefficiency by the same reasons as explained above.
$J_{k}$$\underline{\mathrm{F}\mathrm{A}}$$k$$J_{C}^{(k)}$$\cdots$$J_{i}’ \mathrm{s}$, FA check based on Gr\"obner basis comHere we show modified algorithms forputation. Here we use abbreviation $GB[I]$ for GB of the idal .
$\mathrm{O}\mathrm{B}$$I$

Algorithm 1 [Modified OB check]
Input: a polynomial system $(f(x, u),$ $h(x))$
output: observable or not

1. $k=1$ , fix a monomial ordering.
. Compute $G_{1}=GB[G_{1}]$ .
2. Let3. $k=k+1$ .
of withand let $A_{k}=\{a_{1}, \cdots, a_{s(k)}\}$ . Compute the normal form
4. Construct$G_{k-1}$.
,$i=1,2,$
forrespect tothen go to 5.
. If
beAnd let the set of all non-zero$G_{k}=GB[J_{k}]$and go to 3.
where
Otherwise compute
5. Compute the Gr\"obner basis $G_{d}(\equiv G_{k-1})$ of the ideal . If $G_{d}=\{1\}$ then thesystem is observable.
.
is -dimentiomal or not by
6. If $G_{d}\neq\{1\}$ then check whether. Then if the(a) Ifis -dimensional, we count the number of real roots ofnumber of real roots is , the system is observable.
(b) Ifis not -dimensional, we use QE for the decision problem (8). If (8) is false,the system is observable. Otherwise the system is not observable.
$J_{1}=\langle h(\xi)-h(\eta)\rangle$$A_{k}$$m_{i}$$\cdots$$a_{i}$$s$$A_{k}’$$m_{i}$$A_{k}’=\emptyset$$J_{k}’=G_{k-1}+\langle A_{k}’\rangle$$I_{d}’$$0$$G_{d}$$G_{d}$$G_{d}$$0$$G_{d,\sim}$

$0$

$0$

$G_{d}$

Algorithm 2 [Modified FA check]
Input: a polynomial system $(f(x, u),$ $h(x))$
output: forward accessible or not

1. $k=0$ , fix a monomial ordering.
2. Compute $G_{0}=GB[J\mathrm{o}]$ .

3. $k=k+1$ .
4. Constructofand let $J_{C}^{(k)}=\{g_{1}, \cdots , g_{s(k)}\}$ . Compute the normal form
, .
with respect to $G_{k-1}$ for $i=1,2,$. Ifthen go to 5.
be
And let the set of all non-zero$G_{k}=GB[J_{k}/]$and go to 3.
where
Otherwise compute
If $G_{I}=\{1\}$ then the
5. Compute the Gr\"obner basis $G_{I}(\equiv G_{k-1})$ of the ideal
is forward accessible,$G_{I}\neq\{1\}$.
is -dimentiomal or not bythen check whether
6. If. Then if the(a) Ifis -dimensional, we count the number of real roots ofnumber of real roots is , the system is observable.
(b) Ifis not -dimensional, we use QE for the decision problem (10). If (10) is
false, the system is observable. Otherwise the system is not observable.
$J_{C}^{(k)}$$m_{i}$$\cdots$$m_{i}$$s$$A_{k}’$$A_{k}’=\emptyset$$J_{k}’=G_{k-1}+\langle A_{k}’\rangle$$E_{J_{I}}.\cdot$$.\mathrm{s}\mathrm{y}_{\mathrm{S}\mathrm{t}}\mathrm{e}\mathrm{m}$$G_{I}$$G_{I}$$G_{I}$$G_{I}$$0$$0$$G_{I}$$0$$0$$g_{i}$

69

6Invertibility and extension to BA and TR check
One of main difficulties in the studies of the general discrete-time case is due tothe possible non-invertibility of the one-step transition maps $x\vdash+f(x, u)$ . It is very
important to propose the concrete procedure for determining the invertibility of the map
and computing the inverse if one exists. Since we consider the discrete-time polynomial
system here, we can propose the method to do it. If we can compute the inverse of
systems, we can apply our algorithm of FA check to the BA and TR check.
Fortunately, we have following theorem for invertibility of polynomial maps [2]:Proposition 8 Let $f=(f_{1}, \cdots, f_{n})\in(\mathrm{Q}(u)[X])^{n},$ $T=\{Y_{1}, \cdots, Y_{n}\}$ be a new indeterminate and.
$I=\langle \mathrm{Y}_{1}-f_{1}, \cdots, \mathrm{Y}_{n}-f_{n}\rangle$

Then,
is
that
be a term order on
Furthermore,$to\preceq
is$invertible if and only if the reduced Gr\"obner basis of I with respectof the form
$T(X, \mathrm{Y})$$let\preceq$$sati_{\mathit{8}}fies\mathrm{Y}\prec\prec X.$$\varphi_{f}$$G=\{X_{1^{-}}g_{1}, \cdots, x_{n}-g_{n}\}$with$g_{1},$$\cdots,$$g_{n}\in \mathrm{Q}(u)[Y]$. Moreover if $(b)$ holds, then $g_{i}(f_{1}, \cdots , f_{n})=X_{i}$ for $1\geq i\geq n$ .

By this proposition, for a given , Gr\"obner basis (over a rational function field in ) isis invertible or not and computing the inverse if exists
a method to decide whether
at the same time.
$u$

$f$

$\varphi_{f}$of the system (1) is invertible and assume the inverse
Consider the case wherecanas shown above. The maps and their inverses
using
by
GB
computedof hasbe considered as “one step forward maps” and “one step backward maps” respectively.
and allow backward as well as forward
If we apply a sequence of controls
steps, we obtain a larger family of composition maps$f^{-1}$$f_{u}$$f_{u}^{-1}$$f_{u}$$f_{u}$$u_{0},$$\cdots,$ $u_{k-1}$$\mathcal{F}_{k-1}=f_{u^{k}}e_{k}-1_{\mathrm{O}}\ldots \mathrm{o}f-1u^{0}0e$

(12)

.

.
where each takes aThen, backward accessibility is checked by applying the same manner in \S 5,6 to$n-1$ .
are $-1$ for $i=0,1,$
such thatby using analogous argument in \S 5,6 for the map
achievedalso
Transitivity check is.
since the orbit is the countable union of the images of the map$\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}\pm 1$$e_{i}$$\mathcal{F}_{n-1}$$e_{i}$$\mathcal{F}_{k-1}$$\mathcal{F}_{n-1}$

7$\cdots,$

Conclusion

We have presented the modified algorithms for testing observability and accessibility
for discrete-time polynomial systems based on those proposed in [6].
Our method also use Gr\"obner basis computation for decision problems and incorporates the strategy to improve efficiency in checking equivalence of ideals.
And we also have shown that we can extend our algorithm for forward accessibility to backward accessibility and transitivity by employing the well-known definition of
invertibility of polynomial map and using Gr\"obner basis technique.

70
We should examine the actual efficiency of our method by experiments on
This is one of our important future works.

$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{e}\Gamma’$.

Acknowledgments The author would like to thank Dr. D. Ne\v{s}i\v{c}, Prof. V. Weispfenning, and his colleagues J. Kaneko and Dr. K. Yokoyama for their invaluable comments
and advice.

References[1] H. Anai. An improved algorithm for checking observability of discrete-time polyno, Fujitsu labs, 1998. Sep.
mial systems. Technical Report$\mathrm{H}\mathrm{p}\mathrm{c}\mathrm{R}\mathrm{c}_{-\mathrm{R}\mathrm{R}99-}-01$[2] T. Becker and V.Weispfenning. Gr\"obner Bases. GTM. Springer-Verlag, 1993.

[3] G. Collins. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic
Decomposition, LNCS 32. Springer Verlag, 1975.
[4] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: An Introduction
to Computational Algebraic Geometry and Commutative Algebra. Undergraduate
Texts in Mathematics. Springer, 1992.
[5] B. Jakubczyk and E.D.Sontag. Controllability of nonlinear discrete-time systems: a
lie-algebra approach. SIAM J. Control and Optimization, $28(1):1-33$ , Jan 1990.
[6] D. Ne\v{s}i\v{c}. Two algorithms arising in analysis of polynomial models. In Proceedings of1998 American Control Conference, pages 1889-1893, 1998.
[7] D. Ne\v{s}i\v{c} and I.M.Y.Mareels. Dead beat controllability of polynomial systems: Symbolic computation approaches. IEEE, Transaction in Automatic Control, $43(2):162-$
175, February 1998.
[8] P.Pedersen, M.-F.Roy, A.Szpirglas, Computing real zeros in the multivariate case, in
Computational Algebraic Geometry, Proc. MEGA’92, Birkh\"auser 1993, pp203-224.

[9] E. Sontag. On the observability of polynomial systems I; finite-time problems. SIAM
J. Control and Optimization, $17(1):139^{-151}$ , 1979.