Chapter 20
Commands for Making and Using GB’s

This section contains a glossary of commands available for generating and using non-commutative Gröbner Basis.

20.1 Simplification

Before using these commands, a monomial order must be specified. See the section after this for information on how to set the monomial order.

20.1.1 NCSimplifyAll[expressions, startRelations, iterations]

Aliases: GroebnerSimplify, NCGroebnerSimplify

Description: NCSimplifyAll[expressions, startRelations, iterations] calls NCMakeGB[startRelations, iterations] and uses the result to reduce the expressions in expressions. This is useful when the form the Gröbner Basis is irrelevant and is only used to simplify some set of predetermined equations.

Arguments: exprs can be either an expression or a list of expressions. startRelations is a list of polynomials. iterations is a positive integer.

Comments / Limitations: Not available before NCAlgebra 1.2

20.1.2 NCSimplifyRationalX1[expressions, startRelations, iterations]

Aliases: None

Description: NCSimplifyRationalX1[expressions, startRelations, iterations] is (essentially) equivalent to
NCSimplifyAll[expressions, Join[startRelations, inverses], iterations]
where inverses is a list of polynomials. inverses consists of the defining relations of all inverses (elements with inv[...]) in expressions and startRelations. NCSimplifyRationalX1 simplifies expressions with startRelations together with some additional innocuous relations.
NCSimplifyRationalX1 is different from NCSimplifyAll with the following adjustment: first all instances of inv are converted to Inv before calling NCSimplifyAll, and are converted back afterwards. This overrides NCAlgebra’s automatic handling of inverses. For example, the command
NCSimplifyRationalX1[{inv[x] **inv[1 - x] + y},{z **inv[y] - a}, 10]
equals
NCSimplifyAll[{Inv[x]**Inv[1-x]+y},{z**Inv[y]-a,y**Inv[y]-1,Inv[y]**y- 1,Inv[x]**x-1,x**Inv[x]-1, (1-x)**Inv[1-x]-1,Inv[1-x]**(1-x)-1}, 10].
This call to NCSimplifyAll returns Inv[x] + Inv[1-x] + y. The call to NCSimplifyRationalX1 returns inv[x] + inv[1-x] + y.

Arguments: expressions is a list of polynomials. startRelations is a list of polynomials. iterations is a natural number.

Comments / Limitations: Not available before NCAlgebra 1.2.

20.2 Making a Gröbner Basis and various options (with their defaults)

Before using any of these commands, you must set a monomial order. See Chapter 18.

20.2.1 NCMakeGB[aListOfPolynomials, iterations]

Aliases: NCMakeRules, MorasAlgorithm

Description: The GB algorithm proceeds through at most iterations iterations until a Gröbner basis is found for the list of polynomials aListofPolynomials with respect to the order imposed by SetMonomialOrder, see §18.5.1. NCMakeGB calls a C++ program and while the C++ program is running, it prints intermediate lists of rules to the screen. When the C++ program finishes, it is either because it has run iterations number of iterations or it has found a Gröbner Basis. If it has found a Gröbner Basis, it prints a message saying so. One may also use the command FinishedComputingBasisQ[] in §20.2.5. The Mathematica output of NCMakeGB is a list of polynomials.
 
The following computes the Gröbner basis for the ideal generated by x² -a and x³ -b. For options which can be used inside NCMakeGB, see ReturnRelationsToMma, SupressCOutput??, SupressAllCOutput??, UserSelect and Deselect -DISABLED.

Arguments: aListofPolynomials is a list of polynomials. iterations is a natural number.

Comments / Limitations: Not available before NCAlgebra 1.2

20.2.2 UserSelect→{}(Distinguishing important relations)

Aliases: None

