... indeterminates.¹

If an analyst saw the equation $AB = 1$ for matrices $A$ and $B$, then he might say that $A$ and $B$ satisfy the polynomial equation $x y -1=0$. An algebraist would say that $x y-1$ is a relation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... software.²

When the file ``NCGB.m" is loaded, it loads the file NCAlgebra.m which in turn loads lots or few files depending on how one has set the environmental variable $NC$LongLoadTime$. The default is $NC$LongLoadTime$=True. To save time you can set $NC$LongLoadTime$=False before loading NCGB.m.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.... ¹

There are many orders which ``sit well with intuition". Perhaps the order $Inv[y] < y < Inv[1-y] < a < x$ does not set well, since, if possible, it would be preferable to express an answer in terms of $y$,rather than $y^{-1}$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... input²

This sets a graded lexicographic on the monic monomials involving the variables $y$, $Inv[y]$, $Inv[1-y]$, $a$ and $x$ with $y< Inv[y] < Inv[1-y] < a < x$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... type³

See also §13.4.1

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... unknowns.¹

In future sections we will refer to two collections of equations: the relation mentioned above as well as a set of user selected relations.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... user.²

These do not exist in the first run. A user-selected equation is a polynomial equation which the user has selected. The algorithm described in §19.3.4 treats these equations as ``digested." This, for example, implies that they are given the highest priority in eliminating other equations when NCProcess runs. For example, equations which one knows can be solved by Matlab can be selected.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... equation¹

This polynomial is not written as a rule since it has a collected form as described in §22.2. This collected form can be used to assist a person in finding decompositions (see §[HS]).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... known²

If the user does not notice it at this point, it will become very obvious with an additional run of NCProcess1.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... again³

There is limit of 2 iterations.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... produced⁴

It is not hard to see that NCProcess2 would not have an effect, since the set of equations found on the previous spreadsheet can be easily seen to be minimal. We include the run here for pedagogical reasons.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... lengths¹

`$\ll$' are called multigraded lexicographic orders. Intuitively, we think of $A$, $B$ and $C$ as corresponding to variables in some engineering problem which represent quantities which are known and think of $a$, $b$, $c$, $d$, $e$ and $f$ as corresponding to variables in the engineering problem which represent quantities which are unknown. The fact that $d$, $e$ and $f$ are in the top level indicates that we are very interested in solving for $d$, $e$ and $f$ in terms of $A$, $B$, $C$, $a$, $b$ and $c$, but are not willing to solve for $b$ in terms of expressions involving either $d$, $e$ or $f$.

More precise discussion of mulitgraded lex orderings are in Chapter 21.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... number.²

Up to four iteration numbers can be specified. When only one is given, $NCProcess$ uses that number to choose default values for the other iteration numbers. If the user specifies four values, $I_1$, $I_2$, $I_3$, $I_4$, then $I_1$ is the iterations for NCMakeGB, $I_2$ is the iterations for NCMakeGB on the digesteds, $I_3$ is the iterations for SmallBasis, and $I_4$ is the iterations for the knowns in SmallBasis.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...almosrithm ¹

This is a simplification of the methods which we will introduce later in the paper.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...much ²

See the definition of the notation >> for the technical meaning of `much'/

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... decision.³

For example,

(a) If $R_1$ is $au_1=u_1c$, then the discussion in Example 1.1 might lead him to take $u_1=0$. This makes $u_1$ a known variable so it would be removed from $\cal U$ in the ordering.

(b) If $R_1$ is an algebraic Riccati equation in $u_1$ the user might feel that since numerical packages solve these easily it is reasonable to take as a hypothesis that $u_1$ can be solved for uniquely. In this case the user removes $u_1$ from the set of unknowns $\cal U$. It remains in $\cal A$.

