Chapter 13
NCProcess: What It Does

What you saw in Chapter 11 was an example of the command NCProcess and of our favorite form for output called a ”spreadsheet”. Now we give a little bit of an idea of what it does. Later we explain NCProcess in much more detail, since we will not be providing descriptions of how to use commands or much else in this chapter. See Chapters 9 and 14. For more on concepts see Chapter 16. The example in Chapter 14 is a very good illustration of these ideas. The description of how NCProcess is called is given in the previous chapters and Chapter 15.

We use the abbreviations GB and GBA to refer to Gröbner Basis and Gröbner Basis Algorithm respectively. We begin by describing a facet of noncommutative GB’s which we have not yet described. GB’s are very effective for eliminating, or solving for, variables.

13.1 NCProcess: Input and Output

The commands which we use heavily are called NCProcess1 and NCProcess2. NCProcess1 and NCProcess2 are variants on a more general command called NCProcess. A person can make use of NCProcess1 and NCProcess2 without knowing any of the NCProcess options.

The NCProcess commands are based upon a GBA and will be described in §15.2. GBA’s are very effective at eliminating or solving for variables. Also we have algorithms for removing Redundant equations for the output which can be turned on and off as options. NCProcess2 removes them much more agressively than NCProcess1, but is much slower and it may remove an equation you really like. Also we have algorithms for removing Redundant equations for the output which can be turned on and off as options. A person can use this practical approach to performing computations and proving theorems without knowing anything about GBA’s or the options.

The input to NCProcess command one needs:

I1. A list of knowns.
I2. A list of unknowns (together with an order which gives you priorities for eliminating them).
I3. A collection of equations in these knowns and unknowns. 1
I4. A number of iterations.

The knowns (I1) are set using the SetKnowns command, The unknowns (I2) are set using the SetUnknowns command, For example, SetKnowns[A,B,C] sets A, B and C known and SetUnknowns[x,y,z] sets x, y and z unknown. Also, in this case, the algorithms sets the highest prioirity on eliminating z, then y and then x. Some readers might recall this is exactly the information needed as input to NCMakeGB.

The output of the NCProcess commands is a list of expressions which are mathematically equivalent to the equations which are input (in step I3). That is, the output equations and input equations have exactly the same set of solutions as the input equations. When using NCProcess1, this equivelent list hopefully has solved for some unknowns. The output is presented to the user as

O1. Unknowns which have been solved for and equations which yield these unknowns.
O2. Equations involving no unknowns.
O3. Equations selected or created by the user. 2 For example, in the context of S1 below, one would want to select the equation E17. There are also times during a strategy when one wants to introduce new variables and equations. This is illustrated in Chapter 14.
O4. Equations involving only one unknown.
O5. Equations involving only 2 unknowns. etc.

We say that an equation which is in the output of an NCProcess command is digested if it occurs in items O1, O2 or O3 and is undigested otherwise. Often, in practice, the digested polynomial equations are those which are well understood.

13.1.1 When to stop

Often one makes a run of NCProcess1 gets some likable equations, puts them in to another run of NCProcess.

The digested equations (those in items O1, O2 and O3) often contain the necessary conditions of the desired theorem and the main flow of the proof of the converse. If the starting polynomial equations follow as algebraic consequences of the digested equations, then we should stop. One might run NCProcess2 at this point inorder to get few equations.

13.2 Changing Variables

Often to solve a problem one must change variables. Our belief is that for system engineering problems the changes of variables are fairly simple.

The nature of a simple effective class of changes of variables is explained in [HS99] and sketched in Chapter 31 The NCProcess output prompts for changes of variables if NCCOV True by placing parentheses in carefully selected places. The experimental commands described in §31 actually automates this change of variable business to some extent.