Description: UserSelect is an option for NCMakeGB and for Spreadsheet. If UserSelect→aListOfPolynomials is given as an option, then the main effect is on the display produced by RegularOuput throughout the rest of the session. UserSelect is cumulative and more and more polynomials fall into the selected category as the user puts them in. The command RegularOutput automatically scans for selected polynomials to display in the collection of relations labelled USER SELECTS. It finds them only after NCMakeGB has been run with the user selects (since RegularOutput searches for the selected polynomials by there number. Henceforth, aListOfPolynomials is displayed as a special category. The default value is {}.

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2

20.2.3 ClearUserSelect[]

Aliases: None

Description: Clears the UserSelected polynomials, that is, it makes the USER SELECTED empty

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2

20.2.4 Deselect→{} (DISABLED)

Aliases: None

Description: Deselect is an option for NCMakeGB. If DeSelectPoly→aListOfPolynomials is given as an option for NCMakeGB, then certain S-polynomials will not be computed. Specifically, no S-polynomial will be formed between two deselected polynomials. Deselect is NOT cumulative. The default value is {}.

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2. Bug: Only the deselected polynomials which are also members of the first argument for NCMakeGB are deselected.

20.2.5 FinishedComputingBasisQ[] - Untested in 1999

Aliases: None

Description: FinishedComputingBasisQ[] returns 0 or 1. If it returns 1, then NCMakeRules stopped because it obtained a Gröbner Basis. If it returns 0, then NCMakeRules stopped because it ran the maximal number of iterations and did not find a Gröbner Basis.

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2

.

20.2.6 WhatIsPartialGB[]

Aliases: None

Description: Since we do not require GB algorithm to run until it obtains a Gröbner Basis, the output of the algorithm need not be a Gröbner Basis. We call the output of the algorithm a partial basis. WhatIsPartialGB[] returns a list of all of the elements in the partial groebner basis. See PartialBasis[n].

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2. See also §29.1.3

20.2.7 NCGBSetIntegerOverflow[False]

Aliases: None

Description: An MakeNCGB and NCProcess command which if set True permits large integers to be handled carelessly by C + +. This is dangerous since it causes mistakes when you see large integers (at about 2 billion watch out). The code runs faster with this setting, but still for saftey sake the default is NCGBSetIntegerOverflow[False].

Arguments: None

Comments / Limitations:

20.2.8 PartialBasis[aNumber] - Untested in 1999

Aliases: None

Description: PartialBasis[aNumber] (where aNumber is a positive integer) returns a character string. If this character string is input to the built-in Mathematica command ToExpression, then the result is the aNumber-th element of the partial basis data base.

Arguments: aNumber is a natural number.

Comments / Limitations: Not available before NCAlgebra 1.2. See also 29.1.3. Note: aNumber does not correspond to the numbers generated from the WhatIsHistory command.

20.2.9 IterationNumber[aList] or IterationNumber[ aNumber ] - UNTESTED 1999

Aliases: None

Description: It might be interesting to find out which relations are generated during which iteration of the algorithm. The command IterationNumber returns these numbers. The most common applications of this command will probably be IterationNumber[WhatAreGBNumbers[]] and IterationNumber[WhatAreNumbers[]].

Arguments: aList is a list of integers. aNumber is an integer

Comments / Limitations: Not available before NCAlgebra 1.2.

20.2.10 CleanUp

Aliases: None

Description: CleanUp → 1

Arguments: NCProcess and NCMakeGB Option which controls the reduction step inside Mora’s GB algorithm. When set to 1 the new S- polynomials reduce the current set of relations. When CleanUp → 0 they do not.

Comments / Limitations:

20.2.11 SetCleanUpBasis[n] - Untested in 1999

Aliases: None

Description: If n is nonzero (best to use n=1), SetCleanUpBasis [n] indicates that the program used to implement NCCleanUpRules should be applied after each iteration of the GB algorithm. SetCleanUpBasis[0] indicates that such additional processing should not be done.

Arguments: n is an integer

Comments / Limitations: Not available before NCAlgebra 1.2

20.2.12 CleanUpBasisQ[] - Untested in 1999

Aliases: None

Description: CleanUpBasisQ[] returns the argument of the SetCleanUpBasis command the last time it was used.

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2. This allows one to see which “cleaning” option is in force.

20.2.13 History Off

NCGB has the ability to track the history of GB production. This is used when the RemoveRedundant Options are turned on in NCProcess. Since much storage is consumed by this history it is often advantageous to turn it off. If you are just running NCMakeGB and you want to turn it off do this.

The command

turns off the history collection, except that it replaces useless rules which the code produced by the one dummy rule

The command

turns on the history collection.

If you happen to bring an InvalidHistoryRule → 0 back into Mma, either

a) InvalidRuleHistory is not a member of the order (as expected) and an error message is printed and then is reformatted as 1 → 0 OR

b) InvalidRuleHistory is (artificially) a member of the order and one gets InvalidHistoryRule → 0.

20.2.14 Correspondence to sections ‘Simplification’ and ‘Reduction’

This subsection is a brief note to bring out the conceptual connection between making a Gröbner Basis and the simplification commands and the Reduction commands. Making a Gröbner Basis is the first step in the simplification commands presented above. Making a Gröbner Basis is also the main step in the the command SmallBasis in §21.1.1 and Spreadsheet in §15.2.1.

20.2.15 Setting Monomial Orders- See Chapter 18

20.2.16 ReinstateOrder[]

Aliases: None

Description: After a call to SetGlobalPtr[], ClearMonomialOrde r[] or ClearMonomialOrderN[n], ReinstateOrder[] is used to restore the previously established order of indeterminates. The exception is C learOrder[]. After this function is called, the order cannot be restored.

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2.

20.3 Reduction

20.3.1 Reduction[aListOfPolynomials, aListOfRules]

Aliases: None

Description: Reduction[aListOfPolynomials, aListOfRules] computes the Normal Forms of aListOfPolynomials with respect to the rules aListOfRules.

Arguments: aListOfPolynomials is a list of polynomials. aListOfRules is a list of rules. That is the rules are applied repeatedly to the polynomials in the list until no further reduction occurs

Comments / Limitations: Not available before NCAlgebra 1.2

20.3.2 PolyToRule[aPolynomial]

Aliases: PolToRule,ToGBRule,ToGBRules

Description: PolyToRule[aPolynomial] returns the replacement rule corresponding to aPolynomial, assuming the order of monomials has been set.

Arguments: aPolynomial is a polynomial

Comments / Limitations: Not available before NCAlgebra 1.2

20.3.3 RuleToPoly[aRule]

Aliases: None

Description: RuletoPoly[aRule] returns aPolynomial corresponding to the replacement rule aRule.

Arguments: aPolynomial is a polynomial

Comments / Limitations: Not available before NCAlgebra 1.2