
\centerline{ABSTRACT}

    Currently, the three most popular commercial computer algebra 
systems are Mathematica, Maple and MACSYMA (the 3 M's). These systems 
provide a wide variety of symbolic computation facilities for 
commutative algebra and contain implementations of powerful algorithms 
in that domain. The Gr\"obner Basis Algorithm, for example, is an 
important tool used in computation with commutative algebras and in 
solving systems of polynomial equations.

    On the other hand, most of the computation involved in linear 
control theory is performed on matrices, and these do not commute. A 
typical issue of IEEE TAC is full of A B C D type linear systems and 
computations with the A B C D's or partitions of them into block 
matrices. The 3 M's are weak in the area of non-commutative 
operations. They allow a user to declare an operation to be 
non-commutative, but provide very few commands for manipulating such 
operations and no powerful algorithmic tools.

    It is the purpose of this article to report on applications of a 
powerful tool: a non-commutative version of the Gr\"obner Basis 
Algorithm. 
The commutative version of this algorithm is implemented on
each of the three M's. It has many applications ranging
from solving systems of equations to computations
involving polynomial ideals. 
The noncommutative version is relatively new {\bf [FMora]}.

Part I of the paper introduces Gr\"obner Bases (GB) 
and lays the foundation for simplification of complicated
algebraic expressions from engineering and other 
applications.
In part II
we shall describe the Gr\"obner Bases for several elementary 
situations which arise in systems theory. 
These GB give 
(in a sense to be made precise) 
a ``complete" set of simplifying rules for formulas which 
arise in these situations. 
We have found that this process provides a practical means of 
simplifying expressions.

We begin Part III with an illustration of how the simplification
rules from Part I apply in system theory.
Section \ref{section:four} illustrates the use of Gr\"obner Basis
with an application to the 
Doyle-Glover-Khargonekar-Francis
theory of $H^\infty$ control. 
%Our application is to the Doyle Glover Khargonekar Francis
%theory of $H^\infty$ control. This is done Section 4.
The rest of Part III 
explores other facets of the Gr\"obner Basis machinery.
%turns the GB machinery to other issues.


%In a particular algebraic situation, the GB produced
%depends on the selection of a type of ordering.
%In Section 6, we investigate the effect of various orders
%on the size of the resulting GB.
%Since a GB can take considerable computer time to generate, it is clear
%that generating and using a small GB is more efficient than generating 
%a large (or infinite) GB. 
%Section 6.1 analyzes GB which naturally arise
%when studying Lyapunov equations.
%Our itesis is on the
%effect of particular orders on whether or not one
%obtains a finite GB. Hopefully, the findings in 
%Section 6.1 give the reader practical intuition 
%on which orders produce finite GB.
%To test and illustrate the intuition developed in Section 6.1
%about Lyapunov equations, we consider the case of a lossless system
%in Section 6.2.

The simplification process and the Gr\"obner Basis depend
on the choice of an ordering on variables. In Section 
\ref{section:six}
we will examine the effect of changing the ordering on
the GB which arise in connection with Lyapunov
equations .

%------------
%
%DELETE ??
%
%and give an application to Lossless systems. We provide
%examples, in which the same starting relations
%produce both finite and infinite GBs depending on the
%choice of ordering.
%%Since an infinite
%%GB can take considerable computer time to generate, it is clear
%%that generating and using a small GB is 
%%more efficient than generating 
%%large (or infinite) GB. 
%
%----------------------


In addition to providing an approach to simplifying
complex expressions, the Gr\"obner Basis Algorithm
%these complete sets of rules 
can be used to generate new and (sometimes) interesting
equations from equations
that are the statements of the basic assumptions. 
For example, the Youla-Tissi formulas involving
the intertwining of the controllability and
observability operators of a system arise as a subset of the
Gr\"obner bases studied in Section \ref{section:yt}.


    The research required the use of software suited for computing with 
non-commuting symbolic expressions.  
Most of the research was 
performed using a special-purpose system developed by 
%performed using a special-purpose system developed for the project by 
%J. Wavrik. This system uses a new approach to the development of 
J. Wavrik. This system uses a new approach to the creation of 
support software for mathematical research. 
%mathematical software. 
It provides the flexibility needed for 
experimentation with algorithms, data representation, and data 
analysis. 

    In an effort to make available computational facilities for work 
in non-commutative algebras to a wider audience, the other authors 
have written a collection of packages for Mathematica called NCAlgebra 
(available from ncalg@osiris.ucsd.edu).  
NCAlgebra has a number of commands for manipulating 
non-commuting expressions which are named and designed
to be noncommutative analogs of Mathematica's built
in commands.
We have incorporated in these packages many of the results 
on simplification obtained from this research.