(c) The expert may decide that $R_1$ does not determine $u_1$ uniquely. Then $u_1$ cannot be removed from $\cal U$ and therefore be declared to be a known. The user can then modify the equations to incorporate whatever is known about the solution to the equation $R_1=0$. For example, if one knows that every solution has the form of a sum of a particular solution and a member $v$ of the kernel of some operator, then a relation $u_1 = ParticularSolution + v$ where $ParticularSolution$ is considered known, $v$ is considered not known and an additional relation is added to specify that $v$ is a member of a kernel.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 2.⁴

If one does nothing during step (4) each time through this loop (see (8)), then any results obtained would be purely algebraic.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... unknowns.⁵

In future sections we will refer to two collections of equations: the relation mentioned above as well as a set of user selected relations.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... user.⁶

These do not exist in the first run. A user-selected equation is a polynomial equation which the user has selected. The algorithm described in §19.3.4 treats these equations as ``digested." This, for example, implies that they are given the highest priority in eliminating other equations when NCProcess runs. For example, equations which one knows can be solved by Matlab can be selected.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... )⁷

From this ordering on indeterinates one induces a order on polynomials which is different than we used before. There we used a graded order here we use a strict lexicographic order.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... triangular:⁸

There need not be $\le$ n equations in this list and there need not be any equation in just one variable.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... run.⁹

See Appendix 41 for an example of this.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ideal.¹⁰

The use of the word ``small" rather than minimal is intentional. See §12 of [HS].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... unknown¹

If one wants to speak very loosely, then we would say that $a$, $b$ and $c$ are unknown and $d$, $e$ and $f$ are ``very unknown."

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.... ¹

It takes 113 seconds. The present implementation of the code involves alot of interaction with Mathematica. We expect future versions of the code to be faster.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... should¹

Here date represents the month,date and year that the file was put on anonymous ftp (for example, 2.14.96 means that the the file was put on anonymous ftp on Febuary 14,1996.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... NCGB.¹

You may want to type $NC$Developers$=False. Note the default is $NC$Developers$=True. This unsets an environment variable which means you get the fancy version of our testing programs. We have forgotten what this does.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... dag)¹

A common and canonical example of a dag is a tree

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.... ²

It takes 113 seconds. The present implementation of the code involves alot of interaction with Mathematica. We expect future versions of the code to be faster.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... higher¹

and maybe before too long under Windows

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... higher¹

We know that 2.6.0 will not work. We have not tried 2.6.1 or 2.6.2. We have tried 2.7.0 on an HP. Version 2.7.2 works on Suns

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... argument.¹

In fact even if one realized from the beginning of the computation that $a$ and $c$ have no common eigenvalues, there is no way to express this hypothesis using polynomial equations. In fact, a complete analytic argument which showed that would consist of an algebraic derivation of the identity followed by the use of the hypothesis that $a$ and $c$ have no common eigenvalues. One would not in general know in advance that and so it would be premature to add ``b=0" to the collection of polynomial equations at the beginning of the computation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Helton¹

This work was partially supported by the AFOSR and the NSF.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Helton²

This work was partially supported by the AFOSR and the NSF.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... dag)¹

A common and canonical example of a dag is a tree

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.... ²

It takes 113 seconds. The present implementation of the code involves alot of interaction with Mathematica. We expect future versions of the code to be faster.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... higher¹

and maybe before too long under Windows

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... higher¹

We know that 2.6.0 will not work. We have not tried 2.6.1 or 2.6.2. We have tried 2.7.0 on an HP. Version 2.7.2 works on Suns

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... argument.¹

In fact even if one realized from the beginning of the computation that $a$ and $c$ have no common eigenvalues, there is no way to express this hypothesis using polynomial equations. In fact, a complete analytic argument which showed that would consist of an algebraic derivation of the identity followed by the use of the hypothesis that $a$ and $c$ have no common eigenvalues. One would not in general know in advance that and so it would be premature to add ``b=0" to the collection of polynomial equations at the beginning of the computation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Helton¹

This work was partially supported by the AFOSR and the NSF.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Helton²

This work was partially supported by the AFOSR and the NSF.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.