\documentstyle[11pt]{article}
\textheight 23cm\textwidth 15.5cm
\oddsidemargin 4mm
\topmargin -1cm
\setlength{\unitlength}{1mm}

\begin{document}
\bibliographystyle{plain}

\title{{\sc Polycon} - A Maple Package for Polynomial and Rational Control
Systems; \ version 1.0}
\author{Krister Forsman, Dept.~of Electrical Engineering\\
Link{\"o}ping University, S-581 83 Link{\"o}ping, Sweden\\[2mm]
email: \verb+krister@isy.liu.se+}
\date{1992-08-13}
\maketitle

\section{Introduction}

{\sc Polycon} is a package of Maple functions for the analysis of polynomial
and rational control systems, i.e.~control systems of the type
\begin{equation}
\dot{x}(t)\,=\,f(x(t),u(t)),\quad y\,=\,h(x,u)
\end{equation} or
\begin{equation}
x(t+1)=f(x(t),u(t)),\quad  y=h(x,u)
\end{equation}
where $h$ and all components of $f$ are rational functions in $x$ and $u$.
In some functions only polynomial nonlinearities are allowed.  Most functions
are available in a continuous time and a discrete time version; the
convention is that the names of continuous time functions end in {\tt c} and
those of discrete time functions end in {\tt d}. Exceptions are {\tt lieder} -
{\tt liehom} and the like.

\vspace{6mm}
\noindent The package is aimed at questions related to state space
realizations:
\begin{itemize}
\item state space to input-output conversion ({\tt ss2ioc, ss2iod})
\item realization of input-output equations ({\tt par2ssc, io2ssc, io2ssd})
\item observability ({\tt obsvc, obsvd})
\item state transformations of systems ({\tt newsysc, newsysd})
\item finding the transformation between two equivalent systems ({\tt
sstrac, sstrad})
\end{itemize}

\noindent There is also a function {\tt loclyap} for analysis of local
Lyapunov functions.

\vspace{2mm}
The functions available are, in alphabetical order:

\vspace{2mm}\hspace{6mm}
{\tt \begin{tabular}{lllllll}
auxlieder & io2ssc  & io2ssd  & lieder  & liederlist & liehom  & liehomlist\\
loclyap   & newsysc & newsysd & obsvc   & obsvd      & par2ssc & ss2ioc\\
ss2iod    & sstrac  & sstrad  & uyder   & uyhom      & xss2ioc & xss2iod
\end{tabular}}

\vspace{2mm}
Some of these functions, such as {\tt auxlieder, liederlist} etc.~are
mainly for internal use but are documented anyway.

\vspace{2mm}
In the {\sc polycon} package, time derivatives and time shifts of dependent
variables are represented by subindices, so that e.g. in continuous time
\begin{equation}
y_{0}=y(t),\quad y_{1}=\dot{y}(t),\quad y_{2}=\ddot{y}(t),\quad {\rm etc.}
\end{equation}
while in discrete time
\begin{equation}
y_{0}=y(t),\quad y_{1}=y(t+1),\quad y_{2}=y(t+2),\quad {\rm etc.}
\end{equation}

This rule holds for input and output variables.  Higher derivatives or
shifts of state variables do not occur, so state variables are still called
$x_{1},\dots,x_{n}$ by default (if two state space descriptions are
involved the second one has state variables $z_{1},\dots,z_{n}$ by
default). In functions where the first derivative or time shift of the state
variables may occur, e.g.~{\tt io2ss} and {\tt newsys}, they are denoted by
$dx_{1},\dots,dx_{n}$.

In Maple, subscript is represented by concatenation so that e.g.~$y_{2}$ is
written {\tt y2}.

\vspace{2mm}
Some functions use global variables and most functions have default values
of input para\-meters that are names. In all cases where global names occur,
the user is warned if there is a conflict. The following default names are
used:

\vspace{2mm}\hspace{6mm}
\begin{tabular}{lc}
state variables: & $x_{1},\dots,x_{n}$\\
(second state representation): & $z_{1},\dots,z_{n}$\\
derivatives/shifts of state variables: & $dx_{1},\dots,dx_{n},\,
dz_{1},\dots, dz_{n}$\\
input variable: & $u$ or $u_{0}$\\
derivatives/shifts of input variable: & $u_{1},u_{2},\dots$\\
output variable: & $y$ or $y_{0}$\\
derivatives/shifts of output variable: & $y_{1},y_{2},\dots$
\end{tabular}

\vspace{2mm}
The theoretical background, with proofs for the correctness of the
algorithms is given in chapters 5 and 6 of the authors PhD-thesis
\cite{ForsmanPhD}, where also some source code for primitive versions of
the functions is given. Related work can be found in
\cite{Diop91a,DiopF91a,Glad88a,Glad89a,Ollivier90a}.

The theory behind {\tt loclyap} is also described in \cite{Forsman91a} and that
of {\tt par2ssc} in \cite{Forsman92d}.

\section{The Main Functions}

The largest part of the package is aimed at questions related to rational
state realizations of control systems. The diagram in figure \ref{contime}
summarizes the use of the different functions in the continuous time case.
In the diagram $p$ and $\varphi_{i}$ are differential polynomials in $u,y$,
i.e.~they involve time derivatives of $u$ and $y$ (but not of $x_{i}$).


\begin{figure}[t]

 \begin{picture}(100,60)(-20,-25)
	\put(-13,17){$\varphi_{i}(x_{i},u,y)=0$}
	\put(15,22){\vector(1,0){25}}
	\put(40,14){\vector(-1,0){25}}
	\put(20,24){{\tt io2ssc}}
	\put(20,16){{\tt obsvc}}

	\put(45,20){$\dot{x}=f(x,u)$}
	\put(45,15){$y=h(x,u)$}
	\put(70,22){\vector(1,0){32}}
	\put(79,24){{\tt ss2ioc}}

	\put(103,14){\vector(-1,0){35}}
	\put(72,16){{\tt io2ssc, par2ssc}}

	\put(108,17){$p(u,y)=0$}

	\put(45,-19){$\dot{z}=g(z,u)$}
	\put(45,-24){$y=j(z,u)$}

	\put(50,8){\vector(0,-1){18}}
	\put(55,-10){\vector(0,1){18}}
	\put(58,0){{\tt sstrac,}}
	\put(58,-5){{\tt newsysc}}
 \end{picture}

 \caption{Diagram describing continuous time functions.\label{contime}}
\end{figure}


\vspace{2mm}
For discrete time systems the functions in figure \ref{distime} are
available. Here $p$ and $\varphi_{i}$ involve time shifts of $u$ and $y$
(but not of $x_{i}$).


\begin{figure}

 \begin{picture}(100,60)(-20,-25)
	\put(-13,17){$\varphi_{i}(x_{i},u,y)=0$}
	\put(15,22){\vector(1,0){25}}
	\put(40,14){\vector(-1,0){25}}
	\put(20,24){{\tt io2ssd}}
	\put(20,16){{\tt obsvd}}

	\put(44,20){$x^{+}=f(x,u)$}
	\put(45,15){$y=h(x,u)$}
	\put(70,22){\vector(1,0){32}}
	\put(80,24){{\tt ss2iod}}

	\put(103,14){\vector(-1,0){35}}
	\put(80,16){{\tt io2ssd}}

	\put(108,17){$p(u,y)=0$}

	\put(44,-19){$z^{+}=g(z,u)$}
	\put(45,-24){$y=j(z,u)$}

	\put(50,8){\vector(0,-1){18}}
	\put(55,-10){\vector(0,1){18}}
	\put(58,0){{\tt sstrad,}}
	\put(58,-5){{\tt newsysd}}
 \end{picture}

 \caption{Diagram describing discrete time functions.\label{distime}}
\end{figure}


\vspace{2mm}
The functions {\tt sstrac} and {\tt sstrad} suppose that the two systems
involved are I/O-equivalent and then find the transformation between them.

\vspace{2mm}
The functions {\tt newsysc} and {\tt newsysd} take a system in state space
form and a transformation as inputs and returns the system in the new
coordinates, defined by the transformation.

\vspace{2mm}
There is no function {\tt par2ssd}, because it is unclear at the moment
whether it is always possible to go from a parametrization of a
hypersurface to a realization of the corresponding discrete time system.

\vspace{2mm}
For more information about a particular function, use the help command
\verb+?+ after having loaded {\sc polycon}, e.g.~\verb+?sstrac+
You can also type \verb+?polycon+ to obtain general information on
{\sc polycon}.


\section{The Implementation}

{\sc Polycon} heavily relies on Gr{\"o}bner bases computations and many
functions use the Boege-Gebauer-Kredel algorithm \cite{BoegeGK86},
implemented as {\tt finduni} in Maple, for eliminating variables.

There are two functions {\tt xss2ioc} and {\tt xss2iod} that are ``expert
versions'' of {\tt ss2ioc} and {\tt ss2iod}. They have exactly the same
syntax as the {\tt ss2io}-functions but the output is different: these
functions return an entire Gr{\"o}bner base for the ideal
\begin{equation}
\Big( y_{0}-h,\, y_{1}- L_{f}h,\, \dots,\, y_{n}-L_{f}^{n}h \Big)
\end{equation}
that is, a list of polynomials in the variables
\begin{equation}
y_{0},\, y_{1},\, \dots,\, u_{0},\, u_{1},\, \dots,\, x_{1},\, \dots,\, x_{n}
\end{equation}
The last polynomial of this list is the I/O-relation, the other ones are
relations between the state variables and $u,y$. (These are the relations
obtained in {\tt obsvc, obsvd}.) Since the ordinary {\tt ss2io}-functions
only apply {\tt finduni}, they are generically much faster.


\section{An Example}

Below we show an example how some computations on a simple control system
can be performed using {\sc polycon}. The example is taken from
\cite{McClamroch80}, p.~147.

The following equations roughly describe the vertical motion of a hot air
balloon:
\begin{equation}
\begin{array}{l}
\dot{x}_{1}\,=\, Ku - \frac{1}{t} \, (x_{1}-T)\\[2mm]
\dot{x}_{2}\,=\, x_{3}\\[2mm]
\dot{x}_{3}\,=\, g \left( \frac{W_{a}}{W} \, (1-\frac{T}{x_{1}})
-1-\frac{\mu}{W} \,x_{3} \right)
\end{array}
\end{equation}

Here $x_{2}$ is the altitude above sea level, $x_{3}= \frac{d}{dt}\,
{x}_{2}$ and $x_{1}$ is the air temperature (in Kelvin) in the balloon. The
constants $t,K,W_{a},\mu$ are related to the thermal and physical
characteristics of the balloon, $W$ is the weight of the balloon including
payload and air (in kg), $T$ is the outdoor temperature, and $g$ is the
acceleration of gravity.  The input $u$ of the system is the heat transfer
rate supplied to the balloon by the heater. Let us consider the altitude as
the output of the system: $y=x_{2}$. If we put $g=10, W=200, W_{a}=400$ (I
can't guarantee that these are realistic values\dots) we can use the
procedure {\tt ss2ioc} in {\sc polycon} to obtain a differential equation
relating the input and the output; this equation is
\begin{equation}
\begin{array}{c}
8000\,Tt\, y_{3} - 400(T +Kt\, u)\, y_{2}^{2} - 40\, \Big( \mu\, (Kt\,u +T)\,
y_{1} + 200\,Kt\, u + 10\,\mu\,Tt\Big)\, y_{2}\\[3mm]
- \mu^{2}(Kt\,u +T)\, y_{1}^{2} +400\,\mu Kt\, uy_{1}+40000(T-Kt\,u) \,=\,0
\end{array}
\end{equation}
where $y_{1}=\frac{d}{dt} y(t)$, $y_{2}=\frac{d^{2}}{dt^{2}}y(t)$ etc.
Note that the $t$ occurring as a parameter is not equal to time!

Now suppose that we have accurate measurements of the altitude $x_{2}$ (so
that we can compute the velocity and acceleration with acceptable
precision) and want to estimate the temperature in the balloon $x_{1}$.  We
can then use the function {\tt obsvc} to find an expression for $x_{1}$ in
the output and its derivatives. It turns out that
\begin{equation}
x_{1}\,=\, {\frac {400\,T}{200-20\,y_{2} -\mu\, y_{1}}}
\end{equation}


\vspace{2mm}
This is what a Maple session for doing the computations above could look like:
\begin{verbatim}
> with(linalg): read(`polycon.m`):
> f:=vector([-(1/t)*(x1-T)+K*u, x3, g*((Wa/W)*(1-(T/x1))-1-(mu/W)*x3)]);
> g:=10: Wa:=400: W:=200:
> p:=ss2ioc(f,x2):
> collect(p,[y3,y2,y1]);
                                        2
 8000 T t y3 + (- 400 T - 400 K u0 t) y2

      + ((- 40 mu K u0 t - 40 mu T) y1 + 8000 K u0 t + 400 mu T t) y2

             2       2           2
      + (- mu  T - mu  K u0 t) y1  + 400 mu K u0 t y1 + 40000 T

      - 40000 K u0 t

> obsvc(f,x2,x1);
                                      T
                      [- 400 -------------------]
                             20 y2 - 200 + y1 mu
\end{verbatim}


\vspace{4mm}
\begin{center}{\Large\bf Acknowledgement}\end{center}
This work was financially supported by the Swedish Board for Technical
Development (STU) and the Swedish Council for Technical Research (TFR).

\begin{thebibliography}{10}

\bibitem{BoegeGK86}
W.~Boege, R.~Gebauer, and H.~Kredel.
\newblock Some examples for solving systems of algebraic equations by
  calculating {G}r\"obner bases.
\newblock {\em J. Symbolic Computation}, 1:83--98, 1986.

\bibitem{Diop91a}
S.~Diop.
\newblock Elimination in control theory.
\newblock {\em Math. Control Signals Systems}, 4(1):17--32, 1991.

\bibitem{DiopF91a}
S.~Diop and M.~Fliess.
\newblock On nonlinear observability.
\newblock In {\em Proc.\ First European Control Conf.}, volume~1, pages
  152--157, Grenoble, France, July 1991. Herm{\`e}s.

\bibitem{Forsman91a}
K.~Forsman.
\newblock Applications of {G}r{\"o}bner bases to nonlinear systems.
\newblock In {\em Proc.~First European Control Conf.}, volume~1, pages
  164--169, Grenoble, France, July 1991. Herm{\`e}s.

\bibitem{ForsmanPhD}
K.~Forsman.
\newblock {\em Constructive Commutative Algebra in Nonlinear Control Theory}.
\newblock PhD thesis, Dept.~of Electrical Engineering, Link{\"o}ping
  University, S-581 83 Link{\"o}ping, Sweden, 1991.

\bibitem{Forsman92d}
K.~Forsman.
\newblock On rational state space realizations.
\newblock In M.~Fliess, editor, {\em Proc.~NOLCOS'92}, pages 197--202,
  Bordeaux, 1992. IFAC.

\bibitem{Glad88a}
S.T. Glad.
\newblock Nonlinear state space and input output descriptions using
  differential polynomials.
\newblock In J.~Descusse, M.~Fliess, A.~Isidori, and D.~Leborgne, editors, {\em
  New Trends in Nonlinear Control Theory}, pages 182--189. Springer, 1988.

\bibitem{Glad89a}
S.T. Glad.
\newblock Differential algebraic modelling of nonlinear systems.
\newblock In M.A. Kaashoek, J.H. van Schuppen, and A.C.M. Ran, editors, {\em
  Realization and Modelling in System Theory. Proc. Intl. Symp. MTNS-89},
  volume~I, pages 97--105, Amsterdam, 1990. Birkh\"auser.

\bibitem{McClamroch80}
N.H. McClamroch.
\newblock {\em State Models of Dynamic Systems - A Case Study Approach}.
\newblock Springer, 1980.

\bibitem{Ollivier90a}
F.~Ollivier.
\newblock {\em Le probl{\`e}me de l'identifiabilit{\'e} structurelle globale:
  approche th{\'e}orique, m{\'e}thodes effectives et bornes de complexit{\'e}}.
\newblock PhD thesis, {\'E}cole Polytechnique, 1990.

\end{thebibliography}

\end{document}
