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 x2 -a and x3 -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
SetRecordHistory[False]
turns off the history collection, except that it replaces useless rules which the code produced by the
one dummy rule
InvalidHistoryRule → 0
The command
SetRecordHistory[True]
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